Removing lowest order bit

Question

Given a binary number, what is the fastest way of removing the lowest order bit?

01001001010 -> 01001001000

It would be used in code to iterate over the bits of a variable. Pseudo-code follows.

while(bits != 0){
  index = getIndexOfLowestOrderBit(bits);
  doSomething(index);
  removeLowestOrderBit(bits);
}

The possible languages I'm considering using are C and Java.

Answer 1

This is what I've got so far, I'm wondering if anyone can beat this.

bits &= bits-1

Answer 2

You can find the lowest set bit using x & (~x + 1). Example:

    x: 01101100
 ~x+1: 10010100
       --------
       00000100

Clearing the lowest set bit then becomes x & ~(x & (~x + 1)):

          x: 01101100
~(x&(~x+1)): 11111011
             --------
             01101000

Or x & (x - 1) works just as well and is easier to read.

Answer 3

You don't want to remove the lowest order bit. You want to ZERO the lowest order SET bit.

Once you know the index, you just do 2^index and an exclusive or.

Answer 4

Uh ... In your example, you already know the bit's index. Then it's easy:

bits &= ~(1 << index);

This will mask off the bit whose index is index, regardless of its position in the value (highest, lowest, or in-between). Come to think of it, you can of course use the fact that you know the bit is already set, and use an XOR to knock it clear again:

bits ^= (1 << index);

That saves the inversion, which is probably one machine instruction.

If you instead want to mask off the lowest set bit, without knowing its index, the trick is:

bits &= (bits - 1);

See here for instance.

Answer 5

The ever-useful Bit Twiddling Hacks has some algorithms for counting zero bits - that will help you implement your getIndexOfLowestOrderBit function.

Once you know the position of the required bit, flipping it to zero is pretty straightforward, e.g. given a bit position, create mask and invert it, then AND this mask against the original value

result = original & ~(1 << pos);

Answer 6

I don't know if this is comparable fast, but I think it works:

int data = 0x44A;
int temp;
int mask;

if(data != 0) {   // if not there is no bit set
   temp = data;
   mask = 1;
   while((temp&1) == 0) {
      mask <<= 1;
      temp >>= 1;
   }
   mask = ~mask;
   data &= mask;
}