Using C/C++, what is the fastest way to determine if an integer is a power of 2?

When dealing with powers of two, one must automatically think in terms of binary.

Given any power of 2, its binary equivalent would be 0 in all places except for 1 slot. For example;

Then we look at numbers 1 less than these powers of 2. And we get the following;

As you can see, any power of 2, let’s say x, and x – 1 does not share a single bit where they’re both 1. In other words, if we AND (bitwise operator) these 2 numbers together, we should get a 0.

If x were not a power of two, x – 1 would share a bit where they’re both 1.

Special Case

This method works in all cases, even negative values, except for one: x = 0. If the number is 0, getting the x – 1 will yield in all bits equal to 1. 0 & 1 would always result to 0. Therefore, we add a special case to check if x is non-zero.

Note that this method is endianness-independent since there are no bit shifts or bit streams.

Application

In OpenGL, it is highly advisable that the dimensions of a texture be a power of 2 in order to maximize the memory in the video card. If you load a NPOT (non-power of two) texture, the video card would 0-pad the image resulting in a waste of space. OpenGL uses an image compression algorithm that are designed to work with dimensions equal to a multiple of 4. See NPOT Textures.

Another application would be in Fast Fourier Transforms (FFT).The most common FFT algorithm requires a size of N = 2^k. See Cooley-Tukey FFT.