An interactive visualization of the Power of Two algorithm using bit manipulation. Watch how the n & (n-1) operation elegantly detects whether a number is a power of two by checking if exactly one bit is set.
Bit Manipulation LeetCode 231 ↗ Easyn, return true if it is a power of two. Otherwise, return false.n is a power of two if there exists an integer x such that n == 2x.fun isPowerOfTwo(n: Int): Boolean { if (n <= 0) { return false } return (n & (n - 1)) == 0 }
Powers of two have exactly one bit set in their binary representation. For example:
1 = 20 = 0001, 2 = 21 = 0010, 4 = 22 = 0100, 8 = 23 = 1000.
The clever trick is that n - 1 flips all bits after (and including) the rightmost set bit.
When we perform n & (n - 1), it clears the lowest set bit. If n is a power of two
(exactly one bit), the result is 0. If n has multiple bits set, the result is non-zero.
n <= 0. If true, return False (powers of two are positive).n - 1, which flips all bits from the rightmost 1 to the right.n & (n - 1):0: n had exactly one bit set → return Truen had multiple bits set → return False
For any power of two n = 2k, the binary representation is a single 1 followed by k zeros.
Subtracting 1 gives all 1s in the lower k positions. The bitwise AND of these two numbers is always 0:
8 = 1000, 7 = 0111 → 8 & 7 = 0000 ✓16 = 10000, 15 = 01111 → 16 & 15 = 00000 ✓
For non-powers of two, there are multiple set bits, so n & (n-1) only clears one bit and leaves others:
6 = 110, 5 = 101 → 6 & 5 = 100 (non-zero) ✗3 = 11, 2 = 10 → 3 & 2 = 10 (non-zero) ✗The algorithm performs a constant number of operations (one comparison, one subtraction, one bitwise AND, one comparison) regardless of the input size. No additional space is required beyond a few variables.