Test for a Power of 2

A while ago I wanted to test whether a given number was a power of 2. The code was C++ and the number was a long.

bool is_power_of_2(long);

assert(is_power_of_2(8));

assert(!is_power_of_2(9));

I had a feeling that there was a simple way to test for this property – after all, it just means that it has exactly one bit set doesn’t it? But I couldn’t think of an elegant way to test for this. I ended up using a function that returned the number of bits set, like this:

int total_bits_set(long);

// return true iff ‘n’ is a power of 2

bool is_power_of_2(long n)

{

    return total_bits_set(n) == 1;

}

So that worked, and I moved on. But I knew it was not the simplest way, not least because my total_bits_set() code involved shifting, masking and indexing into a 256 byte table four times. (By the way, ‘iff’ means ‘if and only if’; also I realise now that this implementation incorrectly returns true for is_power_of_2(-2147483648).)

Some time later I was surfing around and I stumbled upon Sean Eron Anderson’s site Bit Twiddling Hacks. And there was the answer, which I implemented like so:

// return true iff ‘n’ is a power of 2

bool is_power_of_2(long n)

{

    return n > 0 && (n & (n - 1)) == 0;

}

That was the sort of clever trick I felt sure existed and meant I could throw away the total_bits_set() code. (This algorithm is described in Wikipedia.)

The code needs to work on gcc on various Unix platforms and on MSVC on Windows. On all these platforms a long is implemented as a 32-bit two’s complement value, which means the above trick will work for all of them. But I got to wonder about how portable this code really is. My copy of the ISO C++ standard says 

[...] the signed and unsigned integer types are collectively called integral types. [...] The representations of integral types shall define values by use of a pure binary numeration system. [Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types.]

3.9.1 Fundamental types, Paragraph 7, ISO/IEC 14882:1998

And in a footnote it elaborates on binary numeration systems

A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position. (Adapted from the American National Dictionary for Information Processing Systems.)

I believe the bit patterns for all three permitted integral type representations are the same for all represented values greater than zero. Therefore the above trick will work correctly on all compliant C++ compilers.

index of blog posts