Bitwise and of Numbers Range

201. 数字范围按位与

分析

按位与的性质
- 任何数字与 0 进行按位与，结果都是 0，即 x & 0 = 0
- 相邻数字的按位与会减少 1 位的 1，例如：

计算 5 & 6 & 7 = 4，可以看到最右侧的 1 被清除了

观察区间变化
- 若 left 和 right 的二进制前缀相同，则它们的按位与结果保留这个前缀，后面的位全部补 0
- 若 left 和 right 的某一位出现了不同（即 0->1 或 1->0），则从该位及其更低位的按位与结果必然为 0

时间复杂度

由于整数的二进制表示最多 32 位，我们最多遍历 32 次，因此时间复杂度为 O(1)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution
{
public:
    int rangeBitwiseAnd(int left, int right)
    {
      int res = 0; // 存储最终结果
      for (int i = 30; i >= 0; -- i)  // 从高位到低位遍历每一位
      {
        if ((left >> i & 1) != (right >> i & 1))  // 如果某一位的 left 和 right 不同，终止循环
          break;
        if (left >> i & 1)  // 如果 left 在该位是 1，则保留该位
          res += (1 << i);
      }
      return res;
    }
};