数字范围按位与(Bitwise AND of Numbers Range)

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

输入：left = 5, right = 7
输出：4

示例 2：

输入：left = 0, right = 0
输出：0

示例 3：

输入：left = 1, right = 2147483647
输出：0

提示：

  • 0 <= left <= right <= 2^31 - 1
int rangeBitwiseAnd(int left, int right){
    if(left == 0) return 0;
    int a = right;
    for(int i = left;i<right;i++){
        a &=i;
    }
    return a;
}

这样显然会超时

int rangeBitwiseAnd(int left, int right){
    int res = 0;
    bool isDiff = false;
    for (int i =30;i>=0; i--){
        int dm = left & (1<<i);
        int dn = right & (1<<i);
        if(dm != dn){
            isDiff = true;
        }
        if(!isDiff){
            res += dm; 
        }
    }
    return res;
}

更简单的方法

int rangeBitwiseAnd(int left, int right){
    int res;
    int count = 0;
    while(left != right){
        left  = left >> 1;
        right = right >> 1;
        count ++;
    }
    res = left << count;
    return res;
}

上面这个是已经知道原理之后的方法，下面再简单改改

int rangeBitwiseAnd(int left, int right){
    int count = 0;
    while(left != right){
        left  = left >> 1;
        right = right >> 1;
        count ++;
    }
    return left << count;
}

不知道leetcode的机制到底是怎么样的，这个代码简单改改居然是上面的1/3的耗时