Low bit deletion

Question

Given a binary number, what's the fastest way to remove a low order bit?

01001001010 → 01001001000

It will be used in the code to iterate over the bits of the variable. The following is pseudo code.

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

Possible languages ​​that I am considering are C and Java.

Answer 1

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

 bits &= ~(1 << index); 

This will close the bit whose index is index , regardless of its position in the value (highest, lowest, or intermediate). Think about it, you can, of course, use the fact that you know that the bit is already set, and use XOR to knock it again:

 bits ^= (1 << index); 

This saves the inverse, which is probably one machine instruction.

If you want to hide the lowest bit without knowing its index, the trick:

 bits &= (bits - 1); 

See here .

Answer 2

This is what I still have, I wonder if anyone can win.

 bits &= bits-1 

Answer 3

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

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

The low-order bit clearing is set as follows: 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 4

The ever-useful Bit Twiddling Hacks has several algorithms for counting zero bits - this will help you implement the getIndexOfLowestOrderBit function.

Once you know the position of the required bit, flipping it to zero is pretty simple, for example. set the bit of the position, create a mask and invert it, then And this mask against the original value

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

Answer 5

You do not want to remove the lower order bit. You want the ZERO low order bit SET.

Once you recognize the index, you simply make the 2 ^ index and the exclusive or.

Answer 6

I don't know how comparable this is 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; } 

Answer 7

In Java, use Integer.lowestOneBit ().