LeetCode-Day109(C++) 201. 数字范围按位与

1. 数字范围按位与

   给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

输入：left = 5, right = 7

输出：4

示例 2：

输入：left = 0, right = 0

输出：0

示例 3：

输入：left = 1, right = 2147483647

输出：0

提示：

0 <= left <= right <= 231 - 1

class Solution {

public:

int rangeBitwiseAnd(int m, int n) {

int shift = 0;

// 找到公共前缀

while (m < n) {

m >>= 1;

n >>= 1;

++shift;

}

return m << shift;

}

};

复杂度分析

时间复杂度：O(logn)。算法的时间复杂度取决于 m 和 n 的二进制位数，由于 m≤n，因此时间复杂度取决于 n 的二进制位数。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/solution/shu-zi-fan-wei-an-wei-yu-by-leetcode-solution/