Comp Sci C/C++: Get Help on Unsigned Int x &= x-1;

[andytran]

Hi,

After hrs of googling still couldn't find the answer to my question. I'm hoping i get better luck positng it here. Any C/C++ out there please help!

1)
a) Given an unsigned int x, what does x &= x-1; do and why does it work?

I know what x &= x-1 does but to explain why does it work, i have no clue.

b) How can the statement in a) be used in a C++ program to count set bits (ones) in a given unsigned int x? What is the advantage over looping through all bit positions?


thanks in advance.

 

[chroot]

For starters, tell us what you already know. What does the & operator do in C?

- Warren

 

[berkeman]

Well for 2b), think about how you would loop through the bit positions. What are you going to change for each iteration of the loop? Also think about the different ways that you could do this counting problem, and whether this &= method would have advantages over other ways... BTW, I think there is at least one faster way to do the counting...can you think of it too?

 

[andytran]

For starters, tell us what you already know. What does the & operator do in C?

- Warren

& is the bitwise and operator, x &= x-1; is the same as x = x & (x-1);

if an unsigned int x = 5; then

5 = 101 in binary and (x-1) = 4 = 100

so after evaluating, x = 100 in binary or x = 4 in decimal.