Counting bits in a int - why does this code work?

I was trying to learn more about bits, and I came across this example.

How does this code work to count the bits? (My C is very rusty, by the way).

开发者_开发知识库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; v >>= 1)
{
  c += v & 1;
}

v & 1 is 1 if the lowest bit in v is set, and 0 if it's not.

The loop keeps dividing shifting the bits of vright by 1 place each iteration, and thus the lowest bit of v loops over each of the bits in the original v (as each one gets to the 1's place before "falling off" the fractional end).

Thus, it loops over each bit and adds 1 to c if it's set, and adds 0 if it's not, thus totaling the set bits in the original v.

For example, with a starting v of 1011:

1. 1011 & 1 = 1, so c is incremented to 1.
2. Then 1011 is shifted to become 101.
3. 101 & 1 = 1, so c is incremented to 2.
4. 101 is shifted to become 10.
5. 10 & 1 = 0, so c isn't incremented and remains 2.
6. 10 is shifted to become 1.
7. 1 & 1 = 1, so c is incremented to 3.
8. 1 is shifted to become 0 (because the last bit fell off the fractional end).
9. Since the condition of the for loop is just v, and v is now 0, which is a false value, the loop halts.

End result, c = 3, as we desire.

v >>= 1 will keep shifting the least significant bit off until v is all zeros. so we Don't stop until we've counted them all. v&1 tests if the bit we are about to shift off is a 1, so we make sure to count it before we shift it off.

v & basically extracts the least significant bit of v -- it's 1 if that bit is set, 0 if not. Every iteration through the loop it shifts v 1 place to the right. And within each iteration, it adds the result of that v & test to a counter c. So every bit that's set means 1 gets added; every clear bit 0 is added.

Basically, you are comparing 1 bit of v to the value 1, and you know the truth table for AND.

• 1 & 0 = 0
• 0 & 1 = 0
• 1 & 1 = 1

So if the bit from v is 1, it will produce 1 if ANDed with 1. Then shift v by 1 bit and continue.