0%

[Leetcode]201. Bitwise AND of Numbers Range(C++)

题目描述

题目链接:201. Bitwise AND of Numbers Range

Given two integers left and right 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(因为数的连续性),如果 leftright 的最高位都为 1 (比如10和8),那么结果则为该位对应的数字,否则是 0。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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