-1

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;
}
Greg
  • 45,306
  • 89
  • 231
  • 297
  • This is not a code review platform. Please do that in the code review section. There are very good and more efficient solutions for counting bits in other questions, e.g. here: http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer – Holger Bille Apr 07 '17 at 06:14

4 Answers4

9

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.

Amber
  • 507,862
  • 82
  • 626
  • 550
2

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.

stew
  • 11,276
  • 36
  • 49
1

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.

Edmund
  • 10,533
  • 3
  • 39
  • 57
1

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.

JoshD
  • 12,490
  • 3
  • 42
  • 53
wkl
  • 77,184
  • 16
  • 165
  • 176