5

I can see in this tutorial on bit manipulation, under the heading "Extracting every last bit", that -

Suppose we wish to find the lowest set bit of x (which is known to be non-zero). If we subtract 1 from x then this bit is cleared, but all the other one bits in x remain set.

I don't understand how this statement is true.

If we take x = 110, subtracting 1 would give 101.

Here, the lowest set bit is not cleared. Can anyone tell me how I'm approaching this problem in a wrong way?

  • 1
    The lowest set bit in 110 is the middle one. In 101, the middle bit is cleared. – Greg Hewgill Nov 28 '13 at 3:03
  • The accepted answer is correct: think about it. How does 2s complement work? – user22815 Nov 28 '13 at 6:40
6

After subtracting 1, you need to & the two values. e.g.

int bitremoved = x & (x-1);

In your example you end up with binary 100.

  • But binary 100 does not meet the second part of the description: "but all the other one bits in x remain set." – SailsMan63 Nov 28 '13 at 3:02
  • 1
    @SailsMan63 its quite possible that the tutorial quoted was... less than complete/ideal (or not fully quoted). The solution of x & (x-1) is the correct approach to clearing the lowest bit. – user40980 Nov 28 '13 at 3:17
  • Read this Intel Haswell new instructions, under BLSR. If this is not correct I will vote to close. – rwong Nov 28 '13 at 3:39
  • Turns out that it wasn't fully quoted, and for that matter wasn't the proper instructions for the operation. The full tutorial is from TopCoder Algorithim Tutorials - A bit of fun: fun with bits (the tutorial is correct, the interpretation of it in this question is incorrect). – user40980 Nov 28 '13 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.