数字范围按位与
难度:
标签:
题目描述
给你两个整数 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
代码结果
运行时间: 25 ms, 内存: 16.2 MB
/*
* 思路：
* 使用Java Stream API实现按位与操作。
* 仍然是找到区间 [left, right] 中的公共前缀。
* 通过Stream生成 [left, right] 的数字流，并使用reduce进行按位与操作。
*/
import java.util.stream.IntStream;
public class Solution {
public int rangeBitwiseAnd(int left, int right) {
return IntStream.rangeClosed(left, right).reduce((a, b) -> a & b).getAsInt();
}
}
解释
方法:
题解的思路是利用位运算的特点，找到区间 [m, n] 中所有数字的二进制表示的公共前缀。因为按位与运算的结果只保留了公共前缀部分，所以最终结果就是将公共前缀再向左移动 shift 位得到的数字。具体做法是，不断将 m 和 n 同时右移，直到 m 和 n 相等，同时记录右移的次数 shift。最后将 m 左移 shift 位即可得到答案。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到的公共前缀是指什么？能否举例说明如何从二进制角度理解公共前缀？
▷🦆
在题解中，为什么当m小于n时，要同时将m和n右移？右移操作对求解最终结果有什么影响？
▷🦆
题解提到，最终结果通过`将m左移shift位`得到，这里的shift是如何计算的？它代表了什么意义？
▷🦆
在极端情况下，例如示例3中left为1，right为2147483647，这种方法的效率如何？与暴力方法相比有何优势？
▷