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

LeetCode 762. Prime Number of Set Bits in Binary Representation

Given two integers left and right, return the count of numbers in the inclusive range [left, right] 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 1’s present when written in binary.

Example 1:

Input: left = 6, right = 10
Output: 4
Explanation:
6  -> 110 (2 set bits, 2 is prime)
7  -> 111 (3 set bits, 3 is prime)
8  -> 1000 (1 set bit, 1 is not prime)
9  -> 1001 (2 set bits, 2 is prime)
10 -> 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.

Constraints:

1 <= left <= right <= 10^6
0 <= right - left <= 10^4

题意

在[left, right]区间中的数，他们的二进制表示中1的个数为质数的有几个

method

因为1024 * 1024 > 10^6，所以10^6最多不超过20个Bit，所以只需要考虑20以内的质数就可以了

int countPrimeSetBits(int left, int right) {
    unordered_set<int> hash = {2, 3, 5, 7, 11, 13, 17, 19};
    int res = 0;
    for (int i = left; i <= right; i++) {
        int cnt = 0;
        for (int k = i; k; k >>= 1) cnt += k & 1;   // 累加每个Bit
        if (hash.count(cnt)) res++;
    }
    return res;
}