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

A:
其实就是挨个查看，该位是否在为全1.

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res = 0;
        for(int i = 31;i>=0;i--){
            long mask = 1<<i;
            if( m>=mask && n <=mask+mask-1){
                res += (int)mask;
                m -= mask;
                n -= mask;
            }
        }
        return res;
    }
};

Mistakes:
1:  当时，感觉，如果高位不在全1 区间。就可以break了。
   但是，没有考虑，还可能是 全0 ， 因此不能break。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果，代码如下：

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int mask = Integer.MAX_VALUE;
        for(int i =0;i<31;i++){
            if( (mask & m) == (mask&n))
                break;
            mask = mask << 1;
        }
        return mask & m;
    }
}