题目链接：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.

这道题的要求是计算给定数m到n中所有数的与操作的结果。

直接思路，从m到n逐个进行与操作。可是当n-m非常大的时候，时间复杂度就会非常高。

接下来，仔细看一下与操作，就是当全是1的时候结果才是1。也就是说，对应的2位不同的话，就清零。而[m, n]间的所有数字进行与操作，也就是将这些数字对应的某一位：

  • 如果相同，不变；
  • 如果有不同，清0。

可以注意到，数字在加1的时候，是从最右边的位开始的，因此可以不用[m, n]间的所有数字，只需要m和n，从左侧开始，保留相同的数位，直到出现第一个不同的，将该位直到最后清0即可。

时间复杂度：O(n)（n为int的二进制位数，即32）

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12

class Solution
{
public:
    int rangeBitwiseAnd(int m, int n)
    {
        // 求最左侧开始m和n中相同的位
        int res = INT_MAX;
        while((m & res) != (n & res))
            res <<= 1;
        return m & res;
    }
};