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

  • Context: Comp Sci 
  • Thread starter Thread starter andytran
  • Start date Start date
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
3 replies · 3K views
andytran
Messages
41
Reaction score
0
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.
 
Physics news on Phys.org
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?
 
chroot said:
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.