# Is power of two

Code
``` 01: bool isPowerOfTwo(unsigned int x) 02: { 03:   return ((x & (x - 1)) == 0); 04: } ``` bits.stephan-brumme.com

Explanation The binary representation of a power-of-two 2y 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

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
``` isPowerOfTwoVc: 01:   lea eax, [ecx-1] 02:   and eax, ecx 03:   neg eax 04:   sbb eax, eax 05:   inc eax isPowerOfTwoGcc: 01:   lea edx, [eax-1] 02:   test eax, edx 03:   sete al ``` bits.stephan-brumme.com