Power of Two

A power of two has exactly one bit set: $1, 2, 4, 8, 16, ...$

Method: n & (n - 1) clears the lowest set bit. If the result is $0$, there was only one bit.

function isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

Example:

• $n = 8 = 1000_2$. $n - 1 = 0111_2$. $1000 \& 0111 = 0000$. True.
• $n = 6 = 0110_2$. $n - 1 = 0101_2$. $0110 \& 0101 = 0100 \neq 0$. False.

Note: Check $n > 0$ because $0$ is not a power of two but $0 \& (-1) = 0$.

Time: $O(1)$.