---

0762. 二进制表示中质数个计算置位

• 标签：位运算、数学
• 难度：简单

题目链接

• 0762. 二进制表示中质数个计算置位 - 力扣

题目大意

描述：

给定两个整数 $left$ 和 $right$。

要求：

在闭区间 $[left, right]$ 范围内，统计并返回「计算置位位数为质数」的整数个数。

说明：

• 「计算置位位数」就是二进制表示中 $1$ 的个数。
  • 例如，$21$ 的二进制表示 $10101$ 有 $3$ 个计算置位。
• $1 \le left \le right \le 10^{6}$。
• $0 \le right - left \le 10^{4}$。

示例：

• 示例 1：

输入：left = 6, right = 10
输出：4
解释：
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
共计 4 个计算置位为质数的数字。

• 示例 2：

输入：left = 10, right = 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 不是质数)
共计 5 个计算置位为质数的数字。

解题思路

思路 1：位运算 + 质数判断

计算置位位数就是计算二进制表示中 $1$ 的个数。我们需要统计范围内有多少个数的二进制表示中 $1$ 的个数是质数。

实现步骤：

1. 由于 $right \le 10^6 < 2^{20}$，所以二进制表示最多有 $20$ 位，$1$ 的个数最多为 $20$。
2. 预先计算 $20$ 以内的质数：$2, 3, 5, 7, 11, 13, 17, 19$。
3. 遍历 $[left, right]$ 范围内的每个数字：
   • 使用 bin(num).count('1') 或位运算计算 $1$ 的个数。
   • 判断 $1$ 的个数是否是质数。
4. 统计满足条件的数字个数。

思路 1：代码

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # 20 以内的质数集合
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        
        count = 0
        for num in range(left, right + 1):
            # 计算二进制表示中 1 的个数
            set_bits = bin(num).count('1')
            # 判断是否是质数
            if set_bits in primes:
                count += 1
        
        return count

思路 1：复杂度分析

• 时间复杂度：$O((right - left) \times \log(right))$，其中 $\log(right)$ 是计算二进制位数的时间。
• 空间复杂度：$O(1)$。