I was looking back through some C code I had written a while ago and found a concise little function for calculating whether an integer is a power of two. In general, there are two main ways to do this: either using its decimal or binary representation. The former approach can be more human-friendly, but generally less efficient; the latter approach is more machine-friendly, but tends to be more efficient. Since integers are stored as binary values in C (precisely how is dependent on the machine architecture), you can see why slicker methods are possible using binary. Essentially: an unsigned integer is a power of two if and only if it has exactly one 1 bit.
int isPowerOfTwo (unsigned int x)
{
return ((x != 0) && !(x & (x - 1)));
}
There are two halves to the expression: x != 0 and !(x & (x – 1)). The first half makes 0 a special case, since the second part of the expression only works correctly for positive numbers. The second half is true when x is a power of two and false when x is not. It turns out that this decrement and compare function is how the power-of-two check is implemented in malloc in the GNU C Library (glibc); let’s see how it works.
Let n be the position of the leftmost 1 bit in x. If x is a power of two, its lone 1 bit is in position n. This means x – 1 has a 0 in position n (recall how binary subtraction works: when subtracting 1 from x, the borrow propagates all the way from position n; bit n becomes 0 and all lower bits become 1). Now, since x has no 1 bits in common with x – 1, x & (x – 1) is 0, and !(x & (x – 1)) is true. Since subtraction borrows from the lowest 1 bit, when x is not a power of two this will be before position n, so it will not propagate. Now x and x – 1 have at least one 1 bit in common (at position n), so x & (x – 1) is non-zero, and !(x & (x – 1)) is false.
Here are some simple 8-bit unsigned integer examples to illustrate:
x |
x - 1 |
x & (x – 1) |
|---|---|---|
00000001 |
00000000 |
00000000 |
00000011 |
00000010 |
00000010 |
00000110 |
00000101 |
00000100 |
00001000 |
00000111 |
00000000 |
00001011 |
00001010 |
00001010 |
10000000 |
01111111 |
00000000 |
11111111 |
11111110 |
11111110 |
You can find more tips and tricks like this in the original HAKMEM (or updated HAKMEMC), as well as the book Hacker’s Delight by Henry S. Warren.
(A big thanks to Rick Regan and his in-depth Ten Ways to Check if an Integer Is a Power Of Two in C blog post)
Digital, Data & Policy 
Let’s generalize this to a standard interview question: how many bits does a given unsigned integer have set?
Oh, and then I meant to add some more, but clicked the button too early …
There are a variety of ways to calculate the number of bits set in the binary representation of an integer, each one of which having trade-offs: speed, space, source-code complexity and therefore maintainability being some obvious ones.
So as a potential candidate for superoptimization, I reckon this could provide some interesting results.
Indeed, I believe there is still a lot of potential in superoptimisation; I intend to write a summary blog post about it in the near future.
I also found two other resources that I forgot to add to the main article: Bit Twiddling Hacks and The Aggregate Magic Algorithms.
I believe that this is the exact implementation in malloc.c (reference here, along with nine other ways to compute whether an integer is a power of two: http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/)
Brilliant, thanks Chris.
And with a bit of recursion it works for signed integers:
int isPowerOfTwo(int x) {
return (((x > 0) && !(x & (x – 1))) ||
((x < 0) && isPowerOfTwo(-x)));
}
even though a negative number can't strictly be a power of 2! My C is very rusty but I think that's right.
I think if x < 0 and -x is a power of 2 XORing x with x + 1 gives 1, so could you use (x ^ (x + 1)) == 1?