Can someone explains why this works to count set bits in an unsigned integer?

Question

I saw this code called "Counting bits set, Brian Kernighan's way". I am puzzled as to how "bitwise and'ing" an integer with its decrement works to count set bits, can someone explain this?

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
}

Answer 1

Walkthrough

Let's walk through the loop with an example : let's set v = 42 which is 0010 1010 in binary.

• First iteration: c=0, v=42 (0010 1010). Now v-1 is 41 which is 0010 1001 in binary. Let's compute v & v-1:

     0010 1010
   & 0010 1001
     .........
     0010 1000
  

  Now v&v-1's value is 0010 1000 in binary or 40 in decimal. This value is stored into v.

• Second iteration : c=1, v=40 (0010 1000). Now v-1 is 39 which is 0010 0111 in binary. Let's compute v & v-1:

     0010 1000
   & 0010 0111
     .........
     0010 0000
  

  Now v&v-1's value is 0010 0000 which is 32 in decimal. This value is stored into v.

• Third iteration :c=2, v=32 (0010 0000). Now v-1 is 31 which is 0001 1111 in binary. Let's compute v & v-1:

     0010 0000
   & 0001 1111
     .........
     0000 0000
  

  Now v&v-1's value is 0.

• Fourth iteration : c=3, v=0. The loop terminates. c contains 3 which is the number of bits set in 42.

Why it works

You can see that the binary representation of v-1 sets the least significant bit or LSB (i.e. the rightmost bit that is a 1) from 1 to 0 and all the bits right of the LSB from 0 to 1.

When you do a bitwise AND between v and v-1, the bits left from the LSB are the same in v and v-1 so the bitwise AND will leave them unchanged. All bits right of the LSB (including the LSB itself) are different and so the resulting bits will be 0.

In our original example of v=42 (0010 1010) the LSB is the second bit from the right. You can see that v-1 has the same bits as 42 except the last two : the 0 became a 1 and the 1 became a 0.

Similarly for v=40 (0010 1000) the LSB is the fourth bit from the right. When computing v-1 (0010 0111) you can see that the left four bits remain unchanged while the right four bits became inverted (zeroes became ones and ones became zeroes).

The effect of v = v & v-1 is therefore to set the least significant bit of v to 0 and leave the rest unchanged. When all bits have been cleared this way, v is 0 and we have counted all bits.