LintCode 1046 · Prime Number of Set Bits in Binary Representation (求比特数和质数题)-Toy模板网

这篇具有很好参考价值的文章主要介绍了LintCode 1046 · Prime Number of Set Bits in Binary Representation (求比特数和质数题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1046 · Prime Number of Set Bits in Binary Representation
Algorithms
Description
Solution16
Notes
Discuss26
Leaderboard
Record

Description
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.)

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

Example
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)

解法1：
注意 R in the range [1, 10^6]，所以最大数也只有20个比特。
每个数的1数目和，应该就是数组primes中的一个。primes = {2, 3, 5, 7, 11, 13, 17, 19};文章来源地址https://www.toymoban.com/news/detail-738239.html

class Solution {
public:
    /**
     * @param l: an integer
     * @param r: an integer
     * @return: the count of numbers in the range [L, R] having a prime number of set bits in their binary representation
     */
    int countPrimeSetBits(int l, int r) {
        int primeBits = 0;
        vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};
        set<int> primeSet(primes.begin(), primes.end());
        int res = 0;
        for (int i = l; i <= r; i++) {
            int numBits = calcBits(i);
            if (primeSet.find(numBits) != primeSet.end()) {
                res++;
            }
        }
        return res;
    }
private:
    int calcBits(int x) {
       int numBits = 0;
       while (x) {
           x = x & (x - 1);
           numBits++;
       }
       return numBits;
    }
};

到了这里，关于LintCode 1046 · Prime Number of Set Bits in Binary Representation (求比特数和质数题)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！