
Is power of two 

Code 
01: bool isPowerOfTwo(unsigned int x)
bits.stephanbrumme.com

Explanation 
The binary representation of a poweroftwo 2^{y} is a 1 followed only by 0s. In such a case, x − 1 generates a binary number where the 1s turn into 0s and the former 0s turn into 1s. For example, 8 = 1000b and 8 − 1 = 7 = 0111b. If x and x − 1 are binary ANDed then the result is only 0 if x is a power of two (line 3). 
Restrictions 
• the algorithm returns true for x = 0 and x = 1, i.e. they are considered to be a power of two 
These ads help me to pay my server bills 

Performance 
• constant time, data independent + Intel® Pentium™ D: • isPowerOfTwo/VC: ≈ 5.5 cycles per number • isPowerOfTwo/GCC: ≈ 11 cycles per number + Intel® Core™ 2: • isPowerOfTwo/VC: ≈ 2.25 cycles per number • isPowerOfTwo/GCC: ≈ 4 cycles per number + Intel® Core™ i7: • isPowerOfTwo/VC: ≈ 2.25 cycles per number • isPowerOfTwo/GCC: ≈ 4 cycles per number CPU cycles (full optimization, lower values are better) 
Assembler Output  
Download  The full source code including a test program is available for download. 
References 
http://graphics.stanford.edu/~seander/bithacks.html 
More Twiddled Bits 
... or go to the index 