Showing posts with label Google CodeJam. Show all posts
Showing posts with label Google CodeJam. Show all posts

Wednesday, August 15, 2012

Write an algorothm to find the position of rightmost set bit in binary representation of number

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