数字范围按位与

201. 数字范围按位与

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

示例 1:

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

示例 2:

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

我们首先想到将[m, n] 范围内的运算全部做一次与运算，然而超时。我们将 [9, 12] 的二进制字符画成图：

我们可以发现，对所有数字执行按位与运算的结果是对应二进制字符串的公共前缀再用零补上后面的剩余位。进一步的说，这些字符串的公共前缀就等于 9 和 12 两个数字的二进制字符串的公共前缀。

方法一：位移

我们可以将两个数字不断右移，同时记录位移的次数，直到它们相等，得到了公共前缀，我们再将公共前缀左移相应的次数。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        //找到公共前缀
        while(m != n){
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        //左移相应的次数
        return m << shift;
    }
}

时间复杂度O(1)，空间复杂度O(1)。

方法二：Brian Kernighan 算法

「Brian Kernighan 算法」，用于清除二进制串中最右边的 1。

我们每次对 n 和 n - 1进行按位与操作后，n 中最右边的 1 会被抹去变为 0 。

对于此题，我们将一直清除 n 最右边的 1 ，直到 n <= m，此时 n 就是公共前缀。

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

时间复杂度O(1)，空间复杂度O(1)。