用java解决这个问题 ,控制时间复杂度在十的七次方以内。给定两个整数 a,b 。 请你计算,在 [a,b] 范围内有多少个整数满足其二进制表示恰好有一个 0 。 不考虑前导 0 。 例如,当 a=5,b=10 时,[5,10] 范围内的所有整数及其二进制表示如下: 510=1012,610=1102,710=1112,810=10002,910=10012,1010=10102 可以看出,只有 5 和 6 满足二进制表示恰好有一个 0 。 输入格式 共一行,两个整数 a,b 。 输出格式 一个整数,表示满足条件的整数数量。数据范围 前 6 个测试点满足 1≤a≤b≤104 。 所有测试点满足 1≤a≤b≤1018 。
时间: 2024-02-12 09:09:19 浏览: 36
以下是时间复杂度为 O(log(b)) 的 Java 代码实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
System.out.println(countNums(a, b));
}
private static long countNums(long a, long b) {
return count(b) - count(a - 1);
}
private static long count(long x) {
if (x <= 0) {
return 0;
}
long res = 0;
for (int i = 0; i < 64; i++) {
long cnt = (x >>> i) & 1;
long pre = x >>> (i + 1) << i;
long suf = (1L << i) - 1;
res += cnt * pre + Math.min(cnt, 1) * suf;
}
return res;
}
}
```
解释:
我们可以枚举一个数的每一位,假设当前枚举的是第 i 位(从低位到高位编号),那么我们可以将这一位上的 0 变成 1,然后枚举第 i+1 位到第 63 位上的数,计算有多少个数的二进制表示中恰好有一个 0。
具体来说,假设当前枚举的数是 x,它的第 i 位上是 0,那么我们可以将它的第 i 位上的 0 变成 1,得到的数是 x'。那么 x' 的二进制表示中恰好有一个 0 的数的个数就等于:
- x' 的前 i 位中 1 的个数,乘以 2 的 i 次方;
- 如果 x 的第 i+1 位上是 1,那么 x' 本身就是一个符合要求的数,因此再加上 x' 的后 i 位中恰好有一个 0 的数的个数。
我们可以使用移位和位运算来计算一个数的二进制表示中 1 的个数和某一位上的数是 0 还是 1。具体来说,如果要计算 x 的第 i 位上的数是 0 还是 1,可以使用 x >>> i & 1 的表达式,如果结果是 0,说明 x 的第 i 位上是 0,否则说明 x 的第 i 位上是 1。
需要注意的是,当 x 的二进制表示中的某一位是 0 时,我们需要将这一位上的 0 变成 1,得到的数是 x',然后再计算 x' 的贡献。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)