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

[1] | Henry S. Warren, "The Quest for an Accelerated Population
Count," in Beautiful Code: Leading Programmers Explain How They
Think, edited by Andy Oram and Greg Wilson, O'Reilly Media, 2007. |