Find Position of the only Set Bit

Problem: You are given a number having only one “1″ its binary representation,. You have to find position of it?

Solution:

First of all we will check if number is power of two, Beacuse then only its binary represenattion will contain only one “1″.

After that, start from rightmost bit and one by one check value of every bit. Following are steps:
1) Initialize two variables; i = 1 (for looping) and pos = 1 (to find position of set bit)
2) Inside loop, do bitwise AND of i and number ‘N’. If value of this operation is true, then “pos” bit is set, so break the loop and return position. Otherwise, increment “pos” by 1 and left shift i by 1 and repeat the procedure.

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;

    while (!(i & n))
    {
        // Unset current bit and set the next bit in 'i'
        i = i << 1;
        ++pos;
    }
 
    return pos;
}

4 Thoughts on “Find Position of the only Set Bit

  1. Sunny bindal on May 27, 2015 at 9:15 am said:

    Cant we use rightshift operation till the number becomes zero then number of right shift operation performed is the position of 1

  2. vishwanath on December 7, 2015 at 12:56 am said:

    int main()
    {
    int number=64;
    int temp=number;
    int count=0;
    int position=0;

    do{
    if((temp&1) && (count++==1)){
    printf(“number have more then one bit set\n”);
    return 0;
    }
    position++;
    }while(temp>>=1);
    printf(“number is having one bit set position=%d \n”,position);

    return 0;
    }

  3. Pratyush on April 12, 2016 at 11:07 pm said:

    #include

    using namespace std;

    int main()
    {
    int count=0;
    int n;
    cin>>n;
    if ((n&(n-1))==0)
    {
    n=n|(n-1);

    while(n)
    {
    n=n&(n-1);
    count++;
    }
    cout<<"Bit present at"<<" "<<count<<" "<<"position"<<endl;
    }
    else
    cout<<"more than one '1's present"<<endl;

    return 0;
    }

  4. #include
    int main()
    {
    int x=8,i;
    for(i=0;x!=0;x=x>>1,i++);
    printf(“position=%dth”,i);
    return 0;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation