题目描述:

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.

位运算题目. 两个数m与n, 从最高位开始往低位看的话, 前面的许多位是相同的, 从某一位开始变得不同, 而这之后的所有位在结果中必然为0(因为中间肯定出现了0和1). 我们把m和n相减后得到的值就是这个阈值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int minus = n - m + 1;
        int re = 0;
        for(int i = 0; i < 31; i++){
            int t = 1 << i;
            if(minus > t){
                re = re & (~t);
            }
            else{
                if((t & m) & (t & n)){
                    re = re | t;
                }
                else{
                    re = re & (~t);
                }
            }
        }
        return re;
    }
};