762. Prime Number of Set Bits in Binary Representation

762

[思路]：寻找给定两个整数区间内的整数的二进制表示拥有素数个数的1；
例如：

21的二进制：10101 ，三位1，为素数；
1 不是素数；

• 一种方法是：计算整数的二进制表示；然后统计1的个数；

• 另一种方法： 使用位运算，通过移位和1相与，来统计1的个数；

本次题限制【1,100000】之间，最大位数20位，所有位数的素数有：
{2, 3, 5, 7, 11, 13, 17, 19}

    int countPrimeSetBits(int L, int R) {
       set<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
        int cnt = 0;
        for (int i = L; i <= R; i++) {
            int bits = 0;
            for (int n = i; n>0; n >>= 1)
                bits += n & 1;
            cnt += primes.count(bits);
        }
        return cnt;
    }