How to check if a number is a power of 2

Wednesday, May 23, 2012

How to check if a number is a power of 2

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 ulong value.

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 ₂ 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

13 comments:

UserMay 23, 2012 at 2:58 AM
There's a simple trick for this problem:

bool 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!
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
Some sites that document and explain this and other bit twiddling hacks are:

http://www-graphics.stanford.edu/~seander/bithacks.html
(http://www-graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
http://bits.stephan-brumme.com/
(http://bits.stephan-brumme.com/isPowerOfTwo.html)

And the grandaddy of them, the book "Hacker's Delight" by Henry Warren, Jr.:

http://www.hackersdelight.org/

As Sean Anderson's page explains, the expression ((x & (x - 1)) == 0)incorrectly indicates that 0 is a power of 2. He suggests to use:

(!(x & (x - 1)) && x)

to correct that problem.
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
return (i & -i) == i
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
I 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.
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
bool IsPowerOfTwo(ulong x)
{
return x > 0 && (x & (x - 1)) == 0;
}
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
After posting the question I thought of the following solution:

We 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.
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
bool IsPowerOfTwo( ulong number )
{
if( i == 0 ) return false;
ulong minus1 = i -1;
return (i|minus1) == (i^minus1);
}
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
Here's a simple c++ solution:

bool IsPowerOfTwo( unsigned int i )
{
return std::bitset<32>(i).count() == 1;
}
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
bool isPow2 = ((x & ~(x-1))==x)? x : 0;
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
Find if the given number is a power of 2.

#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;
}
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
private static bool IsPowerOfTwo(ulong x)
{
var l = Math.Log(x, 2);
return (l == Math.Floor(l));
}
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
bool isPowerOfTwo(int x_)
{
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;
}
ReplyDelete
Replies
UserMay 23, 2012 at 2:58 AM
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.

This 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
ReplyDelete
Replies

Add comment

Ccna final exam - java, php, javascript, ios, cshap all in one

Wednesday, May 23, 2012

How to check if a number is a power of 2

13 comments:

Total Pageviews