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

---

求把从m~n的所有整数相与的结果。
暴力方法就是从m到n遍历一遍，把所有数都相与一下。但是TLE。
这题明显是个数学题或者找规律题。网上的解法大多数是这样的，把m~n的所有数相与的结果等于m和n这两个数的二进制的最长公共前缀。比如题目中的[5,7]，5和7的二进制分别为101和111，最长公共前缀就是100=4，后两位不一样也要补0。再比如[26,30]，26和30的二进制分别为11010和11110，最长公共前缀为11000=24。
知道这个规律就好办了，因为m和n都是正数，不断同时把m和n往右移，直到他们相等，最后再把m往左移回去就是最终结果。代码如下：

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

本代码提交AC，用时69MS。

二刷。看下面的图，m和n最长公共前缀后面的二进制位，在[m,n]范围内都在不停的变化，也就是有0也有1，所以全与之后肯定都是0，只有公共前缀的1相与不会变0，所以要找公共前缀。