0201. 数字范围按位与

0201. 数字范围按位与 #

  • 标签:位运算
  • 难度:中等

题目大意 #

描述:给定两个整数 leftright ,表示区间 [left, right]

要求:返回此区间内所有数字按位与的结果(包含 leftright 端点)。

说明

  • $0 \le left \le right \le 2^{31} - 1$。

示例

1
2
输入    left = 5, right = 7
输出    4

解题思路 #

思路 1:位运算 #

很容易想到枚举算法:对于区间 [left, right],如果使用枚举算法,对区间范围内的数依次进行按位与操作,最后输出结果。

但是枚举算法在区间范围很大的时候会超时,所以我们应该换个思路来解决这道题。

我们知道与运算的规则如下:0 & 0 == 00 & 1 == 01 & 0 == 01 & 1 == 1。只有对应位置上都为 1 的情况下,按位与才能得到 1。而对应位置上只要出现 0,则该位置上最终的按位与结果一定为 0

那么我们可以先来求一下区间所有数对应二进制的公共前缀,假设这个前缀的长度为 x

公共前缀部分因为每个位置上的二进制值完全一样,所以按位与的结果也相同。

接下来考虑除了公共前缀的剩余的二进制位部分。

这时候剩余部分有两种情况:

  • x = 31。则 left == right,其按位与结果就是 left 本身。
  • 0 <= x < 31。这种情况下因为 left < right,所以 left 的第 x + 1 位必然为 0right 的第 x + 1 位必然为 1
    • 注意:leftrightx + 1 位上不可能同为 01,这样就是公共前缀了。
    • 注意:同样不可能是 leftx + 1 位为 1rightx + 1 位为 0,这样就是 left > right 了。

而从第 x + 1 位起,从 leftright。肯定会经过 10000... 的位置,从而使得除了公共前缀的剩余部分(后面的 31 - x 位)的按位与结果一定为 0

举个例子,x = 27,则除了公共前缀的剩余部分长度为 4。则剩余部分从 0XXX1XXX 必然会经过 1000,则剩余部分的按位与结果为 0000

那么这道题就转变为了求 [left, right] 区间范围内所有数的二进制公共前缀,然后在后缀位置上补上 0

求解公共前缀,我们借助于 Brian Kernigham 算法中的 n & (n - 1) 公式来计算。

  • n & (n - 1) 公式:对 nn - 1 进行按位与运算后,n 最右边的 1 会变成 0,也就是清除了 n 对应二进制的最右侧的 1。比如 n = 10110100,进行 n & (n - 1) 操作之后,就变为了 n = 10110000

具体计算步骤如下:

  1. 对于给定的区间范围 [left, right],对 right 进行 right & (right - 1) 迭代。
  2. 直到 right 小于等于 left,此时区间内非公共前缀的 1 均变为了 0
  3. 最后输出 right 作为答案。

思路 1:位运算代码 #

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

参考资料 #

本站总访问量  次  |  您是本站第  位访问者