"
public int rangeBitwiseAnd(int m, int n) {
while(m
//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDEyOTc4MA==.html
return n;}
The key point: reduce n by removing the rightest '1' bit until n<=m;
(1)if n>m,suppose m = yyyzzz, n = xxx100, because m is less than n, m can be equal to three cases:
(a) xxx011 (if yyy==xxx)
(b) less than xxx011 (if yyy==xxx)
(c) yyyzzz (if yyy
for case (a), and (b), xxx011 will always be ANDed to the result, which results in xxx011 & xxx100 = uuu000(uuu == yyy&xxx == xxx);
for case (c), xxx000/xxx011 will always be ANDed to the result, which results in yyyzzz & xxx000 & xxx011 & xxx100 = uuu000 (uuu <= yyy & xxx)
=> for any case, you will notice that: rangBitWiseAnd(vvvzzz,xxx100) == uuu000 == rangBitWiseAnd(vvvzzz,xxx000), (not matter what the value of""uuu"" will be, the last three digits will be all zero)
=> This is why the rightest '1' bit can be removed by : n = n & (n-1);
(2)when n==//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDEyNTU0MA==.html
m, obviously n is the result.(3)when n < m, suppose we reduce n from rangBitWiseAnd(yyyzzz,xxx100) to rangBitWiseAnd(yyyzzz,xxx000);
i) xxx100 >yyyzzz => xxx >= yyy;
ii) xxx000 xxx <= yyy;
=> xxx == yyy;
=> rangBitWiseAnd(yyyzzz,xxx000) == rangeBitWiseAnd(xxxzzz,xxx000);
=>result is xxx000, which is also n;
转自 charlie.chen 的回答
通过不断削减最右的位数直到n的值小于等于m,此时就能得到想要的值
似乎是默认了返回值一定是小于等于m的一个数,所以对n进行按位减少直到小于等于m
当n>m时可以证明rangBitWiseAnd(yyyzzz,xxx100) 与 rangBitWiseAnd(yyyzzz,xxx000) 结果一定相同,从而削减n
对比自己的拙劣代码:
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
if(m == 0){
return 0;
}
int p = 1;
int ret = 0;
for (int i = 2; i/2 0;) {
if (m%i >= i/2 && n%i <= i - 1 && n % i >= m % i && n-m <= i/2-1)
ret += i / 2;
i = i * 2;
if (i < 0)
if (m% 2147483648 >= 1073741824 && n% 2147483648 <= 2147483647 && n % 2147483648 >= m % 2147483648 && n - m <= 1073741824 - 1)
ret += 1073741824;
}
return ret;
}
};
owensy的文章中对此也有相关分析
但实际上复杂度似乎并没有降低多少?甚至有提高?
"
