Checking Power of Two

A number is a power of 2 if it has exactly one bit set. For example, $8 = 1000$, $16 = 10000$, $32 = 100000$.

Here's the trick: a number $n$ is a power of 2 if and only if $n > 0$ and $n \& (n-1) = 0$.

Why? If $n$ has exactly one bit set, then $n-1$ flips that bit and all bits to the right. ANDing them gives 0. But if $n$ has multiple bits set, $n \& (n-1)$ only clears the rightmost one, leaving others, so the result is non-zero. This check runs in $O(1)$ time.