菜单
文章 Leetcode

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

beautifulremi

beautifulremi

• 阅读本文需 4 分钟

题目

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

计算置位位数 就是二进制表示中 1 的个数。

  • 例如， 21 的二进制表示 10101 有 3 个计算置位。

示例 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 <= left <= right <= 10^6
  • 0 <= right - left <= 10^4

解题思路

这道题的逻辑非常直接，可以拆分为两个独立的核心步骤：

  1. 计算置位：统计每个数字二进制表示中 1 的个数。
  2. 质数判断：判断这个个数是否为质数。

因为题目给定的数据范围有一个很关键的隐藏条件，我们可以利用它来做一个非常巧妙的位运算优化。

方法一：常规遍历 + 预置质数集合（直观解法）

由于 $left$ 和 $right$ 最大只有 $10^6$，而 $10^6 < 2^{20}$。这意味着任何在这个范围内的数字，其二进制中的 1 的个数最多不会超过 19 个。

在 19 以内的质数屈指可数：2, 3, 5, 7, 11, 13, 17, 19。

步骤：

  1. 初始化一个计数器 ans = 0。
  2. 遍历 $[left, right]$ 区间内的每一个整数 i。
  3. 计算 i 的二进制中 1 的个数（通常各语言都有内置函数，如 Python 的 i.bit_count()，C++ 的 __builtin_popcount(i)，或者用经典的 n & (n - 1) 算法快速消去最低位的 1）。
  4. 判断这个个数是否在预先定义好的质数集合 {2, 3, 5, 7, 11, 13, 17, 19} 中。如果是，ans += 1。

方法二：状态压缩 / 位掩码（进阶优雅解法）

既然 1 的个数最多只有 19，我们可以把“判断是否为质数”的操作压缩成一个二进制状态掩码（Bitmask）。这是一种非常经典且高效的处理方式。

我们可以构造一个整数，让它的第 $i$ 个二进制位代表数字 $i$ 是否为质数（是质数则为 1，非质数则为 0）。

  • 第 2 位（质数）：1
  • 第 3 位（质数）：1
  • 第 5 位（质数）：1
  • 第 7 位（质数）：1
  • 第 11 位（质数）：1
  • 第 13 位（质数）：1
  • 第 17 位（质数）：1
  • 第 19 位（质数）：1
  • 其余位（包括 0 和 1）全为 0。

将这个对应的二进制数 10100010100010101100 转换为十六进制是 0xA28AC，转换为十进制是 665772。

步骤：

当我们统计出一个数字有 c 个置位（1的个数）时，只需要将 665772 向右移 c 位，再与 1 进行按位与操作：

$$(665772 >> c) \ & \ 1$$

如果结果是 1，说明 c 是质数；如果是 0，则不是。这直接替代了集合查询或写死 if-else 的逻辑，执行效率极高。

复杂度分析

  • 时间复杂度：$O(R - L)$，其中 $R$ 和 $L$ 分别是 $right$ 和 $left$。我们需要遍历区间内的每一个数，每次计算二进制 1 的个数以及位运算判断的时间复杂度都是 $O(1)$。
  • 空间复杂度：$O(1)$，只需要常数级别的变量空间。

具体代码

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # 665772 的二进制表示中，第 2, 3, 5, 7, 11, 13, 17, 19 位均为 1
        # i.bit_count() 统计 i 的二进制中 1 的个数
        return sum((665772 >> i.bit_count()) & 1 for i in range(left, right + 1))
分享