跳到主要内容

LeetCode 201. 数字范围按位与

本节目标

连续整数区间的按位与只保留两个端点共享的二进制前缀。

给定区间的两个端点，要求计算其中每个整数的按位与。连续区间会让低位不断变化；能留下的只有端点共享的高位前缀。这是位运算拓展中“公共二进制前缀”模型的母题。

查看原题

题意与约束​

给定非负整数 left 和 right，满足 0 <= left <= right <= 2^31 - 1，返回闭区间 [left, right] 内所有整数的按位与。

例如 [26, 30] 包含 26 & 27 & 28 & 29 & 30。接口为 C++ 的 int Solution::rangeBitwiseAnd(int left, int right) 和 Python 的 Solution.rangeBitwiseAnd(self, left, right)。

区间变化位为什么归零​

按位与的一位只要遇到过一个 0，结果就是 0。连续整数从 left 增加到 right 时，低位会因进位发生变化；某一位一旦在区间内出现过 0 和 1，它就不可能保留为 1。

不能直接枚举区间并不断按位与：区间长度最多接近 2^31，即使每次操作只需常数时间，也无法接受。我们需要直接找出不会变化的高位。

寻找公共二进制前缀​

让两个端点同时右移，直到它们相等。每右移一次，就舍去一位已经在区间中变化、因此答案必为 0 的低位；相等时留下的值正是两个端点的公共二进制前缀。

以 [26, 30] 为例：

26 = 11010       30 = 11110
13 =  1101       15 =  1111   （右移 1 次）
 6 =   110        7 =   111   （右移 2 次）
 3 =    11        3 =    11   （右移 3 次）

三次右移后相等为 11，说明只有这个前缀能在整个区间中保持不变。

移回原位​

右移了 shift 次，就把公共前缀左移 shift 次。被移除的低 shift 位全部补 0，恰好对应区间内发生变化的位。

上例中 11 << 3 = 11000，即 24。因此 [26, 30] 的按位与为 24。

代码实现​

两种语言都维护右移次数 shift。循环条件使用 left < right：端点相等时已找到公共前缀；left = right 的单元素区间不会进入循环，直接返回原数。

C++17
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            // 同时右移，剥离必然归零的变化位。
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
};

复杂度分析​

每轮消去一位，最多处理 31 位，因此时间复杂度为 O(log right)，在题目整数范围内等价于 O(1)；只使用常数个变量，空间复杂度为 O(1)。

易错点​

  • 枚举整个区间：范围可能接近 2^31，会超出可接受时间。
  • 只比较端点的最低位：变化位的结论来自整个连续区间，应逐层右移直到端点相等。
  • 忘记记录右移次数：公共前缀必须左移回原来的高位位置。
  • 循环写成 left <= right：端点相等时仍会继续右移，丢失本应保留的前缀。

模式迁移​

看到“连续整数区间的按位与”时，先问哪些低位会因进位变化；答案就是端点公共二进制前缀后补零。更多何时适用公共前缀、何时应转向逐位统计或移位倍增，参见位运算拓展。