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