201. 数字范围按位与
201. 数字范围按位与
题目
Given two integers left
and right
that represent the range [left, right]
, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: left = 5, right = 7
Output: 4
Example 2:
Input: left = 0, right = 0
Output: 0
Example 3:
Input: left = 1, right = 2147483647
Output: 0
Constraints:
0 <= left <= right <= 2^31 - 1
题目大意
给你两个整数 left
和 right
,表示区间 [left, right]
,返回此区间内所有数字 按位与 的结果(包含 left
、right
端点)。
解题思路
直接遍历范围内的每个数字会非常低效,因此需要更高效的解决方案。
可以先找到 m
和 n
的公共前缀,并利用位运算特性,高效地计算出范围内所有整数的按位与结果。
位运算特性:
- 按位与操作会将数字的某些位清零,当两个数字的某一位不同(即一个是
0
,另一个是1
)时,该位的结果必为0
。 - 在某些情况下,随着数字的增加,某些低位会变为
0
,而高位则保持不变。
- 按位与操作会将数字的某些位清零,当两个数字的某一位不同(即一个是
找到公共前缀:
- 将
m
和n
逐位比较,直到它们的值相等,记录下公共前缀。 - 这个公共前缀就是在范围内所有数字的按位与结果的高位部分。
- 将
右移操作:
- 在
m
和n
不相等时,持续右移这两个数字,直到它们相等。每次右移都会消除最低位,帮助找到公共前缀。 - 记录右移的次数,以便最终将公共前缀左移回原位。
- 在
复杂度分析
- 时间复杂度:
O(log(max(m, n)))
,因为在最坏情况下,我们最多需要右移 32 次(对于 32 位整数)。 - 空间复杂度:
O(1)
,只使用了常数级别的额外空间。
代码
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
var rangeBitwiseAnd = function (left, right) {
let shift = 0;
// 找到 left 和 right 的公共前缀
while (left < right) {
left = left >> 1; // 右移 left
right = right >> 1; // 右移 right
shift++; // 记录右移的次数
}
// 将公共前缀左移回原位
return left << shift;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2401 | 最长优雅子数组 | 位运算 数组 滑动窗口 |