LeetCode 201. 数字范围按位与

约 3 分钟
文章信息 8 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 面试经典 150 题 字节 旷视
标签
位运算

题目描述

✅ 201. 数字范围按位与

image-20260928231605565

题意分析

计算闭区间 [left, right] 内所有整数的按位与。某一位只有在区间中每个数的这一位都是 1 时才会保留，只要出现过一个 0 就会清零；因此只计算两个端点的与并不够。

解法：公共前缀

核心思路

[!blue]

若两个端点不同，设它们从高到低的公共二进制前缀为 P。在紧接着的最高不同位上，较小的 left 一定是 0，较大的 right 一定是 1。区间中的数都处于这两个端点之间，所以更高的公共前缀不会改变，按位与后仍保留 P。

剩余各位分两部分证明：最高不同位在 left 中已经是 0，因此结果的这一位为 0；它后面的低位，则由区间中的进位边界数字 P100...0 清零。这个数字大于 P0... 形式的 left，且不大于 P1... 形式的 right，确实位于区间内。它的最高不同位是 1，但之后所有低位都是 0，足以清除这些低位。

所以答案是公共前缀后接全 0。同步右移两个端点，直到它们相等，就删去了最高不同位及其后的全部低位；shift 记录删去了多少位。最后将公共值左移 shift 位，恢复原来的位置，并在被删除的位置补 0。

若一开始 left == right，区间只有一个数，无需移位，直接返回它。端点均为非负数且不超过 2^31-1，同步右移最多 31 次一定相等。

解题步骤

  1. 初始化 shift = 0。
  2. 两端不等时，都右移一位，并将 shift 加一。
  3. 两端相等时，剩下的值就是公共前缀，返回 left << shift。

代码实现

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;

        // 端点仍不同时丢弃必为零的低位，直到留下公共前缀
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }

        // 将公共前缀放回原位置，被丢弃的低位统一补零
        return left << shift;
    }
}

func rangeBitwiseAnd(left int, right int) int {
    shift := 0
    // 端点仍不同时丢弃必为零的低位，直到留下公共前缀
    for left < right {
        left >>= 1
        right >>= 1
        shift++
    }
    // 将公共前缀放回原位置，被丢弃的低位统一补零
    return left << shift
}

复杂度分析

  • 时间复杂度：最多处理三十一位，固定输入宽度下为 $O(1)$。
  • 空间复杂度：$O(1)$，移位计数。

关键点总结

[!green]

  • 最高不同位由左端点的 0 清除，其后低位由区间内进位边界数字的 0 清除。
  • 端点相同时不移位，直接返回该数。

易错点总结

[!yellow]

  • 只返回两个端点的与，会漏掉中间数清除的位。
  • 忘记左移复原，返回的是缩短的公共前缀。
  • 逐数扫描，复杂度受区间长度而非位宽影响。

相似题目

题目 难度 关联与区别
191. 位1的个数 简单 清除最低位1的操作也可用于不断缩小右端值，直到区间只剩公共高位。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/99987536
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！