Count Bits in Words

How do we count the number of 1-bit in a 32-bit unsigned integer, x? A naive approach is like this.

pop = 0;
for (i = 0; i < pop =" pop" x =" x">> 1;
}

Can we do better? Yes, according to Henry S. Warren, Jr., who wrote "The Quest for an Accelerated Population Count" of Beautiful Code. There are many ways to improve the loop. For example, if x is a small number, then the loop can be improved as followed.

pop = 0;
while (x) {
pop = pop + (x & 1);
x = x >> 1;
}

The following is looped as many times as the number of 1-bit in x.

pop = 0;
while (x) {
pop = pop + 1;
x = x & (x - 1); //turn off the rightmost bit
}

Or we can trade space for time. Look up the number of 1-bit in a table.

static char table[256] = {0, 1, 1, 2, 1, 2, 2, 3, ...,
pop = table[x & 0xFF] + table[(x >> 8) & 0xFF] + table[(x >> 16) & 0xFF] + table[x>> 24];

And several non-trivial approaches are discussed in the article. The author further applied the 'population count' functions to other problems, such as comparing population counts of two words, calculating Hamming distance, computing the number of trailing 0s in a word and allowing fast direct indexed access to a sparse array. Someone even posted performance analysis of the population count functions on the Internet. It seems Google would ask this kind of questions in an interview. Though I am not sure where I can apply the population count functions in my projects, Mr. Warren's article is definitely very informative.