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)*

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?