Keshawn_lu's Blog

Leetcode 201. 数字范围按位与

字数统计: 268阅读时长: 1 min
2020/08/23 Share

题目简介:

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

示例 1:

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

示例 2:

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

思路:

其实这道题的核心就是找到两个数字用二进制表示时的公共前缀,因为范围内的数字是连续的,所以除了公共前缀,其余后面的部分,每个部位必有0出现,所以根据与运算的规则,都为0。

所以问题转换为了找公共前缀,我们可以先将两个数字向右位移,直至两个数字相同,此时的数字(二进制)便为公共前缀,然后再根据位移的步数再左移回去(即在后面补0),便得到了最后的结果。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {

int move = 0;

//寻找公共前缀
while(m < n){

m = m >> 1;
n = n >> 1;

move++;
}

return m << move;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: