给你两个整数 left 和 right ,表示区间 [left, right] ,返回此区间内所有数字 按位与 的结果(包含 left 、right 端点)。
时间: 2024-03-10 20:49:03 浏览: 17
题目描述
给你两个整数 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 <= 2^31 - 1
解题思路
当 left 和 right 不相等时,它们的二进制至少有一位不同,此时它们的按位与结果的这一位为 0。因此,我们可以不断将 left 和 right 右移一位,直到两者相等,即找到了它们的公共前缀。最后再将 left 左移这个公共前缀的长度,即为所求的结果。
举个例子:假设 left = 5,right = 7,它们的二进制分别为 101 和 111,它们的公共前缀为 10,长度为 1,因此将 left 左移 1 位,即得到 100,即为所求的结果。
代码实现
Python:
```python
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
while left < right:
left >>= 1
right >>= 1
shift += 1
return left << shift
```
C++:
```c++
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
};
```
时间复杂度分析:每次循环将 left 和 right 各右移一位,因此总时间复杂度为 O(log n),其中 n = max(left, right)。
空间复杂度分析:只需要常数级别的额外空间,因此空间复杂度为 O(1)。
完整代码
Python:
```python
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
while left < right:
left >>= 1
right >>= 1
shift += 1
return left << shift
```
C++:
```c++
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
};
```