Power of 2 Check
n & (n−1) removes the lowest set bit. If n is a power of 2, it has exactly one set bit, so n & (n−1) == 0. Example: 8 (1000) & 7 (0111) = 0. Works for any positive n.
How It Works
The expression n & (n-1) clears the lowest set bit of n: subtracting 1 flips that bit to 0 and turns all lower bits to 1, so the AND wipes it while leaving higher bits intact. A power of two has exactly one set bit, so clearing it must leave zero. The test is therefore n > 0 && (n & (n-1)) == 0 — a single constant-time expression.
A loop that repeatedly divides by 2 takes O(log n) iterations; this check is O(1) with no branching or division. The n > 0 guard matters because zero has no set bits yet also satisfies the AND condition, and negative numbers are never powers of two. The sibling trick n & (-n) isolates rather than clears the lowest set bit, and both idioms recur throughout bitmask code, Fenwick trees, and subset enumeration.
Step-by-Step Visualization
Code
static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// isPowerOfTwo(16) → true (10000)
// isPowerOfTwo(6) → false (110)Tips & Gotchas
Practice Problems
- 1Power of Two
- 2Power of Four
- 3Bitwise AND of Numbers Range
About the Core Bit Tricks Pattern
Fundamental bit operations that appear in many problems. These are building blocks — memorize them.
Key tricks: n & (n−1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.
Common Bit Manipulation Interview Problems
- Single Number
- Number of 1 Bits
- Counting Bits
- Missing Number
- Reverse Bits
- Power of Two
Frequently Asked Questions
Why does n & (n-1) clear exactly the lowest set bit?
Subtracting 1 borrows through the trailing zeros: the lowest set bit becomes 0 and every bit below it becomes 1, while higher bits are untouched. ANDing with the original then zeroes the flipped bit and the trailing ones, leaving all higher bits as they were.
How would I extend this to check for a power of four?
First confirm n is a power of two with n & (n-1) == 0, then verify the single set bit sits at an even position — for example with (n & 0x55555555) != 0, a mask covering bits 0, 2, 4, and so on. Powers of four are exactly the powers of two whose lone bit is at an even index.