Bit Counting – Why Brian Kernighan’s Method Works

bitcount

I found this link to count number of bits in a variable. I think it is pretty cool, but I can't figure out why it works. Can someone offer an explanation?

Here is the code

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
}

Any help is appreciated.

Best Answer

The idea is that each iteration sets the least significance bit that isn't zero to zero -and only it. Since each iteration converts exactly bit from 1 to 0, it'll take as many iterations as there are non-0 bits to convert all the bits to 0(and thus v == 0 and the loop finishes).

So, how does this work? Lets say that the bit at index n is 1 and that the bits in indexes 0 upto n-1 are all 0(we'll use little endianess - so index 0 is 1, index 1 is 2, index 2 is 4, index 3 is 8 and so on).

v-1 subtracts from index 0 - but it's 0, so it converts it to 1 and subtracts from index 1 - but it's also 0, so it converts it to 1 and subtracts from index 2 - and so on until we reach index n. Since index n is 1 it can subtract from it and turn it to 0 - and there it stops.

So, v-1 is like v except there are n 0 that became 1 and one 1 that became 0. In v & v - 1 all the other bits remain as is, the n zeros that where turned to ones remain 0(because 0 & 1 == 0), and the one 1 that was turned to 0 turns to 0(because 1 & 0 == 0). So overall - only a single bit was changed in the iteration, and this change was from 1 to 0.

Related Topic