Find position of the only set bit | GeeksforGeeks

Find position of the only set bit | GeeksforGeeks
Given a number having only one '1′ and all other '0′s in its binary representation, find position of the only set bit.

The idea is to one by one right shift the set bit of given number ‘n’ until ‘n’ becomes 0. Count how many times we shifted to make ‘n’ zero. The final count is position of the set bit.

int findPosition(unsigned n)

{

    if (!isPowerOfTwo(n))

        return -1;

    unsigned count = 0;

    // One by one move the only set bit to right till it reaches end

    while (n)

    {

        n = n >> 1;

        // increment count of shifts

        ++count;

    }

    return count;

}

Start from rightmost bit and one by one check value of every bit. 

// A utility function to check whether n is power of 2 or not. See http://goo.gl/17Arj

int isPowerOfTwo(unsigned n)

{  return n && (! (n & (n-1)) ); }

// Returns position of the only set bit in 'n'

int findPosition(unsigned n)

{

    if (!isPowerOfTwo(n))

        return -1;

    unsigned i = 1, pos = 1;

    // Iterate through bits of n till we find a set bit

    // i&n will be non-zero only when 'i' and 'n' have a set bit

    // at same position

    while (!(i & n))

    {

        // Unset current bit and set the next bit in 'i'

        i = i << 1;

        // increment position

        ++pos;

    }

    return pos;

}

We can also use log base 2 to find the position. 

unsigned int Log2n(unsigned int n)

{

   return (n > 1)? 1 + Log2n(n/2): 0;

}

int findPosition(unsigned n)

{

    if (!isPowerOfTwo(n))

        return -1;

    return Log2n(n) + 1;

}

Read full article from Find position of the only set bit | GeeksforGeeks