二进制算法口诀怎么用？打基础之LeetCode算法题第46日

二进制算法口诀怎么用？打基础之LeetCode算法题第46日判断质数：如果一个数n不能被区间[2，（n^0.5） 1]内的任何一个整数整除，那么n就是一个质数。内我的反映是先求出R的二进制长度，然后求在这个长度范围内的质数。大家还记得如何判断一个数是不是质数吗？给定两个整数 L 和 R ，找到闭区间 [L R] 范围内，计算置位位数为质数的整数个数。（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）注：

一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧，一开始就弄些重量级的，什么人工智能，机器学习的算法，还要有大量的数学以及优化的知识，小白们估计会很郁闷，当然我也不一定能做出来对吧。

我计划每题给出两种语言的解决方案，一种静态语言，一种动态语言。

我选择C语言，Python和Java作为实现语言，由于篇幅有限，其他语言的实现有兴趣的朋友请自己尝试。

LeetCode 762. 二进制表示中质数个计算置位（Prime Number of Set Bits in Binary Representatio）

问题描述：

给定两个整数 L 和 R ，找到闭区间 [L R] 范围内，计算置位位数为质数的整数个数。

（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）

注：

1. L R 是 L <= R 且在 [1 10^6] 中的整数。
2. R - L 的最大值为 10000。

示例：

C语言实现：

内我的反映是先求出R的二进制长度，然后求在这个长度范围内的质数。大家还记得如何判断一个数是不是质数吗？

判断质数：如果一个数n不能被区间[2，（n^0.5） 1]内的任何一个整数整除，那么n就是一个质数。

我写出来后，一跑发现性能很差，最后发现题目是限制了，R的范围的：最大是10^6，即R的二进制长度最大是20位，那就意味着，我们根本就不用写算法求质数，只需要列出来即可，所以说审题很重要。

下面就是求区间[L R]内的某个数的二进制中1的个数。关于这个问题，我至少想到了3中方法（依次遍历这么low的不算）。篇幅有限，我只写两种。我相信还有其他的办法，大家可以自己思考。

方法一：

使用位操作，n&(n-1) 可以去除n最右边的1，通过这种操作就可以获取n中1的数量，这个算法效率还是不错的，它和n的数值大小无法，只依赖n中1的数量。

我们首先定义了一个primes数组，注意这个数组不是直接存放1~20之间的质数，只存放0或者1，即primes的质数下标对应的值会填充1否则会填充0。例如primes[12] = 0而primes[13] = 1，因为13是质数，而12不是。

这样做的好处如代码15行所示，一旦确定了一个数的二进制中1的数量setCount后，就可以通过他直接访问primes对应的位置的值给res赋值，如果setCount是质数，res会加1。

方法二：

使用编译器内置二进制相关的函数__builtin_popcount()，它可以直接获取一个无符号整数的二进制表示里1的数量。

关于编译器内置二进制相关的函数， 前面的一些题目中已经提到了其他的几种，有兴趣的朋友可以回头看看。编译器内置的函数通常效率都是非常高的。

python语言的实现：

python的实现和C语言的实现原理一致。本来是和C语言的方法1一样用位操作的方法来获取1的数量，但是提交几次发现效率并不是很好，反而不如直接转成下面字符串的形式效率高。

我查询了一下python的源码发现count()是在底层用C来实现的，虽然依然是遍历字符串，但是纯C的实现，在这里显然是比python实现要快。

Java语言的实现：

内java的实现和C语言基本一致，唯一不同的还是关于如何获取整数的二进制1数量的实现上。

python一样，用bitCount()效率要比循环位操作的实现高。

另外，质素列表的定义和C语言实现一样，这样可以直接通过下标获取值。

代码如下：