题目描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

样例

输入: [5,7]
输出: 4

输入: [0,1]
输出: 0

算法1

(暴力) $O(n)$

C++ 代码

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res=n;
        while(m<n){
            res&=m;
            if(res==0)break;
            m++;
        }
        return res;
    }
};

算法2

(汉名距离) $O(logn)$

C++ 代码

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while(m<n){
            n=n&(n-1);
        }
        return n;
    }
};

算法3

(移位) $O(logn)$

C++ 代码

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift=0;
        while(m<n){
            m>>=1;
            n>>=1;
            shift++;
        }
        return m<<shift;
    }
};