Quick Links
Categories
Links
How to find whether the given number is a power of 2 in single a single step (without using loops) ?
Ok this is another often repeated question. But unlike the others, this has a legitimate solution.
Before I show you the code for this, I would like to explain a few things first. We are required to find if a number is a power of 2 in just one step. A number would be a power of two if there is exactly one bit that is equal to 1 in its bit pattern (even 1 is a power of 2. 2 raised to the power zero is 1). Now we could use the method that we used to count the number of bits that are 1 in a given number and check if it is equal to 1. However that approach needs many steps and hence wont suffice here.
In a number which is an exact power of 2 only 1 bit is set and all others are zero. Let the position of this 1 bit be MSB. Mathematics rules for binary numbers tells us that if we subtract 1 from this number then the number that we would get would have all its bit starting from the bit position MSB+1 set to 1. For example if the given number num is 8(00001000) then num-1 would be 7 (00000111). Now we notice that these two bit patterns dont have a 1 in the same bit position. Further observation suggests that if we bitwise and (&) both these numbers we would get zero.
It can also be proved that num&(num-1) would be zero only if num is a power of 2. I leave that as an exercise. If you are'nt able to figure out why it is so, then just leave a comment here and I will explain that part too.
Now here is the code:
bool isPowerOf2(int num){
return ((num>0) && (num & (num-1))==0);
}
return ((num>0) && (num & (num-1))==0);
}
CategoryPuzzles
Comments [Hide comments/form]
This solution fails for x = 0. It's also missing a return statement. A more correct solution might be:
bool isPowerOf2(int x)
{
return x > 0 && (x & (x - 1)) == 0;
}
bool isPowerOf2(int x)
{
return x > 0 && (x & (x - 1)) == 0;
}
-- byethost15.com (2006-11-08 10:19:59)
Thanks a lot for pointing that out. It was silly of me to have missed the return statement. Was a mistake.
-- PriyaSridharan
(2006-11-08 12:42:09)
can u please explain why sbtracting will always yield zero.. is it not possible with other general numbers.. im just using the brute force method tocheck this .. but i would be happy if i get a generalised solution
-- 59.92.192.214 (2007-02-24 23:42:04)
Hi,
I tried doing the same using the log function.....I think the program works correctly.....
int main()
{
cout<<"enter the number";
double num;
cin>>num;
int a =log(num)/log(2.0);
double b = log(num)/log(2.0);
if(a==b)
{
cout<<"Number is a power of 2";
}
else
cout<<"Number is NOT a power of 2";
return 0;
}
I tried doing the same using the log function.....I think the program works correctly.....
int main()
{
cout<<"enter the number";
double num;
cin>>num;
int a =log(num)/log(2.0);
double b = log(num)/log(2.0);
if(a==b)
{
cout<<"Number is a power of 2";
}
else
cout<<"Number is NOT a power of 2";
return 0;
}
-- 216.87.118.11 (2009-03-25 01:54:41)
Page was generated in 0.0326 seconds