题目描述
题目链接:201. Bitwise AND of Numbers Range
Given two integers
left
andright
that represent the range[left, right]
, return the bitwise AND of all numbers in this range, inclusive.
例子
例子 1
Input:
left = 5, right = 7
Output:4
例子 2
Input:
left = 0, right = 0
Output:0
例子 3
Input:
left = 1, right = 2147483647
Output:0
Constraints
0 <= left <= right <= 2^31 - 1
解题思路
这道题如果直接遍历 range
的所有数字进行相与会超时,因此我们需要找规律。实际上这道题的结果的最大位数是31,因此只需要判断这 31 位里面有哪几位为 1 即可。也就是判断 range
只要其中一位为 0 那么那一位一定为 0.而从数的连续性我们可以知道,以 5 (二进制为 101)到 10 (二进制为 1010)为例,只要看最大数的最高位即可,最高位往左全都是 0,最高位往右也肯定会有 0(因为数的连续性),如果 left
和 right
的最高位都为 1 (比如10和8),那么结果则为该位对应的数字,否则是 0。
代码如下:
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int ret = 0;
for (int i = 30; i >= 0; --i) {
int mask = (1 << i);
if ((right & mask) > 0) {
if ((left & mask) > 0) {
ret ^= (1 << i);
} else {
break;
}
}
}
return ret;
}
};
- 时间复杂度:
O(1)
- 空间复杂度:
O(1)
GitHub 代码同步地址: 201.BitwiseAndOfNumbersRange.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions