0201. Bitwise AND of Numbers Range

题目信息

题号:
  1. 数字范围按位与

难度:

Medium

主题:

位运算、二进制、连续区间

原题:

LeetCode 0201

重点:

从逐个相与推导到共同二进制前缀,利用连续区间一次清空全部变化低位

题目重述

给定非负整数 left、right,且 left <= right。闭区间 [left, right] 中的 每一个整数都要参加按位与,返回:left & (left + 1) & ... & right。

结果的一位要保留 1,区间内所有整数在这一位都必须是 1;只要存在一个整数该位为 0,结果的这一位就为 0。输入满足 0 <= left <= right <= 2^31 - 1,方法只接收 整数副本,不修改调用者可见的值。

自建示例

中间整数会否定端点看起来相同的位:

输入:left = 5,right = 7
区间:101、110、111
输出:100,即 4

端点的按位与是 101 & 111 = 101,但中间的 110 最低位为 0。因此只检查端点 不等于计算完整区间。

跨过更高进位边界时,会同时失去一段低位:

输入:left = 26,right = 30
区间:11010、11011、11100、11101、11110
输出:11000,即 24

单点区间没有额外整数可以清零:

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

C++ 实现

#include <cstdint>

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        return commonPrefixAnd(left, right);
    }

private:
    int enumerateInterval(int left, int right) {
        std::uint32_t answer = static_cast<std::uint32_t>(left);
        std::uint32_t upper = static_cast<std::uint32_t>(right);

        for (std::uint32_t value = answer + 1U;
             value <= upper && answer != 0U;
             ++value) {
            answer &= value;
        }

        return static_cast<int>(answer);
    }

    int commonPrefixAnd(int left, int right) {
        std::uint32_t low = static_cast<std::uint32_t>(left);
        std::uint32_t high = static_cast<std::uint32_t>(right);
        unsigned int removed = 0;

        while (low != high) {
            low >>= 1U;
            high >>= 1U;
            ++removed;
        }

        return static_cast<int>(low << removed);
    }

    int clearChangingSuffix(int left, int right) {
        std::uint32_t low = static_cast<std::uint32_t>(left);
        std::uint32_t high = static_cast<std::uint32_t>(right);

        while (low < high) {
            high &= high - 1U;
        }

        return static_cast<int>(high);
    }
};

题解

逐个相与保留了原始搜索空间

enumerateInterval 从 left 开始,把后续每个整数依次合并到 answer。这是直接遵循 题目定义的基线:每个区间成员恰好参与一次,按位与的结合顺序不影响结果,所以它不会遗漏任何 可能清零的位。answer 一旦为 0 可以停止,因为之后再相与不可能恢复 1。

但它仍按区间内整数数量工作。[2^30, 2^31 - 1] 接近十亿个数,且最高位始终为 1, 答案不会及早变成零;最坏时间仍是 O(right - left + 1)。真正重复的工作是:连续递增时, 同一位按固定进位规律反复出现 0、1,枚举法却逐个数确认。

端点相与没有代表中间状态

为了少看一些数,很自然会尝试 left & right。示例 [5, 7] 已经说明它不正确:最低位在 两个端点中都是 1,却在中间的 6 中为 0。端点相同只是“这位可能保留”的必要条件, 不是“区间中从未出现零”的充分条件。

失败处正是可利用的结构。区间不是任意一组整数,而是连续整数;中间值不是未知状态,而是由 二进制进位规则强制存在的状态。接下来不再问“每个数是多少”,而是问“区间跨过了哪一个最高 进位边界”。

最高差异位决定整个零后缀

从高位向右比较 left、right。设最长公共前缀为 P,第一次不同位之后还有若干低位:

left  = P 0 ...
right = P 1 ...

公共前缀 P 的每一位在整个区间中都不会改变。两个端点都处于以 P 开头的同一个二进制 块,介于它们之间的整数也无法离开这个块,因此这些高位按位与后仍等于 P。

第一次不同位在 left 中已经是 0,它必然被清掉。更低的位也不需要逐位枚举:区间从 P 0 ... 走到 P 1 ... 时,必然经过形如 P 1 000...000 的进位边界整数。该整数 在全部更低位都为 0,一次就给变化后缀的每一位提供了零见证。

所以答案只可能是“P 后补全零”。最高差异位不仅淘汰自己,还删除它右边所有低位的搜索; 这正是从区间宽度级工作缩减到位宽级工作的原因。

同步右移暴露共同前缀

commonPrefixAnd 不必显式定位最高差异位。每轮把 low、high 同时右移一位,相当于 从两个端点同步删除一个最低位;只要两者不同,说明还没删除完变化后缀。

循环执行 removed 轮后,low、high 分别等于原始 left、right 去掉最低 removed 位后的前缀。这个关系就是循环不变量。二者首次相等时,剩下的共同值恰好是 P; low << removed 把前缀放回原位,并在所有已删除位置补 0,正好得到区间按位与。

对 [26, 30] 的状态走读:

已删除位数

low

high

当前含义

0

11010

11110

仍有变化位

1

1101

1111

仍有变化位

2

110

111

仍有变化位

3

11

11

公共前缀已暴露

结束时 11 << 3 得到 11000。27、28、29 从未被实际访问;它们的影响已由“跨过最高 差异位”这一结构事实完整吸收。

清位法压缩右端状态

clearChangingSuffix 是同一结论的另一种实现。high & (high - 1) 会清除 high 最低 的一个 1。只要 low < high,当前 high - 1 仍位于原闭区间中,并在这个位置提供 0;该置位因此不可能留在最终答案,可以立即清除。

例如 [5, 7] 的 high 会经历 111 -> 110 -> 100。第二次清位后 100 < 101, 这不是越界错误:按位与的结果本来可以小于 left。该方案在置位较少时可能少做几轮,但它把 共同前缀隐藏在右端点的连续收缩中;主入口选择同步右移,是因为其状态与推导一一对应。

代码分析

三个私有函数对应三层认识。enumerateInterval 保留“每个整数都参加”的原始定义,用于显示 瓶颈而非主入口;commonPrefixAnd 删除与区间宽度成正比的循环,只保存两个缩短端点和 removed;clearChangingSuffix 则把一个真实的零见证直接变成一次右端清位。

主入口明确调用 commonPrefixAnd。代码将局部状态写成 std::uint32_t,使左右移始终表示 无符号二进制位;输入非负且答案不超过 2^31 - 1,最终转换回 int 是安全的。循环中必须 同时移动两端并随后递增 removed,否则计数就不再代表两个前缀共同删除的位数。

复杂度与边界

逐个相与的时间为 O(right - left + 1)、额外空间 O(1)。同步右移每轮删除一位,若有效 位宽为 W,时间为 O(W)、额外空间 O(1);本题最多处理 31 个有效位。清位法每轮 删除 high 的一个置位,最多同样进行 O(W) 次。

left == right 时同步右移不执行,直接返回该数。left == 0 或没有共同前缀时,两个状态 最终都会变成 0,答案自然为 0。三种方法均不分配与区间宽度相关的容器,也不修改输入。