How does this method count the number 1s in binary representation?

Question

Possible duplicate:
n and (n-1) what does this expression do?

Consider the following algorithm:

int count(int num) { int ones = 0; while(num) { ++ones; num &= num - 1; } return ones; } 

What is the meaning of num & (num-1) ? How it works?

Answer 1

 num &= num - 1; 

clears the least significant bit set to num.

This algorithm counts the bit set, clearing them and increasing the counter until everything disappears.

To understand why it clears the least significant bit, you need to think about what the decrement does for the bits, and, of course, understand what the & operation does.

Subtraction in binary works is exactly the same as the process we all taught in decimal as children. You work from the right (least significant) to the left, simply by subtracting the individual digits when possible, and “borrowing” from the next digit when necessary.

When subtracting 1 from a binary number ending with a set of zeros, this “borrowing” and subtraction turn all zeros into lower positions than the rightmost ones from 1 to 1, and turn the rightmost 1 to zero (because it was borrowed).

Then, applying the & operator leaves all smaller digits zero, because they are zero in num , and sets the least significant bit of num to zero, because it is zero in num-1 .

Both of these operations leave more significant numbers unchanged.

Here's a good list of bit-hacking hacks , including this one, which is driven by Brian Kernighan .

Answer 2

Here is a more detailed (but not very well written!) Answer.

There are two cases: either the least significant bit is set, then "num-1" disables it. Or it is not set, then num-1 turns all trailing zeros into 1, and the smallest value 1 - 0, the remaining bits do not change. When you are “and,” all the immutable bits are the same, the least significant 1, which has a value of 0, turns into 0, and the rest of the remaining bits are zeros. This is shown here:

 num = 1000110111[1]0000 num - 1 = 1000110111[0]1111 num & (num - 1) = 1000110111[0]0000 

I would like to point out that there is often a build operation to count the number of units per cycle. The operation is called "popcount" and, for example, in GCC, it can be obtained using "__builtin_popcount", see this link for details.

Answer 3

The algorithm works like a pump, effectively moving the bit to the right in the variable "num". Line

 num &= num - 1; 

where the work is performed, the task and the logical operation I are performed at the same time. Everything about bit arithmetic.

Pom