[Programming] #4 Finding the smallest bit in a value

More bit magic!

This time we are going to find the smallest bit in a value.

I encountered this problem while implementing uniform grid spatial partition back in school. Basically after some calculations, I would get a resultant value that contains all collisions that need to be resolved encoded in each bit of the value (each bit was representing a part of the world). So I needed a fast way to obtain each and every bit, calculate what I need to calculate, and proceed to the next bit. The problem is getting the bits one by one.

This requires a function that helps me extract the last bit of a value.
If I pass in the number '5' which is 0101, I would want to get 0001.
If I pass in the number '6' which is 0110, I would want to get 0010.

It's pretty nifty because the naive way involves an ugly loop:

int getLastBitNaive( int value ) {
    while ( (value & 1) == 0 ) {
        value = value >> 1;
    }
    return value;
} 

This means for every n bit turned on I would have to loop n times. There are ways to optimize this to make it loop only once of course (by 'remembering' the last position it looped to), but there is a way to do everything without a loop.

Tadah:

int getLastBit( int value ) {
    return value &= ~(value - 1);
}

Basically it's doing an AND operation on it's Two's Complement.

Sadly, returning the positional value (like 0010 = 2, 0100 = 3, etc) still requires either a log2 function or a lookup table. Languages with access to assembly has access to that but that's for another post.