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.
This is what I've got so far, I'm wondering if anyone can beat this.
bits &= bits-1
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With