Article / 文章
LeetCode 第201题：数字范围按位与
给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字按位与的结果（包含 left 、right 端点）。
题目描述
给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字按位与的结果（包含 left 、right 端点）。
难度
中等
题目链接
示例
示例 1：
输入：left = 5, right = 7
输出：4示例 2：
输入：left = 0, right = 0
输出：0示例 3：
输入：left = 1, right = 2147483647
输出：0提示
0 <= left <= right <= 2^31 - 1
解题思路
方法一：位移法
这个问题的核心在于找出给定范围内所有数字的公共前缀，即最高位的相同部分。
关键点：
- 如果我们将范围内所有数字进行按位与操作，那么只有在所有数字的某一位都为1时，结果的该位才为1
- 在范围[left, right]中，如果left < right，从最低位开始，一定存在某些位会出现0和1的交替
- 所以最终的结果就是left和right的公共前缀，后面接上0
算法步骤：
- 将left和right同时右移，直到它们相等
- 记录右移的次数shift
- 将left左移回shift位，得到最终结果
时间复杂度：O(log n)，其中n为right的位数 空间复杂度：O(1)
方法二：Brian Kernighan算法
利用Brian Kernighan算法可以消除二进制中最右边的1，通过不断消除right中的1直到right小于等于left，最后再与left进行按位与操作。
关键点：
- 公式
n & (n-1)可以消除n中最右边的1 - 不断对right应用这个公式，直到right ≤ left
- 然后返回left & right
时间复杂度：O(log n) 空间复杂度：O(1)
代码实现
C# 实现
方法一：位移法
public class Solution {
public int RangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
}方法二：Brian Kernighan算法
public class Solution {
public int RangeBitwiseAnd(int left, int right) {
while (right > left) {
// 消除right中最右边的1
right = right & (right - 1);
}
return right;
}
}Python 实现
方法一：位移法
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
# 找到公共前缀
while left < right:
left >>= 1
right >>= 1
shift += 1
return left << shift方法二：Brian Kernighan算法
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
while right > left:
# 消除right中最右边的1
right = right & (right - 1)
return rightC++ 实现
方法一：位移法
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
// 找到公共前缀
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
};方法二：Brian Kernighan算法
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
while (right > left) {
// 消除right中最右边的1
right = right & (right - 1);
}
return right;
}
};性能分析
各语言实现的性能对比：
| 实现语言 | 方法 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|---|
| C# | 方法一 | 36 ms | 15.1 MB | 代码简洁，易于理解 |
| C# | 方法二 | 40 ms | 15.2 MB | 利用位操作特性 |
| Python | 方法一 | 44 ms | 14.8 MB | 可读性好 |
| Python | 方法二 | 48 ms | 14.9 MB | 算法更为巧妙 |
| C++ | 方法一 | 4 ms | 5.9 MB | 性能出色 |
| C++ | 方法二 | 4 ms | 6.0 MB | 无显著性能差异 |
补充说明
代码亮点
- 两种方法都很简洁，只需要几行代码就能解决问题
- 位操作具有很高的效率，特别适合这类问题
- 方法二巧妙地利用了Brian Kernighan算法的特性
- 两种方法都避免了暴力枚举，大大提高了效率
遍历问题解释
当范围[left, right]较大时，如果使用暴力枚举法（即计算范围内所有数字的按位与），将会导致超时，因为：
- 暴力枚举的时间复杂度为O(right-left)
- 当right-left很大时，计算量会变得非常大
而位移法和Brian Kernighan算法的时间复杂度都是O(log n)，即与范围内的数值大小的对数成正比，而不是与范围的宽度成正比，因此效率大大提高。
常见错误
- 没有正确处理边界情况，如left=0或right=0
- 忽略了在某些情况下，如left=right，可以直接返回left
- 在位移操作时没有考虑溢出问题
- 没有理解按位与操作的本质，导致解题思路错误