题目描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m，n 两端点）。

样例

输入: [5,7]
输出: 4

输入: [0,1]
输出: 0

算法

(位运算) $O(\log n)$

1. 找到 m 和 n 从高位到低位中第一次出现不一样的位置，答案为该位置之前的二进制的累积和。
2. 这是因为出现了第一次不一样之后，从 m 上升到 n 的过程中，必定会经历 xxx100000... 和 xxx011111...的一次变化，这次变化会将该位之后的所有数字按位与清零。

时间复杂度

• 最多遍历 31 次二进制位，故时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            if (((m >> i) & 1) ^ ((n >> i) & 1))
                break;

            if ((m >> i) & 1)
                ans |= 1 << i;
        }

        return ans;
    }
};