Cast some light on population count algorithm

Question

I looked for good methods to do popcount (count of set bits). I found this one, here

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for(c = 0; v; c++) 
{
    v &= v - 1; // clear the least significant bit set
}

Trying on a few examples, its true that it works. What property of binary operations / representation makes it work?

Could you hint at some further readings on popcount and binary representation?

Answer 1

You're starting off with an initial v that initially has n bits in it set.

The point of the game is to have 1 less bit to count at each iteration of the loop. That way, we can just count the number of iterations of the loop that were necessary before we got to the point where n = 0 to figure out the value of the initial n.

Notice that, if n = 0, then v = 0, and so the loop will stop at this point. But so long as v > 0, we'll run the body of the loop at least once. At each iteration, we end up with a v that has 1 fewer bit set.

Here's why. The first property we need is that v && v == v. Now v is a sequence of bits (the exact number of bits depends on your machine / OS), that you can order from most significant to least significant. When you decrement v, we can note the following:

1. the least significant bit, call it v[k], that is set to 1 will be set to 0;
2. all bits more significant than v[k] will not change when you decrement v.

Therefore, ANDing v with its decrement will preserve all the more significant bits, but set v[k] to 0. And by definition, all bits that are less significant than v[k], ie v[k-1] ... v[0], are already 0 because v[k] is "the least significant bit that is 1". Therefore after ANDing all the less significant bits will remain at 0. The upshot is that v && (v - 1) contains one less bit set to 1 than v has.