# 201. Bitwise AND of Numbers Range

[**201. Bitwise AND of Numbers Range**](https://leetcode.com/problems/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]里共有三个数字，分别写出它们的二进制为：

**1**01　　**1**10　　**1**11

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

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

**11**010　　**11**011　　**11**100　　**11**101　　**11**110

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

可以建立一个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; 
}
```
