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

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
Performance Chart
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

Download The full source code including a test program is available for download.

References http://graphics.stanford.edu/~seander/bithacks.html

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index