友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
201. 数字范围按位与
给你两个整数 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 <= 231 - 1
思路分析
当计算 \(n & (n - 1)\) 时，会把 n 最右边的 1 变成 0。
从另外一个角度来看，就是寻找指定范围内所有数字的公共前缀。
对于大于 left 的前面的 1 都会成为 0，可以忽略。在 left 和 right 之间，要么是中间相同，要么是全部不同。所以，可以通过异或，求出后面的不同之处的位数，然后移位减一取反，再相与即可求出“前缀”。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-11 23:15:14
*/
public int rangeBitwiseAnd(int left, int right) {
while (left < right) {
right = right & (right - 1);
}
return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-01-31 21:06:30
*/
public int rangeBitwiseAnd(int left, int right) {
int bit = 32 - Integer.numberOfLeadingZeros(left ^ right);
return left & (~((1 << bit) - 1));
// 下面的方案超时（8265/8272）
// int[] bits = new int[32];
// for (int i = 0; i < 32 && (right >> i != 0); i++) {
// int bit = 1;
// for (int j = left; j <= right; j++) {
// bit &= (j >> i);
// if (bit == 0) {
// break;
// }
// if (j + 1 < j) {
// break;
// }
// }
// bits[i] = bit;
// }
// int result = 0;
// for (int i = 31; i >= 0; i--) {
// result <<= 1;
// result |= bits[i];
// }
// return result;
}