What does the bitwise AND operator & do in this code snippet?

Question

Please help to solve this problem and explain the logic. I don't know how the & operator is working here.

void main() {
   int a = -1;
   static int count;
   while (a) {
      count++;
      a &= a - 1;
   }
   printf("%d", count);
}

Looks an awful lot like: http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer/109036#109036 — sarnold, Mar 04 '11 at 10:06
@Andrew It is good programming practice to initialize it, but strictly speaking it isn't required for the program to work as expected. — Lundin, Mar 04 '11 at 10:17

Tobias Wärre · Answer 1 · 2011-03-04T11:06:03.147

5

If you are referring to

a&=a-1;

then it is a bitwise and operation of a and a-1 copied into a afterwards.

Edit: As copied from Tadeusz A. Kadłubowski in the comment:

a = a & (a-1);

edited Mar 04 '11 at 11:06

answered Mar 04 '11 at 10:04

Tobias Wärre

2

It pretty much means the same as `a = a & (a-1);` – Tadeusz A. Kadłubowski Mar 04 '11 at 10:06
@Tadeusz copied and attributed and upvoted your comment, thnx – Tobias Wärre Mar 04 '11 at 11:06
it might be important to notice that for some values of `a` this expressions might not be equivalent. Consider `#define a (++b)` for some other variable `b`. A minor clarification just in case the OP was a CS student learning intricacies of C. – Tadeusz A. Kadłubowski Mar 04 '11 at 11:43
1

When using `#define` all bets are off. You can't be sure anything means anything. :-) – Zano Mar 04 '11 at 12:39

score 3 · Answer 2 · answered Mar 04 '11 at 10:06

The expression a&=a-1; clears the least significant bit (rightmost 1) of a. The code counts the number of bits in a (-1 in this case).

Starting from

a = -1 ; // 11111111 11111111 11111111 11111111 32bits signed integer

The code outputs 32 on an 32 bit integer configuration.

score 2 · Answer 3 · answered Mar 04 '11 at 10:06

The operation

a&=a-1;

which is same as:

a = a & a-1;

clears the least significant bit of a.

So your program effectively is calculating the number of bits set in a.

And since count is declared as static it will automatically initialized to 0.

score 0 · Answer 4 · answered Mar 04 '11 at 10:06

0

you have count uninitialized

should be

static int count=0;

answered Mar 04 '11 at 10:06

fazo

The C standard guarantees that static variables are initialized to zero if the programmer didn't init them explicitly. Regardless, good practice is that the program either initialize them explicitly or assign a value to them before using them. – Lundin Mar 04 '11 at 10:20
I tried to contradict you on this above and realised my mistake after looking at the C specification. The relevant portion is 6.7.8.10 if anyone else happens to be looking. – James Greenhalgh Mar 04 '11 at 10:52

4 Answers4