For a positive integer n, what does n & (n - 1) == 0 test?
Options
- n is an even number
- n is a power of two (Correct option)
- n is a prime number
- n is an odd number
Answer
n is a power of two
Why
In binary, a power of two has exactly one 1 bit: 8 = 1000. Subtracting 1 flips that bit and turns all lower bits into 1: 7 = 0111.
The AND (&) of 1000 and 0111 is 0000. Any number with two or more 1 bits keeps at least one, so the result is not 0.
The same trick n & (n - 1) removes the lowest 1 bit, which helps count bits.
Remember
n & (n-1) == 0 → power of two.