2022-04-08 约 500 字预计阅读 1 分钟 - 次阅读

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

题目中所提到的二进制表示中单位计算置位为二进制表示中1的个数。

比如说$(21){10}=(10101){2}$，则该数字的计算置位为3。问题要求一段区间[left,right]中有质数个计算置位的数量。

换句话来说，该问题可以相当于快速计算出一个区间内每个数的计算置位，之后只需要判断这些置位是否为素数即可。

考虑以下情况

十进制	二进制
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

从这个表可以看到，二进制表示中从右往左数的第一位0和1的间隔为1个数字，第二位为2个数字，第三位为4个数字……这也是二进制的本质。

换句话来说，可以分别计算出一段区间内第一位为1的数字，第二位为1的数字……然后对其进行求和。

最终还是用了简单的解法

https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/solution/wei-rao-li-lun-by-wfnuser-lc94/

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

class Prime{
    map<int,bool> store;
public:
    Prime(){
        store[2]=true;
        store[3]=true;
    }
    bool judge(int v){
        if(v<2){
            return false;
        }
        if(store.find(v)!=store.end()){
            return true;
        }
        for(int i=2;i<=sqrt(v);i++){
            if(v%i==0){
                return false;
            }
        }
        store[v] = true;
        return true;
    }
};

class Solution {
public:
    int calculate_one(int v){
        int max_2 = log2(v);
        int val = pow(2,max_2);
        int count = 0;
        for(int i=max_2;i>=0;i--){
            if(v>=val){
                v-=val;
                count++;
            }
            val/=2;
        }
        return count;
    }

    int countPrimeSetBits(int left, int right) {
        int count = 0;
        Prime prime;
        for(int i=left;i<=right;i++){
            int val = this->calculate_one(i);
            if(prime.judge(val)){
                count++;
            }
        }
        return count;
    }
};

int main(void){
    Solution s;
    cout<<s.countPrimeSetBits(10,15)<<endl;
    return 0;
}

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

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