題目來源
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.
看到這道題的最初想法是勒庄，取最小的那個數(shù)氛濒，依次判斷該數(shù)在某一位上是否為1，是的話就遍歷另外的數(shù)椎镣，假如都為1則該位為1皆的，否則為0。
可以AC，不過注意一下假如m是2147483647的話for循環(huán)里的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;
}
};
看了看討論區(qū)，然后感覺智商又被碾壓了==
不多說了彤叉，看下面的代碼吧…
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
return (n > m) ? (rangeBitwiseAnd(m >> 1, n >> 1) << 1) : m;
}
};
真的不帶這樣欺負(fù)人的…
平復(fù)下心情庶柿，假如n>m的話，最低位肯定是0秽浇，因為最低位至少有一個0浮庐。
當(dāng)然你也可以把它改為非遞歸的，然后速度會快一些柬焕。如下：
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int trans = 0;
while(m != n)
{
++ trans;
m >>= 1;
n >>= 1;
}
return m << trans;
}
};
