数字范围按位与如何求解？（LeetCode 201）

简化版

给两个整数 left、right，求区间 [left, right] 内所有数字按位与的结果。暴力逐个与会超时。核心洞察：结果等于 left 和 right 二进制的「公共前缀」，后面低位全补 0。因为区间里数字连续变化，只要某一位在区间内发生过翻转，那一位与出来必是 0；只有从高位起 left 和 right 完全相同的那段前缀能保留下来。做法：把 left、right 同步右移直到相等（找到公共前缀），再左移回去补 0。

详细版

解法一：找公共前缀（右移到相等）

int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left < right) {        // 同步右移，去掉不同的低位
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;         // 公共前缀左移补回 0
}

解法二：n & (n-1) 消 right 的低位 1

int rangeBitwiseAnd(int left, int right) {
    while (left < right) {
        right &= (right - 1);     // 消掉 right 最低位的 1
    }
    return right;                 // 消到 <= left 时即为公共前缀
}

结论：区间按位与 = left 与 right 的公共二进制前缀 + 低位补 0。
原理：区间内数字连续，任何在 [left,right] 内翻转过的低位，与结果必为 0。
复杂度：O(log n)（最多移 32 次）。

完整版教学

一、暴力为什么不行

直接 for (i = left; i <= right; i++) res &= i 在区间很大时（如 [0, 2^31-1]）要循环上亿次，超时。必须找规律，用位的性质 O(log n) 解决。

二、核心洞察：按位与的结果是「公共前缀」

按位与有个「一票否决」特性：某一位只要区间里出现过一个 0，这一位与出来就是 0。而区间 [left, right] 是连续整数，随着数字增大，低位会不断 0/1 翻转。关键问题是：哪些位在整个区间里始终不变（保持 1）？

答案：只有从最高位开始、left 和 right 相同的那段「公共前缀」。理由——

对于公共前缀之后的第一个「不同位」，left 是 0、right 是 1（因为 left < right）。区间从 left 走到 right，这一位必然从 0 变到 1，中间经过它翻转，所以这一位与出来是 0。
一旦某高位在区间内变化了，比它更低的所有位在这个变化点附近会取遍 0 和 1（连续计数的进位特性），低位也必然出现 0，与出来全是 0。

所以结果 = 公共前缀保持不变 + 后面所有低位补 0。

三、解法一：右移找公共前缀

既然要找 left 和 right 的公共前缀，就同步右移两者，每次砍掉最低位，直到 left == right——此时剩下的就是公共前缀部分。记录移了多少位 shift，最后把这个公共前缀左移 shift 位移回原来的高位、低位自动补 0，就是答案。

例：left = 5 = 101，right = 7 = 111。

右移 1 次：10 和 11，仍不等，shift=1。
右移 1 次：1 和 1，相等，shift=2。公共前缀是 1。
左移回：1 << 2 = 100 = 4。答案 4。✔（5&6&7 = 101&110&111 = 100）

四、解法二：`right & (right - 1)` 消低位 1

另一个巧解：不断用 right &= (right - 1) 消掉 right 最低位的 1，直到 right <= left。

原理：right & (right-1) 每次去掉 right 的一个最低位 1。当 right 被消到 <= left 时，它恰好变成了 left 和 right 的公共前缀（低位的 1 都被抹掉了）。这个写法更短，但解法一的「找公共前缀」更容易讲清楚原理，面试首选解法一。

五、易错点

误以为要逐个遍历：区间大时超时，必须用公共前缀规律。
忘记左移补回：解法一右移找到前缀后，一定要 left << shift 移回原位，否则结果偏小。
边界 left == right：区间只有一个数，while 不执行，直接返回 left（= right），正确。
负数/大数：本题 left、right 非负（题目范围 [0, 2^31-1]），用普通右移即可；若涉及负数需注意符号位，但本题不涉及。

六、用进位边界证明公共前缀

设 left=26=11010₂、right=30=11110₂。两端从高位看只有前两位 11 相同；第三位在区间内发生从 0 到 1 的进位，因此这一位及其右侧都不可能在所有数字中恒为 1。同步右移是在删除不稳定后缀，而不是在逐个计算区间元素。

26 = 11010, 30 = 11110, shift=0
13 = 01101, 15 = 01111, shift=1
 6 = 00110,  7 = 00111, shift=2
 3 = 00011,  3 = 00011, shift=3
公共前缀 3 左移 3 位：11000₂ = 24
校验：26 & 27 & 28 & 29 & 30 = 24

校验维度	本题必须保持的结论
循环/递推不变量	每次同步右移后，两数代表原端点去掉相同数量的低位；相等时剩余部分就是最长公共前缀。
边界条件	`left==right` 时循环零次；题目端点非负，因此算术右移不会引入负数符号问题。
复杂度与代价	最多删除 31 个低位，时间 O(log right)，空间 O(1)，与区间长度无关。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：每次同步右移后，两数代表原端点去掉相同数量的低位；相等时剩余部分就是最长公共前缀。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“26 = 11010, 30 = 11110, shift=0”开始手推，最后应得到“校验：26 & 27 & 28 & 29 & 30 = 24”。
边界复核：left==right 时循环零次；题目端点非负，因此算术右移不会引入负数符号问题。
代价复核：最多删除 31 个低位，时间 O(log right)，空间 O(1)，与区间长度无关。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“每次同步右移后，两数代表原端点去掉相同数量的低位；相等时剩余部分就是最长公共前缀。”这条正确性主线不能省。

八、常见误区与追问

误区：只计算 left & right 就等于区间按位与。 中间数字还可能把两端都为 1 的某个低位清零，不能省略连续区间条件。
误区：公共前缀之后仍可能保留零散的 1。 第一个不同高位跨越进位边界时，更低位会经历 0，因此按位与后全为 0。
误区：解法二循环结束条件必须是 right == left。 right 清低位 1 后可能直接小于 left，此时它已经是公共前缀补零的结果。
追问：区间 [0,right] 的结果为何恒为 0？ 区间包含 0，按位与任意一位都被 0 一票否决。
追问：为何同步右移最多执行固定位数次？ 每轮删除一位，32 位非负 int 最多处理 31 个有效数值位。
追问：这个规律能直接推广到区间按位或吗？ 按位或关注某位是否曾出现 1，判断逻辑不同，不能照搬“公共前缀后补 0”的结论。

九、加强记忆

数字范围按位与 = 求 left 与 right 的二进制公共前缀，低位补 0。原理：区间是连续整数，公共前缀之后的位在 [left,right] 内必翻转过，按位与「见 0 则 0」，故全为 0；只有从高位起始终不变的公共前缀能留存。解法一：left、right 同步右移到相等（找到前缀），再左移回补 0。解法二：right &= (right-1) 消 right 低位 1，直到 right <= left。O(log n)。核心一句：区间按位与就是公共前缀 + 低位清零。

简化版

详细版