Loading…

easyBit ManipulationLC #231Frequently asked

Power of Two

Q: How do you solve Power of Two using the Divide-by-Two Loop (Warm-Up) approach?

When to use it: Mention as the intuitive baseline, then say 'we can do this in O(1) with bits'. Repeatedly strip a factor of 2 and see whether you land on 1. **The idea.** Every power of two divides evenly by 2 all the way down: 16 → 8 → 4 → 2 → 1. A number with any odd factor stalls — 6 → 3, and 3 is odd and bigger than 1, so 6 is not a power of two. **The guard.** Numbers ≤ 0 can never be powers of two, so return false immediately for them; otherwise the loop on 0 or negatives misbehaves. **The loop.** While n is even and greater than 1, divide by 2. When the loop ends, n is a power of two exactly when it equals 1. **Why we move past this.** It is correct and only O(log n), but it loops where a single bitwise expression would do. Show it to demonstrate understanding, then present the O(1) trick. Time complexity: O(log n). Space complexity: O(1).

Q: How do you solve Power of Two using the Clear Lowest Set Bit — n & (n - 1) (Optimal) approach?

When to use it: The answer they want. Phrase it as 'a power of two has exactly one set bit, and n & (n-1) clears the lowest set bit'. Test for a single set bit by clearing the lowest one and checking nothing remains. **The binary fact.** A power of two is `1` followed by zeros: `1`, `10`, `100`, `1000`. Exactly one bit is set. So 'is n a power of two?' becomes 'does n have exactly one set bit?' (for positive n). **What n - 1 does to the bits.** Subtracting 1 finds the lowest set bit of n, flips it to 0, and turns every bit *below* it into 1. For `n = 1000₂`, `n - 1 = 0111₂`. For `n = 1100₂`, `n - 1 = 1011₂` — the lowest set bit (position 2) cleared, the bit below it set. **Why the AND nails it.** `n & (n - 1)` keeps only the bits set in *both*. Since `n - 1` cleared n's lowest set bit and set everything below it (where n had zeros), the AND drops that lowest bit and preserves all higher bits of n. If n had just one bit, there are no higher bits, so the result is `0`. If n had two or more bits, a higher bit survives and the result is non-zero. **The guard.** For `n = 0`, `n - 1` is all ones (`-1`), and `0 & -1 == 0`, which would falsely report true — so `n > 0` is required. Negatives have the sign bit set and are excluded by the same guard. That single comparison plus the AND is the whole O(1) solution. Time complexity: O(1). Space complexity: O(1).

LCPractice

Bit Manipulation · 10 of 20 · 7 min

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ˣ.

In plain English

Decide whether n equals 2 raised to some non-negative power. In binary, 2ˣ is a 1 followed by x zeros — exactly one set bit. So the task reduces to: does n have precisely one bit set, and is n positive? Zero and all negatives must return false.

Examples

Example 1

Input: n = 1
Output: true
Note: 1 = 2⁰. Binary 1 has a single set bit.

Example 2

Input: n = 16
Output: true
Note: 16 = 2⁴ = 10000₂, one set bit. 16 & 15 = 10000 & 01111 = 0.

Example 3

Input: n = 6
Output: false
Note: 6 = 110₂ has two set bits. 6 & 5 = 110 & 101 = 100 ≠ 0.

Example 4

Input: n = 0
Output: false
Note: Zero has no set bits and is rejected by the n > 0 guard.

Constraints

-2³¹ ≤ n ≤ 2³¹ - 1
n fits in a 32-bit signed integer
x is a non-negative integer (so 1 = 2⁰ counts)

Clarifying questions4First question: Does 1 count as a power of two?Explore questions

Q1.Does 1 count as a power of two?
Yes — 1 = 2⁰. The bit trick handles it: 1 & 0 == 0, and 1 > 0, so it returns true.
Q2.What about 0 and negative numbers?
Both return false. Zero has no set bits; negatives in two's complement have the sign bit set. The n > 0 guard covers both.
Q3.Is n a 32-bit or 64-bit value?
32-bit signed here. The trick is width-independent, but I keep the guard so the sign bit on negatives doesn't slip through.
Q4.Are loops acceptable, or do they want O(1)?
A divide-by-two loop is O(log n) and fine as a warm-up, but the expected answer is the O(1) bit trick.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A positive number is a power of two exactly when its binary form has a single 1 bit. The one-line test is `n > 0 && (n & (n - 1)) == 0`. Subtracting 1 flips the lowest set bit and turns everything below it to 1; ANDing with the original clears that lowest bit. If the result is 0, there was only one bit set. The `n > 0` guard rejects zero and negatives.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you connect 'power of two' to 'one bit set' and know the n & (n-1) identity, plus whether you remember the zero/negative guard.

Where candidates slip

Forgetting the n > 0 guard, so n = 0 wrongly returns true, or reaching for a divide-by-two loop and missing the O(1) trick.

How to stand out

State the binary insight first, show n & (n-1), explain what subtracting 1 does to the bits, and mention the n & (-n) alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Divide-by-Two Loop (Warm-Up)	`O(log n)`	`O(1)`	Mention as the intuitive baseline, then say 'we can do this in O(1) with bits'.	Read
2	Clear Lowest Set Bit — n & (n - 1) (Optimal)Optimal	`O(1)`	`O(1)`	The answer they want. Phrase it as 'a power of two has exactly one set bit, and n & (n-1) clears the lowest set bit'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewIs n a power of two?Need O(1)?No, warm-upYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Divide-by-Two Loop (Warm-Up)

TimeO(log n)SpaceO(1)

Mention as the intuitive baseline, then say 'we can do this in O(1) with bits'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A power of two keeps halving cleanly down to 1. What happens to a non-power along the way?

2Hint 2Explore hint

While n is greater than 1 and even, divide it by 2. If you ever hit an odd number above 1, it wasn't a power of two.

3Hint 3Explore hint

After the loop, n is a power of two iff it landed exactly on 1. Guard n ≤ 0 up front.

A · Core idea

Repeatedly strip a factor of 2 and see whether you land on 1.

The idea. Every power of two divides evenly by 2 all the way down: 16 → 8 → 4 → 2 → 1. A number with any odd factor stalls — 6 → 3, and 3 is odd and bigger than 1, so 6 is not a power of two.

The guard. Numbers ≤ 0 can never be powers of two, so return false immediately for them; otherwise the loop on 0 or negatives misbehaves.

The loop. While n is even and greater than 1, divide by 2. When the loop ends, n is a power of two exactly when it equals 1.

Why we move past this. It is correct and only O(log n), but it loops where a single bitwise expression would do. Show it to demonstrate understanding, then present the O(1) trick.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 16

Array state

start

16 even

n ↓

[0]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isPowerOfTwo(int n) { if (n <= 0) return false; while (n % 2 == 0) { n /= 2; }Explore the full code

solution.javaJava

Divide-by-Two Loop (Warm-Up) — reference

3 teaching notes

1
public boolean isPowerOfTwo(int n) {
2
    // Zero and negatives are never powers of two — reject before looping.
3
    if (n <= 0) return false;
4
    // Strip a factor of 2 while n stays even.
5
    while (n % 2 == 0) {
6
        n /= 2;
7
    }
8
    // A clean power of two ends exactly at 1; an odd factor leaves something bigger.
9
    return n == 1;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Halving is just a right shift, and 'is it still even?' is just 'is the lowest bit 0?'. That observation is the bridge from this loop to the constant-time bit trick.

ComplexityO(log n) time, O(1) space — Each iteration halves n, so there are at most log₂(n) iterations. Only a couple of integer variables are used, so space is O(1).

E · Edge cases and pitfalls3Skipping the n ≤ 0 guard — the loop misbehaves on 0 and negatives.Explore edge cases

Pitfalls

Skipping the n ≤ 0 guard — the loop misbehaves on 0 and negatives.
Returning true whenever the loop ends, instead of checking n == 1.
Looping when an O(1) bit test is available — interviewers expect the trick.

03.2

Approach 2 of 2 · Optimal

Clear Lowest Set Bit — n & (n - 1) (Optimal)

TimeO(1)SpaceO(1)

The answer they want. Phrase it as 'a power of two has exactly one set bit, and n & (n-1) clears the lowest set bit'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write a few powers of two in binary: 1, 10, 100, 1000. What do they all share?

2Hint 2Explore hint

Subtracting 1 from a number flips its lowest set bit to 0 and sets all bits below it to 1. What does ANDing that with the original do?

3Hint 3Explore hint

If n has a single set bit, n & (n-1) wipes it to 0. Add the n > 0 guard so 0 and negatives don't sneak through.

A · Core idea

Test for a single set bit by clearing the lowest one and checking nothing remains.

The binary fact. A power of two is 1 followed by zeros: 1, 10, 100, 1000. Exactly one bit is set. So 'is n a power of two?' becomes 'does n have exactly one set bit?' (for positive n).

What n - 1 does to the bits. Subtracting 1 finds the lowest set bit of n, flips it to 0, and turns every bit below it into 1. For n = 1000₂, n - 1 = 0111₂. For n = 1100₂, n - 1 = 1011₂ — the lowest set bit (position 2) cleared, the bit below it set.

Why the AND nails it. n & (n - 1) keeps only the bits set in both. Since n - 1 cleared n's lowest set bit and set everything below it (where n had zeros), the AND drops that lowest bit and preserves all higher bits of n. If n had just one bit, there are no higher bits, so the result is 0. If n had two or more bits, a higher bit survives and the result is non-zero.

The guard. For n = 0, n - 1 is all ones (-1), and 0 & -1 == 0, which would falsely report true — so n > 0 is required. Negatives have the sign bit set and are excluded by the same guard. That single comparison plus the AND is the whole O(1) solution.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 6 (not a power) vs n = 8 (power)

Array state

n = 8

binary 1000

set bit ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result8 → true, 6 → false, 0 → false

C · Code with teaching comments

solution.javaJava

Clear Lowest Set Bit — n & (n - 1) (Optimal) — optimal

1 teaching note

1
public boolean isPowerOfTwo(int n) {
2
    // n > 0 rejects zero and negatives; (n & (n-1)) == 0 confirms exactly one set bit.
3
    // Short-circuit && means the AND only runs when n is positive.
4
    return n > 0 && (n & (n - 1)) == 0;
5
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.5 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

n & (n - 1) is the universal 'clear the lowest set bit' move — it powers Brian Kernighan's bit-count and many mask tricks. Recognizing that a power of two is the one-bit case turns the entire problem into a single application of it.

ComplexityO(1) time, O(1) space — A single subtraction, a single bitwise AND, and one comparison — all constant-time machine operations regardless of n. No extra memory.

E · Edge cases and pitfalls7n = 1 — 1 & 0 = 0 and 1 > 0 → true (2⁰).Explore edge cases

Edge cases handled

n = 11 & 0 = 0 and 1 > 0 → true (2⁰).
n = 0Guard n > 0 fails → false, even though 0 & -1 = 0.
n = -16Negative; guard rejects it → false despite |16| being a power of two.
n = 2147483647 (2³¹ - 1)Many bits set, AND ≠ 0 → false; no overflow since no addition is done.

Pitfalls

Dropping the n > 0 guard — 0 wrongly returns true because 0 & -1 == 0.
Writing (n & (n - 1)) without parentheses — & has lower precedence than ==, so it parses wrong.
Assuming it works on negatives — the sign bit makes the AND meaningless without the guard.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the positive guard

For n = 0, n - 1 is -1 (all ones), and 0 & -1 == 0, so without n > 0 the function falsely returns true for zero.

Explore the code comparison

Don't write this

public boolean isPowerOfTwo(int n) {
    return (n & (n - 1)) == 0; // 0 wrongly returns true
}

Write this instead

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Operator precedence trap

In C-family languages == has higher precedence than &, so `n & (n - 1) == 0` parses as `n & ((n - 1) == 0)`, giving the wrong result.

Explore the code comparison

Don't write this

return n > 0 && n & (n - 1) == 0; // parses as n & ((n-1)==0)

Write this instead

return n > 0 && (n & (n - 1)) == 0; // parenthesize the AND

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Single-set-bit test via n & (n - 1)

Code pattern to memorize

isPowerOfTwo(n) = (n > 0) && ((n & (n - 1)) == 0)

Rules to remember

1n & (n - 1) clears the lowest set bit. Zero result ⇒ there was only one set bit.
2Always guard with n > 0. For n = 0, n & (n-1) is 0 & -1 = 0, which would falsely pass.
3Negatives are never powers of two; the n > 0 guard rejects them in one shot.
4An alternative trick is n & (-n) == n — isolate the lowest bit and check it equals n.
5Avoid looping-divide-by-2 in interviews when the bit trick exists; mention the loop, then show the O(1) trick.

Use this pattern when

Checking if a value is a single power of two (capacity sizing, hashing, alignment)
Validating a number has exactly one bit set
Bitmask code that requires power-of-two table sizes
Any 'is this 2^k?' question on integers

Choose another pattern when

Need the exponent k itself → use log2 / count trailing zeros, not just the boolean
Power of four specifically → extra mask to confirm the bit sits in an even position
Counting all set bits → Brian Kernighan's loop, not a single clear
Floating-point inputs → the integer bit trick doesn't apply

Interview takeaway

Powers of two are the numbers with exactly one bit set, and `n & (n - 1)` clears the lowest set bit. So `(n & (n-1)) == 0` (with `n > 0`) is the whole test — an O(1), branch-light classic.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPower-of-two detection is the one-set-bit special case of n & (n - 1), the universal lowest-set-bit clear. The same identity drives Number of 1 Bits, Counting Bits, and Power of Four.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Power of Four
Coming soon
Same single-bit test, plus check the bit sits in an even position with a 0x55555555 mask.
Number of 1 Bits
Count set bits by repeatedly applying n &= (n - 1) — the same lowest-bit clear, looped.
Power of Three
Coming soon
No clean bit trick for base 3 — use repeated division or the largest-power-of-three modulo trick.
Counting Bits
DP where bits[i] = bits[i & (i - 1)] + 1 reuses the lowest-bit-clear identity.

Same pattern

←

Gray Code Generation

Continue · Next problem

Sum Over Subsets (SOS DP)

easyBit ManipulationLC #231Frequently asked

Power of Two

LCPractice

Bit Manipulation · 10 of 20 · 7 min

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ˣ.

In plain English

Examples

Example 1

Input: n = 1
Output: true
Note: 1 = 2⁰. Binary 1 has a single set bit.

Example 2

Input: n = 16
Output: true
Note: 16 = 2⁴ = 10000₂, one set bit. 16 & 15 = 10000 & 01111 = 0.

Example 3

Input: n = 6
Output: false
Note: 6 = 110₂ has two set bits. 6 & 5 = 110 & 101 = 100 ≠ 0.

Example 4

Input: n = 0
Output: false
Note: Zero has no set bits and is rejected by the n > 0 guard.

Constraints

-2³¹ ≤ n ≤ 2³¹ - 1
n fits in a 32-bit signed integer
x is a non-negative integer (so 1 = 2⁰ counts)

Clarifying questions4First question: Does 1 count as a power of two?Explore questions

Q1.Does 1 count as a power of two?
Yes — 1 = 2⁰. The bit trick handles it: 1 & 0 == 0, and 1 > 0, so it returns true.
Q2.What about 0 and negative numbers?
Both return false. Zero has no set bits; negatives in two's complement have the sign bit set. The n > 0 guard covers both.
Q3.Is n a 32-bit or 64-bit value?
32-bit signed here. The trick is width-independent, but I keep the guard so the sign bit on negatives doesn't slip through.
Q4.Are loops acceptable, or do they want O(1)?
A divide-by-two loop is O(log n) and fine as a warm-up, but the expected answer is the O(1) bit trick.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you connect 'power of two' to 'one bit set' and know the n & (n-1) identity, plus whether you remember the zero/negative guard.

Where candidates slip

Forgetting the n > 0 guard, so n = 0 wrongly returns true, or reaching for a divide-by-two loop and missing the O(1) trick.

How to stand out

State the binary insight first, show n & (n-1), explain what subtracting 1 does to the bits, and mention the n & (-n) alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Divide-by-Two Loop (Warm-Up)	`O(log n)`	`O(1)`	Mention as the intuitive baseline, then say 'we can do this in O(1) with bits'.	Read
2	Clear Lowest Set Bit — n & (n - 1) (Optimal)Optimal	`O(1)`	`O(1)`	The answer they want. Phrase it as 'a power of two has exactly one set bit, and n & (n-1) clears the lowest set bit'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Divide-by-Two Loop (Warm-Up)

TimeO(log n)SpaceO(1)

Mention as the intuitive baseline, then say 'we can do this in O(1) with bits'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A power of two keeps halving cleanly down to 1. What happens to a non-power along the way?

2Hint 2Explore hint

While n is greater than 1 and even, divide it by 2. If you ever hit an odd number above 1, it wasn't a power of two.

3Hint 3Explore hint

After the loop, n is a power of two iff it landed exactly on 1. Guard n ≤ 0 up front.

A · Core idea

Repeatedly strip a factor of 2 and see whether you land on 1.

The guard. Numbers ≤ 0 can never be powers of two, so return false immediately for them; otherwise the loop on 0 or negatives misbehaves.

The loop. While n is even and greater than 1, divide by 2. When the loop ends, n is a power of two exactly when it equals 1.

Why we move past this. It is correct and only O(log n), but it loops where a single bitwise expression would do. Show it to demonstrate understanding, then present the O(1) trick.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 16

Array state

start

16 even

n ↓

[0]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isPowerOfTwo(int n) { if (n <= 0) return false; while (n % 2 == 0) { n /= 2; }Explore the full code

solution.javaJava

Divide-by-Two Loop (Warm-Up) — reference

3 teaching notes

1
public boolean isPowerOfTwo(int n) {
2
    // Zero and negatives are never powers of two — reject before looping.
3
    if (n <= 0) return false;
4
    // Strip a factor of 2 while n stays even.
5
    while (n % 2 == 0) {
6
        n /= 2;
7
    }
8
    // A clean power of two ends exactly at 1; an odd factor leaves something bigger.
9
    return n == 1;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Halving is just a right shift, and 'is it still even?' is just 'is the lowest bit 0?'. That observation is the bridge from this loop to the constant-time bit trick.

ComplexityO(log n) time, O(1) space — Each iteration halves n, so there are at most log₂(n) iterations. Only a couple of integer variables are used, so space is O(1).

E · Edge cases and pitfalls3Skipping the n ≤ 0 guard — the loop misbehaves on 0 and negatives.Explore edge cases

Pitfalls

Skipping the n ≤ 0 guard — the loop misbehaves on 0 and negatives.
Returning true whenever the loop ends, instead of checking n == 1.
Looping when an O(1) bit test is available — interviewers expect the trick.

03.2

Approach 2 of 2 · Optimal

Clear Lowest Set Bit — n & (n - 1) (Optimal)

TimeO(1)SpaceO(1)

The answer they want. Phrase it as 'a power of two has exactly one set bit, and n & (n-1) clears the lowest set bit'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write a few powers of two in binary: 1, 10, 100, 1000. What do they all share?

2Hint 2Explore hint

Subtracting 1 from a number flips its lowest set bit to 0 and sets all bits below it to 1. What does ANDing that with the original do?

3Hint 3Explore hint

If n has a single set bit, n & (n-1) wipes it to 0. Add the n > 0 guard so 0 and negatives don't sneak through.

A · Core idea

Test for a single set bit by clearing the lowest one and checking nothing remains.

The binary fact. A power of two is 1 followed by zeros: 1, 10, 100, 1000. Exactly one bit is set. So 'is n a power of two?' becomes 'does n have exactly one set bit?' (for positive n).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 6 (not a power) vs n = 8 (power)

Array state

n = 8

binary 1000

set bit ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result8 → true, 6 → false, 0 → false

C · Code with teaching comments

solution.javaJava

Clear Lowest Set Bit — n & (n - 1) (Optimal) — optimal

1 teaching note

1
public boolean isPowerOfTwo(int n) {
2
    // n > 0 rejects zero and negatives; (n & (n-1)) == 0 confirms exactly one set bit.
3
    // Short-circuit && means the AND only runs when n is positive.
4
    return n > 0 && (n & (n - 1)) == 0;
5
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.5 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(1) time, O(1) space — A single subtraction, a single bitwise AND, and one comparison — all constant-time machine operations regardless of n. No extra memory.

E · Edge cases and pitfalls7n = 1 — 1 & 0 = 0 and 1 > 0 → true (2⁰).Explore edge cases

Edge cases handled

n = 11 & 0 = 0 and 1 > 0 → true (2⁰).
n = 0Guard n > 0 fails → false, even though 0 & -1 = 0.
n = -16Negative; guard rejects it → false despite |16| being a power of two.
n = 2147483647 (2³¹ - 1)Many bits set, AND ≠ 0 → false; no overflow since no addition is done.

Pitfalls

Dropping the n > 0 guard — 0 wrongly returns true because 0 & -1 == 0.
Writing (n & (n - 1)) without parentheses — & has lower precedence than ==, so it parses wrong.
Assuming it works on negatives — the sign bit makes the AND meaningless without the guard.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the positive guard

For n = 0, n - 1 is -1 (all ones), and 0 & -1 == 0, so without n > 0 the function falsely returns true for zero.

Explore the code comparison

Don't write this

public boolean isPowerOfTwo(int n) {
    return (n & (n - 1)) == 0; // 0 wrongly returns true
}

Write this instead

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Operator precedence trap

In C-family languages == has higher precedence than &, so `n & (n - 1) == 0` parses as `n & ((n - 1) == 0)`, giving the wrong result.

Explore the code comparison

Don't write this

return n > 0 && n & (n - 1) == 0; // parses as n & ((n-1)==0)

Write this instead

return n > 0 && (n & (n - 1)) == 0; // parenthesize the AND

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Single-set-bit test via n & (n - 1)

Code pattern to memorize

isPowerOfTwo(n) = (n > 0) && ((n & (n - 1)) == 0)

Rules to remember

1n & (n - 1) clears the lowest set bit. Zero result ⇒ there was only one set bit.
2Always guard with n > 0. For n = 0, n & (n-1) is 0 & -1 = 0, which would falsely pass.
3Negatives are never powers of two; the n > 0 guard rejects them in one shot.
4An alternative trick is n & (-n) == n — isolate the lowest bit and check it equals n.
5Avoid looping-divide-by-2 in interviews when the bit trick exists; mention the loop, then show the O(1) trick.

Use this pattern when

Checking if a value is a single power of two (capacity sizing, hashing, alignment)
Validating a number has exactly one bit set
Bitmask code that requires power-of-two table sizes
Any 'is this 2^k?' question on integers

Choose another pattern when

Need the exponent k itself → use log2 / count trailing zeros, not just the boolean
Power of four specifically → extra mask to confirm the bit sits in an even position
Counting all set bits → Brian Kernighan's loop, not a single clear
Floating-point inputs → the integer bit trick doesn't apply

Interview takeaway

Powers of two are the numbers with exactly one bit set, and `n & (n - 1)` clears the lowest set bit. So `(n & (n-1)) == 0` (with `n > 0`) is the whole test — an O(1), branch-light classic.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Power of Four
Coming soon
Same single-bit test, plus check the bit sits in an even position with a 0x55555555 mask.
Number of 1 Bits
Count set bits by repeatedly applying n &= (n - 1) — the same lowest-bit clear, looped.
Power of Three
Coming soon
No clean bit trick for base 3 — use repeated division or the largest-power-of-three modulo trick.
Counting Bits
DP where bits[i] = bits[i & (i - 1)] + 1 reuses the lowest-bit-clear identity.

Same pattern

←

Gray Code Generation

Continue · Next problem

Sum Over Subsets (SOS DP)