LeetCode762-二进制表示中质数个计算置位

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/

中文链接：https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/

题目详述

给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。

（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）

示例 1:

1
2
3
4
5
6
7
输入: L = 6, R = 10
输出: 4
解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)

示例 2:

1
2
3
4
5
6
7
8
9
输入: L = 10, R = 15
输出: 5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)

注意:

  1. L, R 是 L <= R 且在 [1, 10^6] 中的整数。
  2. R - L 的最大值为 10000。

题目详解

  • 统计二进制 1 的个数，为质数则结果加一。
  • 数据范围为 [1, 10^6]，10^6 < 2^20，最多有 19 个 1，可能的质数有 2, 3, 5, 7, 11, 13, 17, 19。
1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode_00762 {

    public int countPrimeSetBits(int L, int R) {
        Set<Integer> set = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
        int res = 0;
        for (int i = L; i <= R; ++i) {
            if (set.contains(Integer.bitCount(i))) {
                ++res;
            }
        }
        return res;
    }
}
  • 实际上我们可以用一个整数来代替 HashSet，将 2, 3, 5, 7, 11, 13, 17, 19 这几个数在它的二进制位对应的位置置 1，其他位置为 0。
  • 比如通过 665772（它等于 0b1010 0010 1000 1010 1100）这个数，进行移位判断。
1
2
3
4
5
6
7
8
9
10
public class LeetCode_00762 {

    public int countPrimeSetBits(int L, int R) {
        int res = 0;
        for (int i = L; i <= R; ++i) {
            res += 665772 >> Integer.bitCount(i) & 1;   // 665772 = 0b1010 0010 1000 1010 1100
        }
        return res;
    }
}