题目来源
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
看到这道题的最初想法是，取最小的那个数，依次判断该数在某一位上是否为1，是的话就遍历另外的数，假如都为1则该位为1，否则为0。
可以AC，不过注意一下假如m是2147483647的话for循环里的m+1会溢出，不过在前面加个判断的话就不会有问题了。
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int res = 0;
int base = 1;
if (m == n)
return m;
while (m > 0) {
if (m % 2 == 1) {
int label = true;
for (int i=m+1; i<=n; i++)
if (i % 2 != 1) {
label = false;
break;
}
if (label)
res += base;
}
base *= 2;
m /= 2;
n /= 2;
}
return res;
}
};
看了看讨论区，然后感觉智商又被碾压了==
不多说了，看下面的代码吧…
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
return (n > m) ? (rangeBitwiseAnd(m >> 1, n >> 1) << 1) : m;
}
};
真的不带这样欺负人的…
平复下心情，假如n>m的话，最低位肯定是0，因为最低位至少有一个0。
当然你也可以把它改为非递归的，然后速度会快一些。如下：
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int trans = 0;
while(m != n)
{
++ trans;
m >>= 1;
n >>= 1;
}
return m << trans;
}
};
