#201

Medium

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Bitwise AND of Numbers Range

Use shared high bits and bit clearing to solve Bitwise AND of Numbers Range without scanning every value.

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right &= right - 1
        return right

Continue Practicing

#191 number of 1 bits #190 reverse bits #187 repeated dna sequences