6

Possible Duplicate:
n & (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 significance of num & (num-1)? How does it work?

Community
  • 1
  • 1
user1526667
  • 227
  • 2
  • 3
  • 11

3 Answers3

7
num &= num - 1;

clears the least significant bit set in num.

This algorithm counts the bits set by clearing them and incrementing a counter until they're all gone.

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

Subtracting in binary works just as the process we were all taught in decimal as children. You work from right (least significant) to left, simply subtracting individual digits when possible, and "borrowing" from the next digit when necessary.

When subtracting 1 from a binary number ending in a set of zeros, this "borrowing" and subtracting turns all the zeros in lower positions than the rightmost 1 to 1's and turns the rightmost 1 to a zero (because it was borrowed).

Then applying the & operator leaves all the lesser digits zero because they're zero in num, and sets the least significant bit of num to zero because it's zero in num-1.

Both of these operations leave the more significant digits unchanged.

Here's a good list of bit twiddling hacks including this one, which is due to Brian Kernighan.

Don Roby
  • 40,677
  • 6
  • 91
  • 113
7

Here's a more detailed (but not very well written!) answer.

There are two cases: either the least significant bit is set, then "num-1" unsets it. Or it's not set, then num-1 turns all trailing zeroes into 1, and the least significant 1 to a 0, the rest of the bits are not changed. When you "and", all unchanged bits are the same, the least significant 1 which is anded with a 0 turns into a 0 and the others remaining bits are zeroes. This is illustrated here:

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

I would point out that there is often an assembly operation to count the number of ones in a single cycle. The operation is called "popcount" and for instance in GCC, it can be accessed using "__builtin_popcount", see this link for details.

another.anon.coward
  • 11,087
  • 1
  • 32
  • 38
Jérémie
  • 1,353
  • 9
  • 19
  • I edited the default description for adding the link. Hope that is ok! +1 for the info about gcc – another.anon.coward Aug 04 '12 at 17:45
  • Yep thanks :) By the way, when I said "Here's a more detailed answer", it was when Don Roby's answer was only three lines. He has since (very well) expanded on his original answer. – Jérémie Aug 04 '12 at 17:59
  • 1
    Visual Studio users can also take advantage of the __POPCNT__ instruction via the [__popcnt compiler intrinsics](http://msdn.microsoft.com/en-us/library/bb385231.aspx). – Blastfurnace Aug 04 '12 at 19:35
  • @Blastfurnace: thank you! I was just wondering what the equivalent on VS was! – Jérémie Aug 04 '12 at 21:13
-1

The algorithm operates like pump, moving bits effectively to right in the "num" variable. The line 

num &= num - 1;

is where the work is done, there's an assignment and boolean AND operation going on at the same time. It's all about bit arithmetic.

Pom

Pompair
  • 7,083
  • 11
  • 60
  • 69