[Leetcode 201] Bitwise AND of Numbers Range

作者 Shilei Tian 日期 2017-01-11
[Leetcode 201] Bitwise AND of Numbers Range

题目要求

Given a range [m, n] where $0 \leq m \leq n \leq 2147483647$, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

解题思路

拿到这道题,我在想,该不会这么简单吧…很从容地写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int res = 2147483647;
for (int i = m; i <= n; ++i) {
res &= i;
if (res == 0) {
return 0;
}
}
return res;
}
};

果然一运行,提示超时,不过还不算是太惨,毕竟是 8266 个 case 通过了 8259 个。言归正传,这道题应该怎么高效地做呢?两个比特位,显然只有它们都是 1 的时候,AND 运算的结果才是 1。我们先把眼光放在最后一位,什么时候两位都是 1 呢?只有这两个数都是奇数的时候才可以。那我们任给一个范围 [m, n],如果 $m \neq n$,那么 mn 中必至少存在一个奇数一个偶数(这个稍微一寻思就是废话,最极端的情况下 $n=m+1$);如果 $m=n$ 的话,那么最低位的结果就等于 mn 最低位 AND 的结果了。那么倒数第二个数该怎么判断呢?因为二进制 AND 每一位都不互相影响,所以我们可以将倒数第二位移位到最低位,然后判断移位以后的数字是否相等,不等的话直接是 0。然后我们再将这个结果左移 1 位,就是第二位 AND 运算的结果了。以此类推,我们就可以得到下面的代码:

1
2
3
4
5
6
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;
}
};

仅仅只有一行而已,非常高效!