Determining if an Integer is a power of 2

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;

16 in Binary

16 in Binary

256 in Binary

256 in Binary

4096 in Binary

4096 in Binary

65536 in Binary

65536 in Binary

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

15 in Binary

15 in Binary

255 in Binary

255 in Binary

4095 in Binary

4095 in Binary

65535 in Binary

65535 in Binary

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 = 2k. See Cooley-Tukey FFT.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.