LeetCode 201. 数字范围按位与
目录
题目描述
题意分析
给定闭区间
[left, right]，要求把区间里每一个整数按位与起来的结果算出来，不是求端点的与，而是求left & (left+1) & ... & right。
right最大到 $2^{31}-1$，区间长度可以达到十亿量级，所以「把区间里的数逐个与一遍」这条路直接被数据量否决了，必须找到一个只与两个端点有关的闭式规律。输入范围里
left可以等于right，此时答案就是这个数本身；left也可以是 0，只要区间包含 0，结果必然是 0。值域上界接近 int 最大值，意味着答案的位宽最多 31 位，任何按位处理的循环次数都是常数级，这是约束给出的最强信号：解法应该按二进制位而不是按数值个数来推进。
解法：公共前缀
核心思路
暴力做法是从
left循环到right逐个做与运算，正确但在left = 0, right = 2147483647时要循环二十亿次，瓶颈在于我们把「区间里有多少个数」当成了问题规模，而真正的规模应该是「数值有多少个二进制位」。换个角度观察某一个二进制位：如果第
k位在结果中要保留 1，那么区间里每一个数的第k位都必须是 1。而只要区间中存在某个数在第k位是 0，这一位就被清零了。再观察低位的行为：只要
left < right，区间里至少有两个相邻整数，相邻整数的最低位必然一个是 0 一个是 1，所以最低位一定会被清掉。把这个论证推广一层，区间跨度只要还没缩到 0，最低位就还会被清掉，于是可以不断把两端同时右移一位来消掉最低位。由此得到本题的不变量：答案等于
left与right的二进制公共前缀，后面补零。理由是公共前缀之后的第一个不同位上，left是 0 而right是 1，说明区间跨越了这一位的进位边界，于是从这一位往低的所有位在区间内都取遍了 0 和 1，全部会被与成 0；而公共前缀那些位上区间内所有数取值恒定，因而原样保留。循环中维护的量是「已经右移了多少位」的计数
shift，它的语义是「有多少个低位被判定为一定归零」，循环终止条件left == right表示剩下的高位已经完全一致，即找到了公共前缀。
解题步骤
- 初始化
shift = 0，用来记录被丢弃的低位数量。之所以要记录，是因为右移是有损操作，最后必须把公共前缀放回它原来的高位位置上，否则数值会缩小 $2^{shift}$ 倍。- 当
left < right时，把left和right同时右移一位，并让shift加一。之所以能同时右移，是因为两端不等就说明区间至少含两个相邻数，当前最低位必定同时出现 0 和 1，该位在答案中一定是 0，可以安全丢弃。- 循环退出时
left == right，此时的公共值就是原始两端的二进制公共前缀。之所以能保证退出，是因为每轮两个数都严格变小或相等，最坏情况下双双降到 0 就相等了，循环次数不超过 31 次。- 把
left << shift作为答案返回。之所以左移而不是直接返回，是因为被丢弃的那些低位在答案里都是 0，左移正好在低位补出对应数量的 0。以
left = 5, right = 7走一遍：初始left = 101₂，right = 111₂，shift = 0。第一轮5 < 7，右移得到left = 10₂ = 2，right = 11₂ = 3，shift = 1。第二轮2 < 3，右移得到left = 1，right = 1，shift = 2。此时两者相等，循环结束，返回1 << 2 = 4。人工核对：5 & 6 & 7 = 101₂ & 110₂ & 111₂ = 100₂ = 4，一致。再用
left = 0, right = 0检验边界：循环条件0 < 0直接为假，shift保持 0，返回0 << 0 = 0，正确。
代码实现
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(\log C)$，其中 $C$ 是数值上界。循环每轮把两个数各右移一位，
right至多有 31 个有效位，因此循环最多执行 31 次，与区间长度无关。- 空间复杂度：$O(1)$，全程只用了
shift一个额外整数，两个端点是在原变量上原地移位的。
关键点总结
- 当数据范围让「遍历元素」不可行、而值域位宽却很小时，要把问题规模从「元素个数」切换到「二进制位数」，这是位运算题最通用的降维手段。
- 与运算的单调性是核心武器：结果的某一位为 1 当且仅当所有参与数在该位都是 1，因此只要能证明某位上出现过 0，就能一次性判死这一位。
- 相邻整数最低位必然相反，这个微小事实是本题从 $O(n)$ 到 $O(\log C)$ 的全部支点，值得单独记住。
- 「区间按位与等于两端的二进制公共前缀」是可以直接复用的结论，同类问题（区间按位或、区间异或前缀和）都可以先问「答案是否只取决于端点」。
- 面试视角：面试官通常想听到你先说出暴力解并主动指出它会超时，再用一两个具体例子（比如 5、6、7）归纳出公共前缀，最后才写那五行代码。直接默写移位循环而讲不清为什么低位会被清零，会被认为是背题。
易错点总结
- 误以为答案是
left & right：用例left = 5, right = 7，5 & 7 = 5，但正确答案是 4，因为漏掉了中间的 6 把第 0 位清零。- 写成
for (int i = left; i <= right; i++) ans &= i：用例left = 0, right = 2147483647，循环二十亿次直接超时，且i <= right在right为Integer.MAX_VALUE时会因溢出变成死循环。- 循环条件写成
left != right：用例left = 7, right = 5（若上游未保证有序），两数永远不会在移位中相遇为同一路径，会多绕一圈甚至越过零点，改用left < right才有单调收敛保证。- 忘记最后左移，直接返回
left：用例left = 5, right = 7，会返回公共前缀 1 而不是 4，答案小了 $2^{shift}$ 倍。- 把
shift累加写在if分支里或漏加：用例left = 5, right = 7，shift停在 1，返回1 << 1 = 2，比正确答案 4 小一半。- Java 里用无符号右移和有符号右移混写，例如
left >>= 1配right >>>= 1：本题输入都是非负数时结果相同，但一旦有人复用这段代码处理负数，两个端点的移位语义不一致会得到完全错误的公共前缀。- Go 里把
shift声明成uint之外的类型后又与int混用移位：用例left = 5, right = 7，编译期就会因类型不匹配失败，shift := 0保持int才能直接参与left << shift。- 特判写成
if (left == 0) return 0之后就不再处理其余情况：用例left = 1, right = 2，正常流程本就能返回 0，多余特判并不错但会让人误以为还需要更多特判，反而在left = 0, right = 0这类输入上写出重复分支。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 191. 位1的个数 | 简单 | 单个数的逐位统计，用 n & (n-1) 消最低位 1 |
| 190. 颠倒二进制位 | 简单 | 位的重排而非位的消除，需要固定 32 轮取位再拼装 |
| 338. 比特位计数 | 简单 | 把位运算和递推结合，用 dp[i] = dp[i>>1] + (i&1)
|
| 477. 汉明距离总和 | 中等 | 按位拆分后统计每位 0/1 个数相乘，是逐位独立求和 |
| 371. 两整数之和 | 中等 | 用异或与进位模拟加法，考察对进位传播的手工推导 |