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 if '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?

Answer 1

(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 2

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.