Sunday, July 21, 2013

Finding Position Of Only Set Bit.....Of a given No.

Given a number having only one ’1′ and all other ’0′s in its binary representation, find position of the only set bit:
Ex- Input 2,4,8,9
   Output 2,3,4, -1 Respectively.

//I did it by using Binary Search,Because i couldn't find better approach than this.... Here is my program. Complexity is logk.

#include<iostream>
using namespace std;
int PowerofTwo(long int n)
{
return n&&(!(n&n-1));
}
int setBit(long int n)
{  
    if(!PowerofTwo(n))
     return -1;
    long int mid,left,right;
     left=0,right=31;
long int k=1;
int temp=1;
while(k)
{   mid=(left+right)/2;
   k=1<<mid;
if(k<n)
{
left=mid;
}
else if(k>n)
{
right=mid;
}
   else
   {
   return mid+1;
   }
}

}
int main(void)
{  long int N=32768;   // Input data.....change it for check on different numbers
cout<<setBit(N)<<endl;
return 0;
}
// Happy Coding
Suggest me if there is another better approach.

No comments:

Post a Comment