201. 数字范围按位与

Medium

题目描述

给你两个整数 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³¹ - 1

解题思路

解题思路

这道题要求计算区间内所有数字的按位与结果。如果直接遍历区间内每个数字进行按位与操作，会超时。我们需要从位运算的性质入手分析。

核心观察： 对于二进制的某一位，如果在区间 [left, right] 中存在某个数字的该位为 0，那么最终按位与的结果在该位上必然为 0。

关键洞察：

1. 如果 left 和 right 在某一位上不同，那么在区间内必然存在该位为 0 和为 1 的数字，所以最终结果该位为 0
2. 只有当 left 和 right 在高位部分完全相同时，这些位才可能在最终结果中保持为 1

解法一：找公共前缀 不断将 right 的最低位置 0（右移再左移），直到 right <= left。此时的 right 就是答案。

解法二：移位法 同时右移 left 和 right，直到它们相等，记录移位次数，然后将相等的值左移相同次数。

解法三：消除最低位差异 重复执行 right = right & (right - 1) 来消除 right 的最低位 1，直到 right <= left。

推荐使用解法一，思路最直观且代码简洁。

代码实现

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            right = right & (right - 1);
        }
        return right;
    }
};

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right = right & (right - 1)
        return right

public class Solution {
    public int RangeBitwiseAnd(int left, int right) {
        while (left < right) {
            right = right & (right - 1);
        }
        return right;
    }
}

var rangeBitwiseAnd = function(left, right) {
    while (left < right) {
        right = right & (right - 1);
    }
    return right;
};

复杂度分析

相关题目

• . Longest Nice Subarray (Medium)