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:^{[26]}

dist() = pop(`x, y`

⊕`x`

)`y`

The *population count* instruction may be used
to compute the number of trailing 0s in a word, using relations such as:

ntz() = pop(¬`x`

& (`x`

– 1)) = 32 – pop(`x`

| –`x`

)`x`

(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 ...

Start Free Trial

No credit card required