## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Applications

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.

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(`x, y`) = pop(`x` ⊕ `y`)`

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

`	ntz(`x`) = pop(¬`x` & (`x` – 1)) = 32 – pop(`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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required