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?

theharshest
  • 153
  • 1
  • 4

1 Answers1

7

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.

user949300
  • 8,679
  • 2
  • 26
  • 35
  • 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 03: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. –  Nov 28 '13 at 03:17
  • Read this [Intel Haswell new instructions](http://software.intel.com/en-us/blogs/2011/06/13/haswell-new-instruction-descriptions-now-available), under BLSR. If this is not correct I will vote to close. – rwong Nov 28 '13 at 03:39
  • 1
    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](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation) (the tutorial is correct, the interpretation of it in this question is incorrect). –  Nov 28 '13 at 04:03