201. Bitwise AND of Numbers Range

201. Bitwise AND of Numbers Range

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

My Solutions：

Brute Force的解法一定会超时，所以需要观察例子，发现结果是该数字范围内所有的数的左边共同的部分(参考：https://www.cnblogs.com/grandyang/p/4431646.html)

比如[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

AND的结果为100。仔细观察可以得出，最后的数是该数字范围内所有的数的左边共同的部分。

再比如[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，只要写代码找到左边公共的部分即可。

可以建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask AND就是最终结果

public int rangeBitwiseAnd(int m, int n) {
    int mask = Integer.MAX_VALUE;
    while ((m & mask) != (n & mask)) mask <<= 1;
    return m & mask;
}

还有一种方法是不需要用mask，直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果。

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