博文中会简要介绍Leetcode P0201题目分析及解题思路。

“Bitwise AND of Numbers Range”是一道比较基础的位运算的题目。这道题有两种解法。一种是利用每一个给定比特位的变化具有周期性，通过比较上下界的差和周期性间隔（Interval）之间的大小关系来判断当前上下界之间的所有数的给定比特位上是否存在0；第二种则是通过观察最终结果，发现实际结果就是上下界公共的比特位前缀，从而通过移位操作来找到上下界两个数的公共前缀比特位。

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

第一种解法比较直接，我们可以观察下述各数，

0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100

不难发现末尾比特位的变化周期是最多每两个变化一次，也就是说若上下界的差大于1，则结果的末尾一定会是零，

观察倒数第二位，则容易发现该比特位的变化周期是最多每三个变化一次，譬如0010, 0011, 0100，也就是说若上下界的差大于2，则结果的该比特位一定会是零，

观察倒数第三位，则容易发现该比特位的变化周期是最多每五个变化一次，譬如0100 0101 0110 0111 1000，也就是说若上下界的差大于4，则结果的该比特位一定会是零，

...

依次类推。除此之外，我们只需要再判断上下界的该比特位是否为0即可，若有存在至少一个0，那么可以跳过对周期的判断，否则判断周期。

以下是Java的题解代码实现。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int ret = 0, interval = n-m, coef = 1;
        for (int itr=0; itr<32; ++itr) {
            if ((m&1) == 1 && (n&1) == 1 
                && interval < coef) {
                ret += coef;
            }
            
            coef *= 2;
            m >>= 1;
            n >>= 1;
        }
        
        return ret;
    }
}

第二种解法虽然没那么直接，但是也非常易懂并且十分简单。我们可以观察如下图片，

不难发现对于任意两个给定的上下界，两者公共的比特位前缀其实就是我们需要的结果。原因其实很简单，从下界累加到上界，在累加过程中后缀比特位会一直变化，即不断出现进位的情况，但公共的前缀比特位则一直保持不变，所以我们最终只需要关注上下界的公共比特位前缀即可。

最终我们使用下图的移位操作，来得到它们的公共前缀比特位。需要注意的是，我们最终还需要乘上一个系数，因为移位以后公共前缀比特位代表的数其实被我们缩小了，所以需要还原回去。

以下是C++的题解代码实现。

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        // Find the common prefix bits
        long exp = 1;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            exp *= 2;
        }
        
        return m*exp;
    }
};