The population count instruction has a miscellany of uses. As mentioned at the beginning of this chapter, one use is to compute the size of a set when sets are represented by bit strings. In this representation, there is a "universe" set whose members are numbered sequentially. A set is represented by a bit string in which bit i is 1 if and only if member i is in the set.
Figure 10-3. A circuit for the total population count of seven words
Another simple application is to compute the Hamming distance between two bit vectors, a concept from the theory of error-correcting codes. The Hamming distance is simply the number of places where the vectors differ, that is:
x, y) = pop(
The population count instruction may be used to compute the number of trailing 0s in a word, using relations such as:
x) = pop(¬
x– 1)) = 32 – pop(
(The reader who is not familiar with these mixtures of arithmetic
and logical operations might pause for a few moments to discover why
they work.) The function
ntz(x) also has a
miscellany of uses. For example, some early computers, upon interrupt,
would store a "reason for interrupt" bit in a special register. The bits
were placed in a position that identified which type of interrupt
occurred. The positions were chosen in priority order, usually with the
higher-priority interrupts in the less significant positions. Two or more ...