企业网站建设投标书,销售管理软件新技术,有多少网站建设外包,如何做视频教程网站数字范围按位与
给你两个整数 left 和 right #xff0c;表示区间 [left, right] #xff0c;返回此区间内所有数字 按位与 的结果#xff08;包含 left 、right 端点#xff09;。
示例 1#xff1a;
输入#xff1a;left 5, right 7 输出#xff1a;4
解题思路 …数字范围按位与
给你两个整数 left 和 right 表示区间 [left, right] 返回此区间内所有数字 按位与 的结果包含 left 、right 端点。
示例 1
输入left 5, right 7 输出4
解题思路
在一个范围内进行按位与操作时如果这个范围跨越了多个2的幂次方区间那么最终的结果中这些幂次方位上的所有位都将变为0。例如
对于范围 [5, 7]按位与的结果是 4因为 5 的二进制表示是 101 6 的二进制表示是 110 7 的二进制表示是 111 5 6 7 100 (即 只有相同前缀的数字保留了其他位都是0)
可以通过不断右移操作找到左端点和右端点的共同前缀非共同前缀的结果一定是0记录右移的次数最后将共同前缀左移回原来的位置。
**例如**n 和 m 的二进制及最长前缀如下图所示后缀 011 累加到 110 必然经过 100。011 和 100 保证了答案中长度为 3 的后缀必然均为 0。
java实现
public class RangeBitwiseAnd {public int rangeBitwiseAnd(int left, int right) {int shift 0;// 找到 left 和 right 的共同前缀while (left right) {left 1;right 1;shift;}// 将共同前缀左移回去return left shift;}// 测试用例public static void main(String[] args) {RangeBitwiseAnd solution new RangeBitwiseAnd();System.out.println(solution.rangeBitwiseAnd(5, 7)); // 期望输出: 4System.out.println(solution.rangeBitwiseAnd(0, 1)); // 期望输出: 0System.out.println(solution.rangeBitwiseAnd(1, 2147483647)); // 期望输出: 0}
}时间空间复杂度 时间复杂度O(log n)其中 n 是范围内的最大值。因为在逐步右移直到 left 等于 right最多需要进行 log n 次右移操作。 空间复杂度O(1)只使用了常数级别的额外空间。
