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``。三种方法均不分配与区间宽度相关的容器,也不修改输入。