3

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.

yannis
  • 39,547
  • 40
  • 183
  • 216
flashburn
  • 147
  • 1
  • 8
  • This code should be written with a while loop, not a for. – AK_ Dec 12 '15 at 11:28
  • 3
    Dear close voters: this question is not "asking for assistance in writing or debugging existing code," it is asking for help understanding an algorithm. –  Dec 12 '15 at 20:36

2 Answers2

8

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.

Idan Arye
  • 12,032
  • 31
  • 40
0

I am adding this answer which is similar to the answer above, but is a slightly different way at looking at things, so it might help someone.

Suppose we take the number 1111 (in binary) and subtract 1 from it, we get 1110 & again subtracting 1, we get, 1101 and we see a pattern emerge, i.e. to subtract 1 from a binary number flip all the 0's to the right of the least significant '1' bit to 1 and then flip that '1' itself to a 0 (assuming that the most significant bit is the left most bit and the least significant bit is the rightmost bit).

So, suppose, we have v = 14, which in binary is 1110, then to get v-1, first flip the zero to the right of least significant 1 to '1', which gives us 1111 & then flip the least significant 1 itself to a zero, giving us 1101.

Now, we know that &ing the number 'v' and 'v-1' will preserve all the 1's to the left of the least significant 1 and the rest of the numbers will get '&ded' to zeroes therefore preserving 1 less than the number of bits actually set in the number, i.e. in the case of 1110, v & v-1 = 1100 which has 1 less bit set than its predecessor. This process happens for as many '1's there are as the number of bits set, the count of which we store in the count variable.
Arun Balachandran
  • 1