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

Question

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;
}

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

Amber · Accepted Answer · 2010-10-12T02:19:23.303

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:

1011 & 1 = 1, so c is incremented to 1.
Then 1011 is shifted to become 101.
101 & 1 = 1, so c is incremented to 2.
101 is shifted to become 10.
10 & 1 = 0, so c isn't incremented and remains 2.
10 is shifted to become 1.
1 & 1 = 1, so c is incremented to 3.
1 is shifted to become 0 (because the last bit fell off the fractional end).
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.

I like your answer the best :-) – Travis Gockel Oct 12 '10 at 02:13 — Travis Gockel, Oct 12 '10 at 02:13

score 2 · Answer 2 · answered Oct 12 '10 at 02:13

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.

answered Oct 12 '10 at 02:13

stew

11,276
36
49

score 1 · Answer 3 · answered Oct 12 '10 at 02:13

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.

score 1 · Answer 4 · edited Oct 12 '10 at 02:15

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.

edited Oct 12 '10 at 02:15

JoshD

12,490
3
42
53

answered Oct 12 '10 at 02:13

wkl

77,184
16
165
176

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

4 Answers4