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.

  • This code should be written with a while loop, not a for.
    – AK_
    Dec 12, 2015 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.
    – user22815
    Dec 12, 2015 at 20:36

2 Answers 2


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.

  • Could include an example: 1101000 - 1 = 1100111. 1101000 & 1100111 = 1100000; notice the lowest 1 bit was changed to a 0.
    – user253751
    Dec 12, 2015 at 11:52
  • well explained.
    – OhadR
    Dec 5, 2016 at 15:06

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.