Powers of two

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)

6 Comments

  1. Let’s generalize this to a standard interview question: how many bits does a given unsigned integer have set?

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

  3. 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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s