201. 数字范围按位与

🟠   🔖  位运算  🔗 LeetCode

题目

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 的公共前缀，并利用位运算特性，高效地计算出范围内所有整数的按位与结果。

1. 位运算特性：

   • 按位与操作会将数字的某些位清零，当两个数字的某一位不同（即一个是 0，另一个是 1）时，该位的结果必为 0。
   • 在某些情况下，随着数字的增加，某些低位会变为 0，而高位则保持不变。

2. 找到公共前缀：

   • 将 m 和 n 逐位比较，直到它们的值相等，记录下公共前缀。
   • 这个公共前缀就是在范围内所有数字的按位与结果的高位部分。

3. 右移操作：

   • 在 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	最长优雅子数组		位运算 数组 滑动窗口