Population Counts

5 Aug 2007

In Beautiful Code, Henry S. Warren, Jr., discusses a population count or sideways sum algorithm, which "calculates the number of bits in a computer word that are 1." [1] The problem of finding the number of set bits in a binary value has a number of applications, apparently, although I have never seen it except in answering Google interview questions. (Representing a set of elements as a bit string, with the bit corresponding to an element set to 1 if the element is present in the set, is fairly common. However, I have never had to count the number of elements in the set.)

Warren describes several ways of computing the count, from a couple of simple iterations over the bits of the value (in this case, one C int of 32-bits) to a table lookup, and finally to a couple non-trivial bit-manipulation schemes. The fourth algorithm, using a parallel divide-and-conquer approach, is particularly nice, from both an analysis as well as a performance viewpoint, and is the subject of this note.

I needed notation that is not easily available in HTML (or ReStructured Text), so I used LaTeX and provide PDF copy of the analysis.

[population_count.pdf]