What's the simplest way to test whether a number is a power of 2 in C++?

Question

I need a function like this:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

Can anyone suggest how I could write this? Can you tell me a good web site where this sort of algorithm can be found?

Answer 1

A power of two will have just one bit set (for unsigned numbers). Something like

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Will work fine; one less than a power of two is all 1s in the less significant bits, so must AND to 0 bitwise.

As I was assuming unsigned numbers, the == 0 test (that I originally forgot, sorry) is adequate. You may want a > 0 test if you're using signed integers.

Answer 2

bool is_power_of_2(int i) {
    if ( i < 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

Answer 3

Powers of two in binary look like this:

1: 0001
2: 0010
4: 0100
8: 1000

Note that there is always exactly 1 bit set. The only exception is with a signed integer. e.g. An 8-bit signed integer with a value of -128 looks like:

10000000

So after checking that the number is greater than zero, we can use a clever little bit hack to test that one and only one bit is set.

bool is_power_of_2(int n) {
    return x > 0 && !(x & (x−1));
}

For more bit twiddling see here.

Answer 4

This isn't the fastest or shortest way, but I think it is very readable. So I would do something like this:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

This works since binary is based on powers of two. Any number with only one bit set must be a power of two.

Answer 5

"(n & (n - 1)) == 0" is best. However, note that it will incorrectly return true for n=0, so if that is possible, you will want to check for it explicitly.

http://www-graphics.stanford.edu/~seander/bithacks.html has a large collection of clever bit-twiddling algorithms, including this one.

Answer 6

Another way to go (maybe not fastest) is to determine if ln(x) / ln(2) is a whole number.

Answer 7

The very simplest way is to use the modulus operator; please note that it works for negative numbers as well. It's much simpler that bit shift math and it can be used in virtually any language. You asked for simple, here's simple.

bool is_power_of_2(int n)
{
    return (n % 2 == 0);
}

// You can always do it inline to; where x is an int
if (x%2==0) {
    // x is even
}
else {
    // x is odd
}