How to Solve Bitwise AND of Numbers Range

The result of ANDing every number from left to right is the common binary prefix shared by both endpoints. Any bit that changes anywhere inside the range becomes 0, so the job is to remove unstable suffix bits until left and right match or repeatedly clear right's lowest set bit while it still exceeds left. For left = 5 and right = 7, the range 101, 110, 111 keeps only the leading 100, so the answer is 4.

Problem Statement

You are given two integers, left and right, defining an inclusive interval from left to right. Return the bitwise AND produced by combining every integer in that range, not just the two endpoints.

The key challenge is that even a short range can flip several low bits, and once a bit becomes both 0 and 1 somewhere inside the interval, that position is forced to 0 in the final answer. For example, when left = 5 and right = 7, the numbers 5, 6, and 7 share only the high bit pattern that leaves 4 after the full range AND.

Examples

Example 1

Input: left = 5, right = 7

Output: 4

Example details omitted.

Example 2

Input: left = 0, right = 0

Output: 0

Example details omitted.

Example 3

Input: left = 1, right = 2147483647

Output: 0

Example details omitted.

Constraints

• 0 <= left <= right <= 231 - 1

Solution Approach

Recognize that only the shared binary prefix survives

This problem is not about evaluating every value in the interval. In a range AND, any trailing bit position that changes across the interval is guaranteed to collapse to 0. What remains is the longest common prefix of left and right in binary, because higher bits stay fixed while lower bits cycle through both states.

Shift both endpoints until they become equal

A clean Bit Manipulation-driven solution is to right-shift left and right together until they match. Count how many shifts were needed, then left-shift the shared value back by that count. Those removed bits are exactly the unstable suffix that cannot survive the AND across the full range.

Use right &= right - 1 as an equivalent optimization

Another direct implementation keeps clearing the lowest set bit of right while right is still greater than left. Each clear removes a bit that cannot remain set once the interval spans past that boundary. This works because the final answer must be at most the stable prefix below the first differing bit.

Complexity Analysis

With the shared-prefix method, time is O(k) where k is the number of bits shifted before left and right meet, which is at most 31 for the given constraint range. Space is O(1) because the algorithm only updates a few integers. The bit-clearing variant is also O(k) in the number of cleared bits and stays O(1) space.

What Interviewers Usually Probe

• They want you to notice that iterating from left to right is the wrong model once the interval gets large.
• They expect you to explain why differing lower bits vanish, not just recite a shift loop.
• A strong answer connects the final value to the common binary prefix of left and right.

Common Pitfalls or Variants

Common pitfalls

• Looping through every number in the range times out conceptually and misses the actual Bit Manipulation pattern.
• Assuming the AND depends only on left & right ignores intermediate values that zero out extra bits.
• Forgetting that once the range crosses a power-of-two boundary, many lower bits immediately become unstable and drop to 0.

Follow-up variants

• Return the common binary prefix length instead of the final AND value.
• Handle many range AND queries, where preprocessing or trie-like bit grouping may become relevant.
• Generalize the reasoning to explain why range OR keeps unstable bits as 1 instead of 0.

How GhostInterview Helps

• GhostInterview identifies the shared-prefix insight early so you do not waste time proposing a full range scan.
• GhostInterview maps left = 5 and right = 7 into binary transitions and shows exactly which suffix bits die.
• GhostInterview suggests both accepted implementations, so you can pick shift-and-restore or repeated bit clearing.

Topic Pages

• Bit Manipulation

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main trick in Bitwise AND of Numbers Range?

The trick is to keep only the common high-bit prefix of left and right. Every lower bit that changes anywhere in the interval becomes 0 in the final AND.

Why does left = 5 and right = 7 return 4?

In binary, 5, 6, and 7 are 101, 110, and 111. The only bit pattern shared across all three numbers is 100, which equals 4.

Why is scanning the full range a bad approach for this problem?

The interval can be huge, and the real structure is bit stability, not accumulation. Once you see that unstable suffix bits always vanish, scanning adds work without adding insight.

How does the shared-prefix Bit Manipulation pattern work here?

Right-shift left and right until they become equal, counting the shifts. That equal value is the stable prefix, and shifting it back restores the answer with all unstable lower bits set to 0.

When does the answer become 0 immediately?

If left and right differ at a high enough position that the interval spans across many bit boundaries, the common prefix may be empty. For example, from 1 to 2147483647, every bit position flips somewhere in the range, so the result is 0.