题目

类型：位运算

解题思路

1、枚举 [left,right] 范围内的数不可避免
2、二进制中 1 的个数不会超过 19 。用一个二进制数

来存储这些质数，其中 mask 二进制的从低到高的第 i 位为 1 表示 i是质数，为 0 表示 i 不是质数。
核心 统计「二进制 1 的数量」
3、设整数 x 的二进制中 1 的个数为 c ，若 mask 按位与 2的c次方 不为 0 ，则说明 c 是一个质数。

代码

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (((1 << Integer.bitCount(x)) & 665772) != 0) {
                ++ans;
            }
        }
        return ans;
    }
}