第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0201. 数字范围按位与

题目地址(201. 数字范围按位与)

题目描述

1
给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。
2
3
示例 1:
4
5
输入: [5,7]
6
输出: 4
7
示例 2:
8
9
输入: [0,1]
10
输出: 0
Copied!

前置知识

  • 位运算

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

一个显而易见的解法是, 从 m 到 n 依次进行求与的操作。
1
let res = m;
2
for (let i = m + 1; i <= n; i++) {
3
res = res & i;
4
}
5
return res;
Copied!
但是, 如果你把这个 solution 提交的话,很显然不会通过, 会超时。
我们依旧还是用 trick 来简化操作。 我们利用的性质是, n 个连续数字求与的时候,前 m 位都是 1.
举题目给的例子:[5,7] 共 5, 6,7 三个数字, 用二进制表示 101, 110,111, 这三个数字特点是第一位都是 1,后面几位求与一定是 0.
再来一个明显的例子:[20, 24], 共 20, 21, 22, 23,24 五个数字,二进制表示就是
1
0001 0100
2
0001 0101
3
0001 0110
4
0001 0111
5
0001 1000
Copied!
这五个数字特点是第四位都是 1,后面几位求与一定是 0.
因此我们的思路就是, 求出这个数字区间的数字前多少位都是 1 了,那么他们求与的结果一定是前几位数字,然后后面都是 0.

关键点解析

  • n 个连续数字求与的时候,前 m 位都是 1
  • 可以用递归实现, 个人认为比较难想到
  • bit 运算
代码:
1
n > m ? rangeBitwiseAnd(m / 2, n / 2) << 1 : m;
Copied!
每次问题规模缩小一半, 这是二分法吗?

代码

语言支持:JavaSCript,Python3
JavaScript Code:
1
/*
2
* @lc app=leetcode id=201 lang=javascript
3
*
4
* [201] Bitwise AND of Numbers Range
5
*
6
*/
7
/**
8
* @param {number} m
9
* @param {number} n
10
* @return {number}
11
*/
12
var rangeBitwiseAnd = function (m, n) {
13
let count = 0;
14
while (m !== n) {
15
m = m >> 1;
16
n = n >> 1;
17
count++;
18
}
19
20
return n << count;
21
};
Copied!
Python Code:
1
class Solution:
2
def rangeBitwiseAnd(self, m: int, n: int) -> int:
3
cnt = 0
4
while m != n:
5
m >>= 1
6
n >>= 1
7
cnt += 1
8
9
return m << cnt
Copied!
复杂度分析
  • 时间复杂度:最坏的情况我们需要循环 N 次,最好的情况是一次都不需要, 因此时间复杂度取决于我们移动的位数,具体移动的次数取决于我们的输入,平均来说时间复杂度为 $O(N)$,其中 N 为 M 和 N 的二进制表示的位数。
  • 空间复杂度:$O(1)$