0201. Bitwise AND of Numbers Range
==================================
题目信息
--------
:题号: 0201. 数字范围按位与
:难度: Medium
:主题: 位运算、二进制、连续区间
:原题: `LeetCode 0201 `_
:重点: 从逐个相与推导到共同二进制前缀,利用连续区间一次清空全部变化低位
题目重述
--------
给定非负整数 ``left``、``right``,且 ``left <= right``。闭区间 ``[left, right]`` 中的
每一个整数都要参加按位与,返回:``left & (left + 1) & ... & right``。
结果的一位要保留 ``1``,区间内所有整数在这一位都必须是 ``1``;只要存在一个整数该位为
``0``,结果的这一位就为 ``0``。输入满足 ``0 <= left <= right <= 2^31 - 1``,方法只接收
整数副本,不修改调用者可见的值。
自建示例
--------
中间整数会否定端点看起来相同的位:
.. code-block:: text
输入:left = 5,right = 7
区间:101、110、111
输出:100,即 4
端点的按位与是 ``101 & 111 = 101``,但中间的 ``110`` 最低位为 ``0``。因此只检查端点
不等于计算完整区间。
跨过更高进位边界时,会同时失去一段低位:
.. code-block:: text
输入:left = 26,right = 30
区间:11010、11011、11100、11101、11110
输出:11000,即 24
单点区间没有额外整数可以清零:
.. code-block:: text
输入:left = 0,right = 0
输出:0
C++ 实现
--------
.. code-block:: cpp
#include
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(left);
std::uint32_t upper = static_cast(right);
for (std::uint32_t value = answer + 1U;
value <= upper && answer != 0U;
++value) {
answer &= value;
}
return static_cast(answer);
}
int commonPrefixAnd(int left, int right) {
std::uint32_t low = static_cast(left);
std::uint32_t high = static_cast(right);
unsigned int removed = 0;
while (low != high) {
low >>= 1U;
high >>= 1U;
++removed;
}
return static_cast(low << removed);
}
int clearChangingSuffix(int left, int right) {
std::uint32_t low = static_cast(left);
std::uint32_t high = static_cast(right);
while (low < high) {
high &= high - 1U;
}
return static_cast(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``,第一次不同位之后还有若干低位:
.. code-block:: text
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]`` 的状态走读:
.. list-table::
:header-rows: 1
* - 已删除位数
- 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``。三种方法均不分配与区间宽度相关的容器,也不修改输入。