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.

#201

Medium

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字按位与的结果（包含 left 、 right 端点）。示例 1：输入： left = 5, right = 7 输出： 4 示例 2：输入： left = 0, right = 0 输出：…

位运算

题目描述

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

输入：left = 5, right = 7
输出：4

示例 2：

输入：left = 0, right = 0
输出：0

示例 3：

输入：left = 1, right = 2147483647
输出：0

提示：

0 <= left <= right <= 2³¹ - 1

lightbulb

解题思路

方法一：位运算

题目可以转换为求数字的公共二进制前缀。

当 $left \lt right$ 时，我们循环将 $right$ 的最后一个二进制位 $1$ 变成 $0$ ，直到 $left = right$ ，此时 $right$ 即为数字的公共二进制前缀，返回 $right$ 即可。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#191 位1的个数 #190 颠倒二进制位 #187 重复的DNA序列