跳至主要內容

0201. 数字范围按位与

ITCharge大约 3 分钟

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

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

题目链接

题目大意

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

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

说明

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

示例

  • 示例 1:
输入:left = 5, right = 7
输出:4
  • 示例 2:
输入:left = 1, right = 2147483647
输出:0

解题思路

思路 1:位运算

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

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

我们知道与运算的规则如下:

  • 0 & 0 == 0
  • 0 & 1 == 0
  • 1 & 0 == 0
  • 1 & 1 == 1

只有对应位置上都为 11 的情况下,按位与才能得到 11。而对应位置上只要出现 00,则该位置上最终的按位与结果一定为 00

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

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

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

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

  • x=31x = 31。则 left==rightleft == right,其按位与结果就是 leftleft 本身。
  • 0x<310 \le x < 31。这种情况下因为 left<rightleft < right,所以 leftleft 的第 x+1x + 1 位必然为 00rightright 的第 x+1x + 1 位必然为 11
    • 注意:leftleftrightrightx+1x + 1 位上不可能同为 0011,这样就是公共前缀了。
    • 注意:同样不可能是 leftleftx+1x + 1 位为 11rightrightx+1x + 1 位为 00,这样就是 left>rightleft > right 了。

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

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

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

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

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

具体计算步骤如下:

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

思路 1:位运算代码

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

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n)
  • 空间复杂度O(1)O(1)

参考资料