Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: C/C++ hw question!

  1. Jan 30, 2006 #1

    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!!!

    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.
  2. jcsd
  3. Jan 30, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    - Warren
  4. Jan 30, 2006 #3


    User Avatar

    Staff: Mentor

    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?
  5. Jan 30, 2006 #4
    & 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook