置位位数为质数的整数个数如何用位运算统计？

简化版

遍历区间 [left,right]，对每个数统计二进制中 1 的个数，再判断这个个数是否为质数。由于整数范围通常不大，1 的个数最多 32，可以用质数集合或位掩码快速判断。

详细版

统计 1 的个数可以用内置函数 Integer.bitCount(x)，也可以用 x &= x-1 手写。对 32 位整数，可能的置位数量只有 0 到 32，其中质数是 2,3,5,7,11,13,17,19,23,29,31。

时间复杂度为 O((right-left+1) * 位数)，若用内置 bitCount 可视作常数。面试重点是区分“数字本身是否为质数”和“数字的 1 的个数是否为质数”。

完整版教学

一、题目判断的是谁为质数

题目不是问数字 x 是否为质数，而是问 x 的二进制中 1 的数量是否为质数。

x = 10
二进制 1010
1 的个数 = 2
2 是质数，所以 10 计入答案

这个语义如果读错，整题就会跑偏。

二、如何统计置位位数

置位位数也叫汉明重量。可以用内置函数：

Integer.bitCount(x)

也可以手写：

while x != 0:
    x = x & (x - 1)
    count++

x & (x-1) 每次会消掉最低位的 1。

三、哪些 count 是质数

对 32 位整数，count 最大也就 32。质数集合很小：

count	是否质数
0	否
1	否
2	是
3	是
4	否
5	是

记忆钩子：这题质数判断的对象是 bitCount，范围很小，可以预处理。

可以用 Set<Integer>，也可以用一个整数位掩码记录哪些 count 是质数。

四、代码模板

int countPrimeSetBits(int left, int right) {
    Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31);
    int ans = 0;
    for (int x = left; x <= right; x++) {
        if (primes.contains(Integer.bitCount(x))) {
            ans++;
        }
    }
    return ans;
}

这份写法可读性最好。若面试追求位味，可以把质数集合压成一个 mask。

五、质数集合也能用位掩码

构造：

primeMask = 0
对每个质数 p：primeMask |= 1 << p

判断：

((primeMask >> count) & 1) == 1

这种写法把“count 是否在质数集合中”也变成了位查询。

六、用例子推演

left=6,right=10：

6  = 110  => count=2 => 计入
7  = 111  => count=3 => 计入
8  = 1000 => count=1 => 不计
9  = 1001 => count=2 => 计入
10 = 1010 => count=2 => 计入

答案是 4。

七、常见误区与追问

• 误区：判断 x 本身是否为质数。 题目判断的是 bitCount(x)。
• 误区：把 1 当成质数。 1 不是质数。
• 误区：忘记 0 也不是质数。 没有 1 的数字不应计入。
• 追问：为什么质数集合这么小？ 32 位整数最多只有 32 个 1。
• 追问：能不用内置函数吗？ 可以用 x & (x-1) 手写计数。
• 追问：复杂度是多少？ 遍历区间，单个数字统计为常数位数。

八、加强记忆

置位质数题分两步：先数 1，再判这个数量是不是质数。不要去判断数字本身。Integer.bitCount 是工程写法，x&(x-1) 是面试解释位技巧；质数集合只到 31，很小，Set 或 bitmask 都可以。