201.数字范围按位与

数字范围按位与

给你两个整数 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 <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/bitwise-and-of-numbers-range
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1：朴素解法

遍历数字范围，逐个相与即可。唯一需要注意的是int的最大值2147483647，right = 2147483647时，int i 会超出数值表示范围。需要定义long long int。left = 2147483647时，i = left + 1会超出范围，需要i = (long long int)left + 1,问题时每次都进行强制类型转换会导致超时，所以将left = 2147483647作为特例。

code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        
        int ans = left;
        if(left == 2147483647) return 2147483647;

        long long int i;
        for(i = left + 1;i <= right;i++)
        {
            ans = ans & i;
        }

        return ans;
    }
};

解题思路2：位运算

基于两个结论：
结论1：一个数加上1之后一定存在一个高位的数字之后的数字变成相反的
结论2：相反之后相与结果为零，并且只要存在一个零，之后所有的相与的值均为零
基于以上结论，我们可以发现从m不断加一到n的过程中会存在不断的抵消掉一些地位的数字，最后会只剩下n的高位。只需要找到m和n的公共高位即可。时间复杂度O(logn).

code

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        
        int offset = 0;

        while(m != n)
        {
            m = m >>1;
            n = n >>1;
            offset ++;
        }

        return n << offset;
    }
};