How to check if a number is a power of 2

Question

Today I needed a simple algorithm for checking if a number is a power of 2.

The algorithm needs to be:

1. Simple
2. 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 log2x 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 doubles 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?

Answer 1

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);
}

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

return (i & -i) == i

Answer 6

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

Answer 7

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

Answer 8

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;
}

Answer 9

bool IsPowerOfTwo( ulong number )
{
   if( i == 0 ) return false;
   ulong minus1 = i -1;
   return (i|minus1) == (i^minus1);
}

Answer 10

Here's a simple c++ solution:

bool IsPowerOfTwo( unsigned int i )
{
   return std::bitset<32>(i).count() == 1;
}

Answer 11

bool isPow2 = ((x & ~(x-1))==x)? x : 0;