Example
Number 19, Binary Representation 010011
Answer Position of right most set bit 1
Here is an order of log(X) algorithm. We can conclude from 2's complement form that "a number can be converted to 2's complement form by complementing each bit from right most set bit". For example, -7 can be obtained in the following way (assuming 8 bit size)
8 = 00001000
-8 = 11111000
If we perform ANDing between x and -x we left with right most set bit. All this takes O(1) time. Now use binary search [ O(log(x)) ] to figure out which bit is set. Given below is code.
int getPosition(unsigned x)
{
// ASSUMPTION: x will not be zero
// left, right and mid position
int l = 0, r = 33, mid = 0;
// temp value
unsigned temp;
// Iterate till we find the bit position
while(l < r)
{
// ((r - l) >> 1) + l - Is more effective??
mid = (l + r) >> 1;
// Set the most possible significant bit
temp = (1 << (mid - 1));
if(temp == x)
{
break;
}
else if(temp < x)
{
// Bit is in the higher half
l = mid;
}
else
{
// Bit is in the lower half
r = mid;
}
}
// Return mid itself if bits
// are positioned from 1 to 32
return (mid-1);
}
int getRightMostSetBit(unsigned x)
{
// Return 0 if x is zero
int position = 0;
// Avoid multiple return statements
if(x != 0)
{
// Make the integer passes as least power of 2
// Call the position locator
position = getPosition(x & -(signed)x);
}
return position;
}
Source Heard from My Friend Venki
