I recently posted one the following solution. Question is, given an integer (other than 0) find right most set bit in that integer.
You can see the post in the following link
The solution is given below,
// Position of rightmost set bit
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)
7 = 00000111
-7 = 11111001
8 = 00001000
-8 = 11111000
5 = 00000101
-5 = 11111011
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;
}
If you find any errors, please let me know.
No comments:
Post a Comment