A number is a power of 2 if it has exactly one bit set. For example, , , .
Here's the trick: a number is a power of 2 if and only if and .
Why? If has exactly one bit set, then flips that bit and all bits to the right. ANDing them gives 0. But if has multiple bits set, only clears the rightmost one, leaving others, so the result is non-zero. This check runs in time.