CODEWITHSUNDEEP
cbit-manipulationkernighan-and-ritchie
ggg123
ggg123

Reputation: 142

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

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
}

Upvotes: 2

Views: 440

Answers (3)

Alain Merigot
Alain Merigot

Reputation: 11557

Let A=an-1an-2...a1a0 be the number on which we want to count bits and k the index of the right most bit at one.

Hence A=an-1an-2...ak+1100...0=Ak+2k where Ak=an-1an-2...ak+1000...0

As 2k−1=000..0111..11, we have A-1=Ak+2k-1=an-1an-2...ak+1011...11

Now perform the bitwise & of A and A-1

an-1an-2...ak+1100...0 A
an-1an-2...ak+1011...1 A-1
an-1an-2...ak+1000...0 A&A-1=Ak

So A&A-1 is identical to A, except that its right most bit has been cleared, that proves the validity of the method.

Upvotes: 3

Louen
Louen

Reputation: 3677

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.

Upvotes: 5

Doug Currie
Doug Currie

Reputation: 41200

Each time though the loop one bit is counted, and one bit is cleared (set to zero).

How this works is: when you subtract one from a number you change the least significant one bit to a zero, and the even less significant bits to one -- though that doesn't matter. It doesn't matter because they are zero in the values you're decrementing, so they will be zero after the and-operation anyway.

XXX1 => XXX0
XX10 => XX01
X100 => X011
etc.

Upvotes: 4

Related Questions