Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two if there exists an integer x such that n == 2^x.
Output: true
Explanation: 2^0 = 1.
Output: false
Explanation: 3 is not expressible as 2^x for any integer x.
A power of two has exactly one bit set in its binary representation (e.g., 1=001, 2=010, 4=100, 8=1000). The expression n & (n-1) clears the lowest set bit of n. If n is a power of two, this results in 0.
- n must be greater than 0 (powers of two are positive).
- n & (n-1) must equal 0 — this is true only when n has exactly one set bit.
- Combine both conditions:
n > 0 && (n & (n-1)) == 0.
Complexity Analysis:
Time complexity: O(1) — single bit operation.
Space complexity: O(1) — constant extra space.