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