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.

For example, given the range [5, 7], you should return 4.

分析

第一眼看这是一道很简单很直接的题目，但做了这么多Leetcode，也很容易想到这肯定是一道技巧性很强的题目，直接做的结果就是超时或者超内存。

所以我们必须在时间和空间上做出优化，首先观察到的是，如果下界m==0，那么无论经过多少次运算，其结果最终都为0.

但仅有这一点还不够，所以要从别的角度考虑。

所以我们举几个例子观察一下: m==5,n==7时，返回4

101->111
10->11
1->1

m==2，n==4，返回

010->100
1->10

我们看到，如果每次让m，n右移一位，直到m，n相等为止。记录右移次数count，让最后的m左移count位，就是我们需要的结果。

水平有限，不能给出详尽的数学证明，但可以给出正确结论，即:m到n范围内所有数字相与的结果就是m和n在二进制表示下的”公共首部”

代码如下:

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