LeetCode/solutions/201. Bitwise AND of Numbers Range.md

# [201. Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/)

# 思路
给定两个整数m和n，求m到n之前所有数按位与后的结果。这题如果按照题目的意思暴力解的话肯定会超时，需要思考巧妙的方法。

我们看看5到7三个数的例子：
``` 
5: 101
6: 110
7: 111
-> 100
```
结果为100，仔细观察我们可以得出，结果是该数字范围内所有的数的高位公共部分。
进一步观察得出，结果是m和n的高位公共部分，原因是：由于 m <= n，所以如果m和n在高x位bit值都相同，那么其中间的数在高x位也与m和n相同。

因此，题目转换成求m和n的二进制的高位公共部分。有以下几种思路。

## 思路一
建立一个全1的mask，然后每次向左移一位，比较`(m & mask)`和`(n & mask)`是否相同，不同再继续左移一位，直至相同，最后`m & mask`就是最终结果。

## 思路二
不用mask，将m和n不断右移直到相等，若移动了x次，再将m左移x位即结果。

## 思路三
考虑不断去掉n最低位的1直到`m >= n`，可以采用**n不断与上n-1实现去掉n最低位的1**。

# C++
## 思路一
``` C++
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        long long mask = 0xffffffff;
        while ((m & mask) != (n & mask)) {
            mask <<= 1;
        }
        return m & mask;
    }
};
```

## 思路二
``` C++
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            count++;
        }
        return m << count;
    }
};
```

## 思路三
``` C++
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) n &= (n - 1);
        return n;
    }
};
```