0201. 数字范围按位与 #
- 标签:位运算
- 难度:中等
题目大意 #
描述:给定两个整数 $left$ 和 $right$,表示区间 $[left, right]$。
要求:返回此区间内所有数字按位与的结果(包含 $left$、$right$ 端点)。
说明:
- $0 \le left \le right \le 2^{31} - 1$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:位运算 #
很容易想到枚举算法:对于区间 $[left, right]$,如果使用枚举算法,对区间范围内的数依次进行按位与操作,最后输出结果。
但是枚举算法在区间范围很大的时候会超时,所以我们应该换个思路来解决这道题。
我们知道与运算的规则如下:
0 & 0 == 0
0 & 1 == 0
1 & 0 == 0
1 & 1 == 1
。
只有对应位置上都为 $1$ 的情况下,按位与才能得到 $1$。而对应位置上只要出现 $0$,则该位置上最终的按位与结果一定为 $0$。
那么我们可以先来求一下区间所有数对应二进制的公共前缀,假设这个前缀的长度为 $x$。
公共前缀部分因为每个位置上的二进制值完全一样,所以按位与的结果也相同。
接下来考虑除了公共前缀的剩余的二进制位部分。
这时候剩余部分有两种情况:
- $x = 31$。则 $left == right$,其按位与结果就是 $left$ 本身。
- $0 \le x < 31$。这种情况下因为 $left < right$,所以 $left$ 的第 $x + 1$ 位必然为 $0$,$right$ 的第 $x + 1$ 位必然为 $1$。
- 注意:$left$、$right$ 第 $x + 1$ 位上不可能同为 $0$ 或 $1$,这样就是公共前缀了。
- 注意:同样不可能是 $left$ 第 $x + 1$ 位为 $1$,$right$ 第 $x + 1$ 位为 $0$,这样就是 $left > right$ 了。
而从第 $x + 1$ 位起,从 $left$ 到 $right$。肯定会经过 $10000…$ 的位置,从而使得除了公共前缀的剩余部分(后面的 $31 - x$ 位)的按位与结果一定为 $0$。
举个例子,$x = 27$,则除了公共前缀的剩余部分长度为 $4$。则剩余部分从 $0XXX$ 到 $1XXX$ 必然会经过 $1000$,则剩余部分的按位与结果为 $0000$。
那么这道题就转变为了求 $[left, right]$ 区间范围内所有数的二进制公共前缀,然后在后缀位置上补上 $0$。
求解公共前缀,我们借助于 Brian Kernigham 算法中的 n & (n - 1)
公式来计算。
n & (n - 1)
公式:对 $n$ 和 $n - 1$ 进行按位与运算后,$n$ 最右边的 $1$ 会变成 $0$,也就是清除了 $n$ 对应二进制的最右侧的 $1$。比如 $n = 10110100_{(2)}$,进行n & (n - 1)
操作之后,就变为了 $n = 10110000_{(2)}$。
具体计算步骤如下:
- 对于给定的区间范围 $[left, right]$,对 $right$ 进行
right & (right - 1)
迭代。 - 直到 $right$ 小于等于 $left$,此时区间内非公共前缀的 $1$ 均变为了 $0$。
- 最后输出 $right$ 作为答案。
思路 1:位运算代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(\log n)$。
- 空间复杂度:$O(1)$。