当前位置: 面试刷题>> 数字范围按位与(经典算法150题)


题目描述补充

题目:数字范围按位与

给定一个范围 [left, right] 表示一个闭区间内的所有整数,其中 0 ≤ left ≤ right ≤ 2^31 - 1,计算并返回该范围内所有数字的按位与(bitwise AND)结果。

示例 1:

输入: [5,7]
输出: 4
解释:
5: 101
6: 110
7: 111
按位与结果: 100,即 4

示例 2:

输入: [0]
输出: 0

示例 3:

输入: [1,2147483647]
输出: 0
解释: 最大的数是 2147483647,其二进制表示是 31 个 1。与任何数进行按位与操作,结果都将是 0。

解题思路

这个问题可以通过观察数字的二进制表示来解决。一般来说,如果 leftright 相差很远,那么大部分位上的数字都会不同,按位与的结果很可能是 0。但如果 leftright 在某个前缀之后才开始不同,那么前缀部分的按位与结果就是这个问题的解。

一个高效的算法是找到 leftright 最高位开始不同的位置,这个位置之前的所有位都是相同的,并且这些位就是我们要找的答案。

PHP 代码示例

function rangeBitwiseAnd($left, $right) {
    $shift = 0;
    // 找到 left 和 right 最高位开始不同的位置
    while ($left < $right) {
        $left >>= 1;
        $right >>= 1;
        $shift++;
    }
    // 将 left 左移回原来的位置,因为我们已经右移了 shift 位
    return $left << $shift;
}

// 示例测试
echo rangeBitwiseAnd(5, 7);  // 输出 4
echo "\n";
echo rangeBitwiseAnd(0, 0);  // 输出 0
echo "\n";
echo rangeBitwiseAnd(1, 2147483647);  // 输出 0

Python 代码示例

def rangeBitwiseAnd(left, right):
    shift = 0
    # 找到 left 和 right 最高位开始不同的位置
    while left < right:
        left >>= 1
        right >>= 1
        shift += 1
    # 左移回原来的位置
    return left << shift

# 示例测试
print(rangeBitwiseAnd(5, 7))  # 输出 4
print(rangeBitwiseAnd(0, 0))  # 输出 0
print(rangeBitwiseAnd(1, 2147483647))  # 输出 0

JavaScript 代码示例

function rangeBitwiseAnd(left, right) {
    let shift = 0;
    // 找到 left 和 right 最高位开始不同的位置
    while (left < right) {
        left >>>= 1;
        right >>>= 1;
        shift++;
    }
    // 左移回原来的位置
    return left << shift;
}

// 示例测试
console.log(rangeBitwiseAnd(5, 7));  // 输出 4
console.log(rangeBitwiseAnd(0, 0));  // 输出 0
console.log(rangeBitwiseAnd(1, 2147483647));  // 输出 0

在这些示例中,我们利用了位运算的右移(>>=>>>=)和左移(<<)来高效地找到并计算答案。这种方法避免了遍历整个范围,从而提高了算法的效率。

推荐面试题