一、问题描述
给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
题目链接：二进制中质数个数
二、题目要求
样例
输入: L = 6, R = 10 输出: 4 解释: 6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 9 -> 1001 (2 个计算置位，2 是质数) 10-> 1010 (2 个计算置位，2 是质数)
考察
位运算基础题型 建议用时10~25min
三、问题分析
本题是位运算的第11题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：
题目说的有点迷惑，其实就是区间范围内每一个数字，假如转换成二进制之后1的个数为质数，那么就计算，否则不作数，下面分两步完成：
1.二进制 1 的个数
这一题数的范围最大是10^6，20位2进制就够用，你要用 int型 32位最大也没有多大影响。
这部分需要用到位运算的 与 左移运算，第45天有讲，我就不详细说了。
用左移运算一位一位计算是否包含1，如果相与的结果为1，那么计数器++。
2.判断是否为质数
质数：除了1和本身，不能被其他的自然数整除。
单独构造一个judge判断函数就行。
四、编码实现
classSolution { public: booljudge(intx)//质数判断 { inti; if(x<2) returnfalse; for(i=2;i*i<=x;i++) if(x%i==0) returnfalse; returntrue; } intcountPrimeSetBits(intleft, intright) { inti,j,ans=0,k=0;//初始化数据for(i=left;i<=right;i++)//循环计数 { ans=0;//计数器为0for(j=0;j<20;j++) { if(i&(1<<j))//判断1的个数 { ans++; } } if(judge(ans))//判断是否为质数k++; } returnk;//输出结果 } };
