Using C/C++, what is the fastest way to determine if an integer is a power of 2?
1 2 3 4 5 6 7 |
int x = /* some value */; if (/* is x a power of 2 ?*/) { /* x is a power of 2 */ } else { /* x is not 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

256 in Binary

4096 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

255 in Binary

4095 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.
1 2 3 4 5 6 7 |
int x = /* some value */; if ( !(x & (x - 1)) ) { /* x is a power of 2 */ } else { /* x is not a power of 2 */ } |
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.
1 2 3 4 5 6 7 |
int x = /* some value */; if ( x && !(x & (x - 1)) ) { /* x is a power of 2 */ } else { /* x is not a power of 2 */ } |
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.