762. Prime Number of Set Bits in Binary Representation

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

Note:
L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

思路:根据提示,数字范围在1~1000000之间,而2^20 =1048576>10^6,即20位的二进制可以表示0~1048575之间的任意数,因此不用太花功夫考虑怎么判断质数,只要找出20以内的质数存在集合里,判断是否属于集合即可(set容器的count()方法).
剩下的很简单,对[L, R]的每个数i,每次将i和1进行与操作

  110      111
& 001    & 001
------  ------
  000      001

若结果为0,则最低位为0;结果为1,则最低位为1.
然后i右移一位,继续检查最低位.
直到i为0.

int countPrimeSetBits(int L, int R) {
    set<int> prime = {2, 3, 5, 7, 11, 13, 17, 19}; //20以内质数集合
    int res = 0;
    for (int i = L; i <= R; i++) { //遍历从L到R的整数
        int set_bits = 0; //"set bit"数,即1的个数
        int tmp = i;
        while (tmp) {
            if (tmp & 1) set_bits++;  //若与操作结果为1,说明找到一个set bit
            tmp >>= 1; //自右移操作
        }
        //检查set_bits是否在质数集中
        if (prime.count(set_bits)) res++;
    }
    return res;
}