跳至主要內容

201. 数字范围按位与


201. 数字范围按位与open in new window

🟠   🔖  位运算  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你两个整数 leftright ,表示区间 [left, right],返回此区间内所有数字 按位与 的结果(包含 leftright 端点)。

解题思路

直接遍历范围内的每个数字会非常低效,因此需要更高效的解决方案。

可以先找到 mn 的公共前缀,并利用位运算特性,高效地计算出范围内所有整数的按位与结果。

  1. 位运算特性

    • 按位与操作会将数字的某些位清零,当两个数字的某一位不同(即一个是 0,另一个是 1)时,该位的结果必为 0
    • 在某些情况下,随着数字的增加,某些低位会变为 0,而高位则保持不变。
  2. 找到公共前缀

    • mn 逐位比较,直到它们的值相等,记录下公共前缀。
    • 这个公共前缀就是在范围内所有数字的按位与结果的高位部分。
  3. 右移操作

    • mn 不相等时,持续右移这两个数字,直到它们相等。每次右移都会消除最低位,帮助找到公共前缀。
    • 记录右移的次数,以便最终将公共前缀左移回原位。

复杂度分析

  • 时间复杂度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最长优雅子数组open in new window位运算 数组 滑动窗口