201. Bitwise AND of Numbers Range (M)

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

题意

将指定范围内所有数字进行按位与操作，返回结果。

思路

直接按位与会超时。

找规律(如下图)可发现，由于是连续数字区间，所以必有一部分末尾位相与后为0，问题就转化为了求m和n二进制形式左半边相同的部分。

可以直接移位求相同部分，也可以使用 191. Number of 1 Bits 中提到的 n = n & (n - 1) 方法来处理。

代码实现 - 位运算 1

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

代码实现 - 位运算 2

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