Bit Manipulation — Power of Two
↗ LeetCode: Power of Two · Easy · pattern chapter →
Asked atMetaAmazonGoogleMicrosoft
Return true iff n is a positive power of two.
Example 1 — n=1 → true (2⁰) Example 2 — n=16 → trueExample 3 — n=3 → false
Constraints — -2³¹ ≤ n ≤ 2³¹−1. Brute divide-by-2 loop is O(log n) = 30 iters at n=2³¹. Bit trick n>0 && (n&(n-1))==0 is 2 ops = <1 ns — 10⁹ checks/sec.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Divide by 2
O(log n).
Approach 2 — n & (n-1) == 0 (canonical)
Insight. A positive power of two has exactly one bit set. n & (n-1) clears the lowest set bit → 0 iff there was only one.
Trap — guard n > 0. For n = 0, 0 & -1 == 0 would falsely return true.
java
boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}Complexity — Time O(1); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Divide by 2 | O(log n) | O(1) | works |
n & (n-1) == 0 | O(1) | O(1) | canonical |
When to use which
- "Power of 2" → bit trick.
- "Power of 4" → also check
n & 0x55555555 != 0(bit at even position). - "Power of 3" → no clean bit trick —
1162261467 % n == 0(largest power of 3 ≤ INT_MAX).
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems