Today I needed a simple algorithm for checking if a number is a power of 2.
The algorithm needs to be:
- Simple
- Correct for any
ulongvalue.
I came up with this simple algorithm:
private bool IsPowerOfTwo(ulong number)
{
if (number == 0)
return false;
for (ulong power = 1; power > 0; power = power << 1)
{
// this for loop used shifting for powers of 2, meaning
// that the value will become 0 after the last shift
// (from binary 1000...0000 to 0000...0000) then, the for
// loop will break out
if (power == number)
return true;
if (power > number)
return false;
}
return false;
}
But then I thought, how about checking if log 2 x is an exactly round number? But when I checked for 2^63+1, Math.Log returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in double s and not in exact numbers:
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
This returned true for the given wrong value: 9223372036854775809 .
Does anyone have any suggestion for a better algorithm?
Source: Tips4all, CCNA FINAL EXAM
There's a simple trick for this problem:
ReplyDeletebool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
Discovery of how and why this works is left as an exercise for the reader, as well as consideration of an obvious edge case.
Editor's Note
For completeness, zero is not a power of two. If you want to take into account that edge case, here's how:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
Editor's Note by user JonH
I figured instead of discovering why this works, why not explain it to those who do not understand.
First and foremost the bitwise binary & operator from MSDN definition:
Binary & operators are predefined for the integral types and bool. For
integral types, & computes the logical bitwise AND of its operands.
For bool operands, & computes the logical AND of its operands; that
is, the result is true if and only if both its operands are true.
Now let's take a look at how this all plays out:
The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:
bool b = IsPowerOfTwo(4)
Now we replace each occurrence of x with 4:
return (4 != 0) && ((4 & (4-1)) == 0);
Well we already know that 4 != 0 evals to true, so far so good. But what about:
((4 & (4-1)) == 0)
This translates to this of course:
((4 & 3) == 0)
But what exactly is 4&3
The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers. So we have:
100=4
011=3
Imagine these values being stacked up much like elementary addition. The & operator says that if both values are = 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, and 0 & 1 = 0. So we do the math:
100
011
----
000
Cool we are getting somewhere...the end result is simply 0. So we go back and look at what our return statement now translates to:
return (4 != 0) && ((4 & 3) == 0);
Which translates now to:
return true && (0 == 0);
Which translates to:
return true && true;
We all know true && true is simply true, and this shows that for our example, 4 is a power of 2. I hope this helps!
return (i & -i) == i
ReplyDeleteI wrote an article about this recently at http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/. It covers bit counting, how to use logarithms correctly, the classic "x && !(x & (x - 1))" check, and others.
ReplyDeletebool IsPowerOfTwo(ulong x)
ReplyDelete{
return x > 0 && (x & (x - 1)) == 0;
}
After posting the question I thought of the following solution:
ReplyDeleteWe need to check if exactly one of the binary digits is one. So we simply shift the number right one digit at a time, and return true if it equals 1. If at any point we come by an odd number ((number & 1) == 1), we know the result is false. This proved (using a benchmark) slightly faster than the original method for (large) true values and much faster for false or small values.
private static bool IsPowerOfTwo(ulong number)
{
while (number != 0)
{
if (number == 1)
return true;
if ((number & 1) == 1)
// number is an odd number and not 1 - so it's not a power of two.
return false;
number = number >> 1;
}
return false;
}
Of course, Greg's solution is much better.
bool IsPowerOfTwo( ulong number )
ReplyDelete{
if( i == 0 ) return false;
ulong minus1 = i -1;
return (i|minus1) == (i^minus1);
}
Here's a simple c++ solution:
ReplyDeletebool IsPowerOfTwo( unsigned int i )
{
return std::bitset<32>(i).count() == 1;
}
bool isPow2 = ((x & ~(x-1))==x)? x : 0;
ReplyDeleteFind if the given number is a power of 2.
ReplyDelete#include <math.h>
int main(void)
{
int n,logval,powval;
printf("Enter a number to find whether it is s power of 2\n");
scanf("%d",&n);
logval=log(n)/log(2);
powval=pow(2,logval);
if(powval==n)
printf("The number is a power of 2");
else
printf("The number is not a power of 2");
getch();
return 0;
}
private static bool IsPowerOfTwo(ulong x)
ReplyDelete{
var l = Math.Log(x, 2);
return (l == Math.Floor(l));
}
bool isPowerOfTwo(int x_)
ReplyDelete{
register int bitpos, bitpos2;
asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
return bitpos > 0 && bitpos == bitpos2;
}
A number is a power of 2 if it contains only 1 set bit. We can use this property and the generic function countSetBits to find if a number is power of 2 or not.
ReplyDeleteThis is a C++ program:
int countSetBits(int n)
{
int c = 0;
while(n)
{
c += 1;
n = n & (n-1);
}
return c;
}
bool isPowerOfTwo(int n)
{
return (countSetBits(n)==1);
}
int main()
{
int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
return 0;
}
We dont need to check explicitly for 0 being a Power of 2, as it returns False for 0 as well.
OUTPUT
Num:0 Set Bits:0 is power of two: 0
Num:1 Set Bits:1 is power of two: 1
Num:2 Set Bits:1 is power of two: 1
Num:3 Set Bits:2 is power of two: 0
Num:4 Set Bits:1 is power of two: 1
Num:5 Set Bits:2 is power of two: 0
Num:15 Set Bits:4 is power of two: 0
Num:16 Set Bits:1 is power of two: 1
Num:22 Set Bits:3 is power of two: 0
Num:32 Set Bits:1 is power of two: 1
Num:38 Set Bits:3 is power of two: 0
Num:64 Set Bits:1 is power of two: 1
Num:70 Set Bits:3 is power of two: 0