Loading…

mediumBit ManipulationLC #201Sometimes asked

Bitwise AND of Numbers Range

Q: How do you solve Bitwise AND of Numbers Range using the Brute Force — AND Every Number in the Range approach?

When to use it: Say it first to frame the problem, then immediately note it's O(range) and infeasible for the constraints. The most direct translation: fold the AND across the whole range. **How it works.** Initialise `result = left`, then iterate `i` from `left + 1` to `right`, doing `result &= i`. After the loop `result` holds the AND of every number in `[left, right]`. It's obviously correct — it's the definition. **Why it's too slow.** The constraints allow `right − left` up to about `2³¹ ≈ 2.1 billion`. Even at hundreds of millions of operations per second that's seconds-to-minutes per call — an immediate TLE. The problem size is specifically chosen to forbid iterating the range. **A subtle correctness hazard at the boundary.** If `right == Integer.MAX_VALUE` and you loop with an `int i` using `i <= right`, then `i` overflows to a negative number after `MAX_VALUE` and the loop never terminates. Avoiding this forces an awkward `long` counter or break logic — another reason the brute force is a poor fit even before performance. **The takeaway that unlocks the real solution.** Watching the AND of `5, 6, 7` collapse to `4` reveals the structure: the low-order bits *churn* through both 0 and 1 across consecutive integers, so they get zeroed, while the high-order bits the endpoints already share are untouched. That observation — only the common high prefix survives — is the basis for the O(log n) approaches. Time complexity: O(right − left). Space complexity: O(1).

Q: How do you solve Bitwise AND of Numbers Range using the Brian Kernighan — Strip Right's Low Set Bits approach?

When to use it: Offer as an elegant alternative once you've explained the prefix idea — shows depth with bit tricks. A second route to the same prefix, using Brian Kernighan's bit-clearing identity. **The identity.** `x & (x - 1)` turns off the **lowest set bit** of `x`. For example `right = 1100` → `right & (right-1) = 1100 & 1011 = 1000`: the lowest `1` is gone. **Why repeatedly clearing right's low bits works.** We argued that every bit at or below the top position where `left` and `right` differ must be `0` in the answer. Those are exactly the low set bits of `right` that sit *above* the common prefix. So we strip `right`'s lowest set bit again and again; each removal kills a bit that cannot appear in the range AND. We keep going **while `right > left`** — as long as `right` still exceeds `left`, it must still carry a low set bit that lies within the differing region and therefore must be cleared. The moment `right ≤ left`, every such extra low bit is gone and `right` has collapsed to precisely the common high prefix shared with `left`. We return `right`. **Why the stopping condition is `right > left`.** If `right` ever drops to `left` (or below), the bits it still holds are common to both endpoints — they're the prefix that survives the AND — so there's nothing left to clear. Clearing further would erase legitimate prefix bits and give a wrong, too-small answer. **How it compares to the shift method.** Both are `O(log(max))` and `O(1)` space and produce the identical answer. The shift version is arguably easier to explain ('find the common prefix'); Brian Kernighan is terser and demonstrates fluency with the `x & (x-1)` idiom. Mention both and let the interviewer pick. Time complexity: O(log(max)). Space complexity: O(1).

LCPractice

Bit Manipulation · 8 of 20 · 9 min

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

In plain English

Compute left & (left+1) & (left+2) & ... & right. The range can be enormous (up to ~2 billion numbers), so an explicit loop is infeasible. The result is determined entirely by the bit pattern shared between the two endpoints.

Examples

Example 1

Input: left = 5, right = 7
Output: 4
Note: 5=101, 6=110, 7=111. AND: 101 & 110 & 111 = 100 = 4. Only the top bit (4) is set in all three; the lower bits differ and clear.

Example 2

Input: left = 0, right = 0
Output: 0
Note: Single-number range; the AND is 0 itself.

Example 3

Input: left = 1, right = 2147483647
Output: 0
Note: The range spans across powers of two, so every bit toggles somewhere and clears — the common prefix is empty, giving 0.

Constraints

0 ≤ left ≤ right ≤ 2³¹ − 1

Clarifying questions4First question: How large can the range be?Explore questions

Q1.How large can the range be?
Endpoints up to 2³¹ − 1, so the range can contain billions of numbers. Iterating every value is far too slow — we need a bit-structural shortcut.
Q2.Can left equal right?
Yes. Then the 'range' is a single number and the AND is just that number. Both methods handle it: the while loop never runs, returning left/right unchanged.
Q3.Can left be 0?
Yes. If left is 0 and right > 0, the answer is 0 — 0 ANDed with anything is 0. The prefix method returns 0 because the endpoints share no leading prefix above the differing bits.
Q4.Are these unsigned or signed integers?
Non-negative (0 ≤ left ≤ right ≤ 2³¹ − 1), so they fit in a signed 32-bit int and all shifts are logical/positive. In Java use >> safely since values are non-negative; >>> also works.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The AND of every integer in [left, right] equals the common binary prefix of left and right, with all lower bits zeroed. Any bit that differs anywhere in the range gets cleared, because within a contiguous range that bit toggles at least once (so some number has it 0). Shift both endpoints right until they're equal (counting shifts), then shift left by that count. O(log(max)) time, O(1) space. Brian Kernighan's `right &= right - 1` until `right ≤ left` is an equivalent one-liner.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reason about how individual bits behave across a contiguous range — recognising that the AND collapses to the endpoints' common prefix — instead of naively ANDing every number (which can be 2³¹ iterations).

Where candidates slip

Looping i from left to right ANDing each value (TLE for large ranges and risk of infinite loop at INT_MAX), or mishandling left == right / the all-zero collapse.

How to stand out

Explain WHY differing bits vanish: within consecutive integers a low bit toggles, so some number zeroes it; only the unchanging high prefix remains. Then give both the prefix-shift and Brian-Kernighan one-liners and their O(log n) cost.

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	Brute Force — AND Every Number in the Range	`O(right − left)`	`O(1)`	Say it first to frame the problem, then immediately note it's O(range) and infeasible for the constraints.	Read
2	Common Binary Prefix — Shift Until Equal (Optimal)Optimal	`O(log(max))`	`O(1)`	The answer they want. Frame it as 'the AND is the shared high prefix; find it by shifting both endpoints together'.	Read
3	Brian Kernighan — Strip Right's Low Set Bits	`O(log(max))`	`O(1)`	Offer as an elegant alternative once you've explained the prefix idea — shows depth with bit tricks.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Why low bits die: 5,6,7 in binary

How to read it:The high prefix '1' is shared by all three; the lower two bits each take both values across the range, so they AND to 0.

Rendering diagram…

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 3

Brute Force — AND Every Number in the Range

TimeO(right − left)SpaceO(1)

Say it first to frame the problem, then immediately note it's O(range) and infeasible for the constraints.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal definition: start an accumulator at left, then AND in left+1, left+2, ..., up to right.

2Hint 2Explore hint

Estimate the cost: with endpoints up to 2³¹, the range can hold ~2 billion numbers — far too many to loop.

3Hint 3Explore hint

Also notice a subtle hazard: if right is INT_MAX, a `for (long i...)` or careless `int i <= right` can overflow or loop forever. Use this to motivate the bit shortcut.

A · Core idea

The most direct translation: fold the AND across the whole range.

How it works. Initialise result = left, then iterate i from left + 1 to right, doing result &= i. After the loop result holds the AND of every number in [left, right]. It's obviously correct — it's the definition.

Why it's too slow. The constraints allow right − left up to about 2³¹ ≈ 2.1 billion. Even at hundreds of millions of operations per second that's seconds-to-minutes per call — an immediate TLE. The problem size is specifically chosen to forbid iterating the range.

A subtle correctness hazard at the boundary. If right == Integer.MAX_VALUE and you loop with an int i using i <= right, then i overflows to a negative number after MAX_VALUE and the loop never terminates. Avoiding this forces an awkward long counter or break logic — another reason the brute force is a poor fit even before performance.

The takeaway that unlocks the real solution. Watching the AND of 5, 6, 7 collapse to 4 reveals the structure: the low-order bits churn through both 0 and 1 across consecutive integers, so they get zeroed, while the high-order bits the endpoints already share are untouched. That observation — only the common high prefix survives — is the basis for the O(log n) approaches.

B · Visual dry run

Interactive dry run

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

left = 5, right = 7

init

result = 5 (101)

Stateresult = 101

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rangeBitwiseAnd(int left, int right) { int result = left; for (long i = (long) left + 1; i <= right; i++) { result &= (int) i; // 'long i' avoids overflow when right == INT_MAX }Explore the full code

solution.javaJava

Brute Force — AND Every Number in the Range — reference

2 teaching notes

1
public int rangeBitwiseAnd(int left, int right) {
2
    int result = left;
3
    // Use a long counter so i <= right doesn't overflow when right == INT_MAX.
4
    for (long i = (long) left + 1; i <= right; i++) {
5
        result &= (int) i; // 'long i' avoids overflow when right == INT_MAX
6
    }
7
    return result;
8
}

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

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

Manually ANDing a few small ranges exposes the pattern: lower bits toggle across consecutive numbers and clear, only the shared high prefix of the endpoints remains. Seeing that structure is what lets you replace an O(range) loop with an O(log n) prefix computation.

ComplexityO(right − left) time, O(1) space — One AND per number in the range → O(right − left), which can approach 2³¹ operations. Constant space. Correct, but times out and risks overflow at the top of the int range.

E · Edge cases and pitfalls5left = 5, right = 5 — Loop body never executes; returns 5.Explore edge cases

Edge cases handled

left = 5, right = 5Loop body never executes; returns 5.
left = 0, right = 2³¹−1Correct result 0 but ~2 billion iterations — TLE; motivates the shortcut.

Pitfalls

Using `int i` with `i <= right` — overflows and loops forever when right == INT_MAX.
Assuming the range is small — it can be billions wide.
Treating O(range) as acceptable; it's the trap this problem sets.

03.2

Approach 2 of 3 · Optimal

Common Binary Prefix — Shift Until Equal (Optimal)

TimeO(log(max))SpaceO(1)

The answer they want. Frame it as 'the AND is the shared high prefix; find it by shifting both endpoints together'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at left and right in binary. Any bit position where they DIFFER — what must the AND of the whole range be at that position, and why?

2Hint 2Explore hint

If two endpoints differ at bit position p, the range crosses a boundary where that bit (and everything below it) takes both 0 and 1, so all bits ≤ p clear. Only the identical high bits above the top differing position survive.

3Hint 3Explore hint

Find that shared prefix: right-shift left and right together, counting shifts, until they're equal. Then shift the common value back left by the count to re-append the zeroed low bits.

A · Core idea

The key fact: the AND over `[left, right]` is exactly the longest common high-order bit prefix of `left` and `right`, padded with zeros in the low bits.

Why differing bits must be zero. Suppose left and right differ first (from the top) at bit position p — meaning left has 0 there and right has 1 (it must be this way since left ≤ right and all higher bits match). Then as numbers increase from left to right, bit p flips from 0 to 1 somewhere, which can only happen by a carry that also sweeps every bit below p through 0. Concretely, the range contains a number whose bit p is 1 with all lower bits 0 (the next multiple of 2^p), and a number just below it with bit p = 0. So for bit p and every bit below it, the range contains at least one value with that bit 0. ANDing anything with a 0 in a position yields 0 there. Hence all bits at and below the top differing position are cleared.

Why the high bits survive. Above position p, left and right are bit-for-bit identical, and because the range never crosses a boundary that would change those higher bits (that would require the numbers to differ there), every number in [left, right] shares that exact high prefix. ANDing identical bits leaves them unchanged. So the result = (shared high prefix) followed by all zeros.

The algorithm. To extract the common prefix, repeatedly right-shift both endpoints by one and count the shifts, stopping when they become equal. At that moment the shared value is the common prefix with the differing low bits discarded. Re-append those discarded positions as zeros by shifting the common value left by the number of shifts. That's left << shift. The loop runs at most ~31 times (one per bit), so it's O(log(max)), utterly independent of how wide the range is.

Why this beats the loop categorically. The brute force scaled with the range size (up to billions); this scales with the number of bits (about 31). We replaced 'visit every number' with 'reason about the bit structure once'. Both endpoints are non-negative (≤ 2³¹−1), so the right shifts are logical and safe in both languages.

B · Visual dry run

Interactive dry run

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

left = 5, right = 7

Interactive diagram

Shifting endpoints to the common prefix

start

Active call / nodeSupporting contextReturned stateNot active

Both endpoints shift right together until equal; the shared value, shifted back, is the answer.

Final result4

C · Code with teaching comments

solution.javaJava

Common Binary Prefix — Shift Until Equal (Optimal) — optimal

4 teaching notes

1
public int rangeBitwiseAnd(int left, int right) {
2
    int shift = 0;
3
    // Keep dropping low bits until the two endpoints collapse to their shared prefix.
4
    while (left < right) {
5
        left >>= 1;
6
        right >>= 1;
7
        // Count how many low bits were discarded so we can zero-pad them back.
8
        shift++;
9
    }
10
    // left now equals the common prefix; shift it back left to append the cleared low
11
    // bits as zeros.
12
    return left << shift;
13
}

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

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

The whole problem collapses to: 'what high bits do left and right share?' A bit that differs between the endpoints is guaranteed 0 in the AND because a carry across the range zeroes it; the unchanging prefix is all that remains. Shifting both endpoints until they meet is just a way to read off that prefix in O(31).

ComplexityO(log(max)) time, O(1) space — Each shift drops one bit; there are at most ~31 bits, so the loop runs O(log(max)) ≈ 31 times, each O(1). Constant extra space. No dependence on the range width.

E · Edge cases and pitfalls7left = 0, right = 0 — left < right is false immediately; shift stays 0; return 0 << 0 = 0.Explore edge cases

Edge cases handled

left = 0, right = 0left < right is false immediately; shift stays 0; return 0 << 0 = 0.
left = right = 12Loop doesn't run; returns 12 — single-number range AND.
left = 1, right = 2³¹−1Endpoints share no high prefix; shifting collapses both to 0 → returns 0.
left = 6, right = 6Already equal → 6, no shifting.

Pitfalls

Shifting only one endpoint — they must move together to stay aligned.
Forgetting to shift the common value back left, returning the truncated prefix instead of the zero-padded result.
Using arithmetic right shift on negative values — not an issue here since inputs are non-negative.

03.3

Approach 3 of 3

Brian Kernighan — Strip Right's Low Set Bits

TimeO(log(max))SpaceO(1)

Offer as an elegant alternative once you've explained the prefix idea — shows depth with bit tricks.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Brian Kernighan's trick: `x & (x - 1)` clears the lowest set bit of x. How could clearing low set bits of `right` converge to the common prefix?

2Hint 2Explore hint

Repeatedly clear right's lowest set bit while right is still greater than left. Each clear removes a low bit that can't be in the AND.

3Hint 3Explore hint

Stop when right ≤ left; at that point right has had all its 'extra' low bits stripped and equals the common prefix. Return right.

A · Core idea

A second route to the same prefix, using Brian Kernighan's bit-clearing identity.

The identity. x & (x - 1) turns off the lowest set bit of x. For example right = 1100 → right & (right-1) = 1100 & 1011 = 1000: the lowest 1 is gone.

Why repeatedly clearing right's low bits works. We argued that every bit at or below the top position where left and right differ must be 0 in the answer. Those are exactly the low set bits of right that sit above the common prefix. So we strip right's lowest set bit again and again; each removal kills a bit that cannot appear in the range AND. We keep going while `right > left` — as long as right still exceeds left, it must still carry a low set bit that lies within the differing region and therefore must be cleared. The moment right ≤ left, every such extra low bit is gone and right has collapsed to precisely the common high prefix shared with left. We return right.

Why the stopping condition is `right > left`. If right ever drops to left (or below), the bits it still holds are common to both endpoints — they're the prefix that survives the AND — so there's nothing left to clear. Clearing further would erase legitimate prefix bits and give a wrong, too-small answer.

How it compares to the shift method. Both are O(log(max)) and O(1) space and produce the identical answer. The shift version is arguably easier to explain ('find the common prefix'); Brian Kernighan is terser and demonstrates fluency with the x & (x-1) idiom. Mention both and let the interviewer pick.

B · Visual dry run

Interactive dry run

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

left = 5, right = 7

Interactive diagram

Brian Kernighan stripping bits of right

right=7 (111)

Active call / nodeSupporting contextReturned stateNot active

Each step clears right's lowest set bit until right ≤ left; the survivor is the common prefix.

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rangeBitwiseAnd(int left, int right) { while (left < right) { right &= (right - 1); // clear right's lowest set bit } return right;Explore the full code

solution.javaJava

Brian Kernighan — Strip Right's Low Set Bits — reference

3 teaching notes

1
public int rangeBitwiseAnd(int left, int right) {
2
    // Keep stripping while right still exceeds left — those low set bits can't survive
3
    // the AND.
4
    while (left < right) {
5
        // Brian Kernighan: removes exactly one (the lowest) set bit of right per
6
        // iteration.
7
        right &= (right - 1); // clear right's lowest set bit
8
    }
9
    // Once right <= left it equals the common prefix — that's the range AND.
10
    return right;
11
}

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

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

Brian Kernighan reframes 'find the common prefix' as 'delete every low set bit of right that lies above the prefix'. Because x & (x-1) removes exactly one set bit per step, the loop converges in at most ~31 iterations — and stopping at right <= left is what preserves the surviving prefix bits.

ComplexityO(log(max)) time, O(1) space — Each step clears one set bit of right, and right has at most ~31 set bits, so the loop runs O(log(max)) times, each O(1). Constant space.

E · Edge cases and pitfalls6left = 0, right = 0 — 0 < 0 false → return 0 immediately.Explore edge cases

Edge cases handled

left = 0, right = 00 < 0 false → return 0 immediately.
left = right = 9Loop skipped, returns 9.
left = 0, right = 5Strip 5→4→0 (each clears a low bit) until right ≤ 0; returns 0.

Pitfalls

Using `<=` in the condition (`left <= right`) — over-strips and can wrongly return a value below the prefix.
Clearing left instead of right — left has no extra low bits above the prefix to remove.
Forgetting that `x & (x-1)` removes the LOWEST set bit, not the highest.

Practice

Try the solution yourself

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

Editable code previewpublic int rangeBitwiseAnd(int left, int right) { int shift = 0; while (left < right) { left >>= 1; right >>= 1;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.

Iterating the whole range

With endpoints up to 2³¹, the range can hold billions of numbers; ANDing each one times out. The answer depends only on the endpoints' shared prefix.

Explore the code comparison

Don't write this

int result = left;
for (int i = left + 1; i <= right; i++) {  // TLE; also overflow at INT_MAX
    result &= i;
}
return result;

Write this instead

int shift = 0;
while (left < right) {
    left >>= 1;
    right >>= 1;
    shift++;
}
return left << shift;

Forgetting to restore the shifted bits

After shifting both endpoints until equal, the common value is the prefix WITHOUT its low bits. You must shift it back left by the shift count to zero-pad those positions.

Explore the code comparison

Don't write this

shift = 0
while left < right:
    left >>= 1
    right >>= 1
    shift += 1
return left  # missing the << shift -- returns the truncated prefix

Write this instead

shift = 0
while left < right:
    left >>= 1
    right >>= 1
    shift += 1
return left << shift

Wrong stopping condition in Brian Kernighan

Stripping while left <= right (instead of left < right) removes one bit too many, erasing a legitimate prefix bit and returning a value below the true AND.

Explore the code comparison

Don't write this

while left <= right:      # over-strips
    right &= right - 1
return right

Write this instead

while left < right:
    right &= right - 1
return right

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Common binary prefix of the endpoints

Code pattern to memorize

common-prefix:
    shift = 0
    while left < right:
        left >>= 1; right >>= 1; shift += 1
    return left << shift

brian-kernighan:
    while left < right: right &= right - 1
    return right

Rules to remember

1The answer is left and right's common high-bit prefix, with every lower bit set to 0.
2A bit that differs between left and right is necessarily 0 in the AND — somewhere in the range that bit flips to 0.
3Only the endpoints matter: if the top differing bit position is p, every bit at and below p clears; bits above p are identical and survive.
4Common-prefix method: right-shift both until equal (count shifts s), then result << s to restore the prefix.
5Brian Kernighan: right &= right - 1 strips right's lowest set bit each step; stop once right <= left.
6Watch for left == right (answer is left itself) and the full range where the result collapses to 0.

Use this pattern when

AND (or a monotone bit-erasing op) over a contiguous integer range
You need the bits guaranteed common to every number in [left, right]
Reasoning about how a bit behaves across consecutive integers (toggling/carry patterns)
Any 'find the shared high-order prefix of two numbers' subproblem

Choose another pattern when

AND over an arbitrary (non-contiguous) set of numbers → just fold the AND, no prefix shortcut
OR or XOR over a range → different bit behavior, different analysis
Range is given as an explicit small list → loop and AND directly
You need per-number bits, not the aggregate → no collapse to a prefix

Interview takeaway

ANDing a whole contiguous range is secretly a 'common prefix' problem: low bits churn through 0 across consecutive integers and die, only the shared high bits survive. Shifting both endpoints until they meet finds that prefix in O(log n); Brian Kernighan reaches the same answer by erasing right's low set bits. Either way, never loop the range — it can span billions.

Continue

Transfer the pattern to another problem

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

Transferable patternReduce a range-AND to the endpoints' common binary prefix. Whenever you AND a contiguous integer range, the churning low bits clear and only the shared high prefix survives — find it by shifting both endpoints until equal, or by stripping right's low set bits with Brian Kernighan (x & (x-1)). Both are O(log n). Related bit-structure problems: Number of 1 Bits, Counting Bits, Single Number II.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
Brian Kernighan again — count how many times x & (x-1) can clear a set bit before x hits 0.
Counting Bits
Bit-structure DP over a range; relates each number's popcount to a shifted/cleared predecessor.
Hamming Distance
Coming soon
Compare two numbers' bits — XOR then popcount; a cousin of reasoning about shared vs differing bits.
Single Number II
Coming soon
Per-bit reasoning across a set of numbers — count each bit position modulo 3.

Same pattern

←

Add Binary

Continue · Next problem

Gray Code Generation

mediumBit ManipulationLC #201Sometimes asked

Bitwise AND of Numbers Range

LCPractice

Bit Manipulation · 8 of 20 · 9 min

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

In plain English

Examples

Example 1

Input: left = 5, right = 7
Output: 4
Note: 5=101, 6=110, 7=111. AND: 101 & 110 & 111 = 100 = 4. Only the top bit (4) is set in all three; the lower bits differ and clear.

Example 2

Input: left = 0, right = 0
Output: 0
Note: Single-number range; the AND is 0 itself.

Example 3

Input: left = 1, right = 2147483647
Output: 0
Note: The range spans across powers of two, so every bit toggles somewhere and clears — the common prefix is empty, giving 0.

Constraints

0 ≤ left ≤ right ≤ 2³¹ − 1

Clarifying questions4First question: How large can the range be?Explore questions

Q1.How large can the range be?
Endpoints up to 2³¹ − 1, so the range can contain billions of numbers. Iterating every value is far too slow — we need a bit-structural shortcut.
Q2.Can left equal right?
Yes. Then the 'range' is a single number and the AND is just that number. Both methods handle it: the while loop never runs, returning left/right unchanged.
Q3.Can left be 0?
Yes. If left is 0 and right > 0, the answer is 0 — 0 ANDed with anything is 0. The prefix method returns 0 because the endpoints share no leading prefix above the differing bits.
Q4.Are these unsigned or signed integers?
Non-negative (0 ≤ left ≤ right ≤ 2³¹ − 1), so they fit in a signed 32-bit int and all shifts are logical/positive. In Java use >> safely since values are non-negative; >>> also works.

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

Where candidates slip

Looping i from left to right ANDing each value (TLE for large ranges and risk of infinite loop at INT_MAX), or mishandling left == right / the all-zero collapse.

How to stand out

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	Brute Force — AND Every Number in the Range	`O(right − left)`	`O(1)`	Say it first to frame the problem, then immediately note it's O(range) and infeasible for the constraints.	Read
2	Common Binary Prefix — Shift Until Equal (Optimal)Optimal	`O(log(max))`	`O(1)`	The answer they want. Frame it as 'the AND is the shared high prefix; find it by shifting both endpoints together'.	Read
3	Brian Kernighan — Strip Right's Low Set Bits	`O(log(max))`	`O(1)`	Offer as an elegant alternative once you've explained the prefix idea — shows depth with bit tricks.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Why low bits die: 5,6,7 in binary

How to read it:The high prefix '1' is shared by all three; the lower two bits each take both values across the range, so they AND to 0.

Rendering diagram…

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 3

Brute Force — AND Every Number in the Range

TimeO(right − left)SpaceO(1)

Say it first to frame the problem, then immediately note it's O(range) and infeasible for the constraints.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal definition: start an accumulator at left, then AND in left+1, left+2, ..., up to right.

2Hint 2Explore hint

Estimate the cost: with endpoints up to 2³¹, the range can hold ~2 billion numbers — far too many to loop.

3Hint 3Explore hint

Also notice a subtle hazard: if right is INT_MAX, a `for (long i...)` or careless `int i <= right` can overflow or loop forever. Use this to motivate the bit shortcut.

A · Core idea

The most direct translation: fold the AND across the whole range.

B · Visual dry run

Interactive dry run

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

left = 5, right = 7

init

result = 5 (101)

Stateresult = 101

Final result4

C · Code with teaching comments

solution.javaJava

Brute Force — AND Every Number in the Range — reference

2 teaching notes

1
public int rangeBitwiseAnd(int left, int right) {
2
    int result = left;
3
    // Use a long counter so i <= right doesn't overflow when right == INT_MAX.
4
    for (long i = (long) left + 1; i <= right; i++) {
5
        result &= (int) i; // 'long i' avoids overflow when right == INT_MAX
6
    }
7
    return result;
8
}

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

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

E · Edge cases and pitfalls5left = 5, right = 5 — Loop body never executes; returns 5.Explore edge cases

Edge cases handled

left = 5, right = 5Loop body never executes; returns 5.
left = 0, right = 2³¹−1Correct result 0 but ~2 billion iterations — TLE; motivates the shortcut.

Pitfalls

Using `int i` with `i <= right` — overflows and loops forever when right == INT_MAX.
Assuming the range is small — it can be billions wide.
Treating O(range) as acceptable; it's the trap this problem sets.

03.2

Approach 2 of 3 · Optimal

Common Binary Prefix — Shift Until Equal (Optimal)

TimeO(log(max))SpaceO(1)

The answer they want. Frame it as 'the AND is the shared high prefix; find it by shifting both endpoints together'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at left and right in binary. Any bit position where they DIFFER — what must the AND of the whole range be at that position, and why?

2Hint 2Explore hint

3Hint 3Explore hint

Find that shared prefix: right-shift left and right together, counting shifts, until they're equal. Then shift the common value back left by the count to re-append the zeroed low bits.

A · Core idea

The key fact: the AND over `[left, right]` is exactly the longest common high-order bit prefix of `left` and `right`, padded with zeros in the low bits.

B · Visual dry run

Interactive dry run

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

left = 5, right = 7

Interactive diagram

Shifting endpoints to the common prefix

start

Active call / nodeSupporting contextReturned stateNot active

Both endpoints shift right together until equal; the shared value, shifted back, is the answer.

Final result4

C · Code with teaching comments

solution.javaJava

Common Binary Prefix — Shift Until Equal (Optimal) — optimal

4 teaching notes

1
public int rangeBitwiseAnd(int left, int right) {
2
    int shift = 0;
3
    // Keep dropping low bits until the two endpoints collapse to their shared prefix.
4
    while (left < right) {
5
        left >>= 1;
6
        right >>= 1;
7
        // Count how many low bits were discarded so we can zero-pad them back.
8
        shift++;
9
    }
10
    // left now equals the common prefix; shift it back left to append the cleared low
11
    // bits as zeros.
12
    return left << shift;
13
}

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

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

E · Edge cases and pitfalls7left = 0, right = 0 — left < right is false immediately; shift stays 0; return 0 << 0 = 0.Explore edge cases

Edge cases handled

left = 0, right = 0left < right is false immediately; shift stays 0; return 0 << 0 = 0.
left = right = 12Loop doesn't run; returns 12 — single-number range AND.
left = 1, right = 2³¹−1Endpoints share no high prefix; shifting collapses both to 0 → returns 0.
left = 6, right = 6Already equal → 6, no shifting.

Pitfalls

Shifting only one endpoint — they must move together to stay aligned.
Forgetting to shift the common value back left, returning the truncated prefix instead of the zero-padded result.
Using arithmetic right shift on negative values — not an issue here since inputs are non-negative.

03.3

Approach 3 of 3

Brian Kernighan — Strip Right's Low Set Bits

TimeO(log(max))SpaceO(1)

Offer as an elegant alternative once you've explained the prefix idea — shows depth with bit tricks.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Brian Kernighan's trick: `x & (x - 1)` clears the lowest set bit of x. How could clearing low set bits of `right` converge to the common prefix?

2Hint 2Explore hint

Repeatedly clear right's lowest set bit while right is still greater than left. Each clear removes a low bit that can't be in the AND.

3Hint 3Explore hint

Stop when right ≤ left; at that point right has had all its 'extra' low bits stripped and equals the common prefix. Return right.

A · Core idea

A second route to the same prefix, using Brian Kernighan's bit-clearing identity.

The identity. x & (x - 1) turns off the lowest set bit of x. For example right = 1100 → right & (right-1) = 1100 & 1011 = 1000: the lowest 1 is gone.

B · Visual dry run

Interactive dry run

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

left = 5, right = 7

Interactive diagram

Brian Kernighan stripping bits of right

right=7 (111)

Active call / nodeSupporting contextReturned stateNot active

Each step clears right's lowest set bit until right ≤ left; the survivor is the common prefix.

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rangeBitwiseAnd(int left, int right) { while (left < right) { right &= (right - 1); // clear right's lowest set bit } return right;Explore the full code

solution.javaJava

Brian Kernighan — Strip Right's Low Set Bits — reference

3 teaching notes

1
public int rangeBitwiseAnd(int left, int right) {
2
    // Keep stripping while right still exceeds left — those low set bits can't survive
3
    // the AND.
4
    while (left < right) {
5
        // Brian Kernighan: removes exactly one (the lowest) set bit of right per
6
        // iteration.
7
        right &= (right - 1); // clear right's lowest set bit
8
    }
9
    // Once right <= left it equals the common prefix — that's the range AND.
10
    return right;
11
}

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

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

ComplexityO(log(max)) time, O(1) space — Each step clears one set bit of right, and right has at most ~31 set bits, so the loop runs O(log(max)) times, each O(1). Constant space.

E · Edge cases and pitfalls6left = 0, right = 0 — 0 < 0 false → return 0 immediately.Explore edge cases

Edge cases handled

left = 0, right = 00 < 0 false → return 0 immediately.
left = right = 9Loop skipped, returns 9.
left = 0, right = 5Strip 5→4→0 (each clears a low bit) until right ≤ 0; returns 0.

Pitfalls

Using `<=` in the condition (`left <= right`) — over-strips and can wrongly return a value below the prefix.
Clearing left instead of right — left has no extra low bits above the prefix to remove.
Forgetting that `x & (x-1)` removes the LOWEST set bit, not the highest.

Practice

Try the solution yourself

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

Editable code previewpublic int rangeBitwiseAnd(int left, int right) { int shift = 0; while (left < right) { left >>= 1; right >>= 1;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.

Iterating the whole range

With endpoints up to 2³¹, the range can hold billions of numbers; ANDing each one times out. The answer depends only on the endpoints' shared prefix.

Explore the code comparison

Don't write this

int result = left;
for (int i = left + 1; i <= right; i++) {  // TLE; also overflow at INT_MAX
    result &= i;
}
return result;

Write this instead

int shift = 0;
while (left < right) {
    left >>= 1;
    right >>= 1;
    shift++;
}
return left << shift;

Forgetting to restore the shifted bits

After shifting both endpoints until equal, the common value is the prefix WITHOUT its low bits. You must shift it back left by the shift count to zero-pad those positions.

Explore the code comparison

Don't write this

shift = 0
while left < right:
    left >>= 1
    right >>= 1
    shift += 1
return left  # missing the << shift -- returns the truncated prefix

Write this instead

shift = 0
while left < right:
    left >>= 1
    right >>= 1
    shift += 1
return left << shift

Wrong stopping condition in Brian Kernighan

Stripping while left <= right (instead of left < right) removes one bit too many, erasing a legitimate prefix bit and returning a value below the true AND.

Explore the code comparison

Don't write this

while left <= right:      # over-strips
    right &= right - 1
return right

Write this instead

while left < right:
    right &= right - 1
return right

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Common binary prefix of the endpoints

Code pattern to memorize

common-prefix:
    shift = 0
    while left < right:
        left >>= 1; right >>= 1; shift += 1
    return left << shift

brian-kernighan:
    while left < right: right &= right - 1
    return right

Rules to remember

1The answer is left and right's common high-bit prefix, with every lower bit set to 0.
2A bit that differs between left and right is necessarily 0 in the AND — somewhere in the range that bit flips to 0.
3Only the endpoints matter: if the top differing bit position is p, every bit at and below p clears; bits above p are identical and survive.
4Common-prefix method: right-shift both until equal (count shifts s), then result << s to restore the prefix.
5Brian Kernighan: right &= right - 1 strips right's lowest set bit each step; stop once right <= left.
6Watch for left == right (answer is left itself) and the full range where the result collapses to 0.

Use this pattern when

AND (or a monotone bit-erasing op) over a contiguous integer range
You need the bits guaranteed common to every number in [left, right]
Reasoning about how a bit behaves across consecutive integers (toggling/carry patterns)
Any 'find the shared high-order prefix of two numbers' subproblem

Choose another pattern when

AND over an arbitrary (non-contiguous) set of numbers → just fold the AND, no prefix shortcut
OR or XOR over a range → different bit behavior, different analysis
Range is given as an explicit small list → loop and AND directly
You need per-number bits, not the aggregate → no collapse to a prefix

Interview takeaway

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

Number of 1 Bits
Brian Kernighan again — count how many times x & (x-1) can clear a set bit before x hits 0.
Counting Bits
Bit-structure DP over a range; relates each number's popcount to a shifted/cleared predecessor.
Hamming Distance
Coming soon
Compare two numbers' bits — XOR then popcount; a cousin of reasoning about shared vs differing bits.
Single Number II
Coming soon
Per-bit reasoning across a set of numbers — count each bit position modulo 3.

Same pattern

←

Add Binary

Continue · Next problem

Gray Code Generation