面试的时候，除了TopK，你有没有被问过：一个正整数的二进制表示有多少个1？画外音：姊妹篇《一次搞透，面试中的TopK问题!》。例如：uint32_ti=58585858；i的二进制表示是：0000001101111011111001100000010因此，i的二进制表示包含15个1。有几种方法，而这些思路又包含了什么样的优化思路，今天就和大家聊一聊。1、位移法。思路：由于输入n为uint32，每次取n的最低位判断是否为1，移位32次，循环判断。伪代码：do{if((n&1)==1){result++;}n>>=1;i++;}while(i<32);分析：无论n的二进制表示中包含多少个1，都需要循环计算32次，比较耗时。可不可以每次都消掉一个1，从而减少计算次数？二、求和法。观察n和n-1这两个数的二进制表示：（1）最后的1会变成0；(2)最后一个1之后的全0都会变成1；(3)其他位同上；栗子：x=10110000x-1=10101111x&(x-1)=10100000因此n&(n-1)的运算可以起到“消去最后1”的效果。思路：逐步通过n&(n-1)消除n末尾的1，消除多少次，1就有多少次。伪代码：while(n){result++;n&=(n-1);}分析：在该方法中，n的二进制表示中1的个数会被计算多少次。通常，n的长度为32位。如果完全随机选择n的值，平均期望由16个1组成，平均16次，这样就节省了一半的计算量。三、查表法。以空间换时间是算法优化中最常用的方法。如果你有相对足够的内存，你可以有一个更快的算法。思路：uint32的一个正整数n，一旦确定了n的值，那么n的二进制表示中包含多少个1也就确定了，理论上不需要重新计算：1的二进制表示中包含1个1，而2的二进制表示包含113的二进制表示包含2个1...58585858的二进制表示包含15个1...提前计算结果数组：result[1]=1;result[2]=1;result[3]=2;...result[58585858]=15;...伪代码：returnresult[n];查表方式的优点是时间复杂度为O(1)，潜在的问题是需要大量内存。内存分析：如果要分析的整数是uint32，table数组需要记录2^32个正整数的结果。n的二进制表示最多包含32个1，存储结果的个数可以5位存储。因此总共需要2^32*5bit=2.5GB内存。画外音：5位，可表示00000-11111的32个数字。四、第二种查表法。查表法速度很快，只需要查询一次，但太耗内存，在项目中很少用到。算法设计本身就是时间复杂度和空间复杂度之间的折衷。增加计算次数往往可以减少存储空间。思路：（1）将uint32的正整数n分解为低16位正整数n1和高16位正整数n2；(2)对n1查表一次，其二进制表示为1；(3)对n2表查一次，其二进制表示包含b个1；(4)那么，n的二进制表示包含a+b个1；伪代码：uint16nn1=n&0xFFFF；uint16n2=(n>>16)&0xFFFF；returnresult[n1]+result[n2]；问题来了：计算量翻倍（一次查表变成两次），内存空间要减半？内存分析：待分析的整数变为uint16，table数组需要记录2^16个正整数的结果。n1和n2的二进制表示最多包含16个1，存储结果的个数可以4位存储。因此总共需要2^16*4bit=32KB的内存。太奇妙了！！！计算量增加了一倍，但内存占用从2.5G下降到32K（1万多倍）。是不是很有趣？五、总结1号不难；但思路有个优化过程，并不简单：（1）置换法，32次计算；(2)n&(n-1)，平均可以剔除a1,16次计算；(3)查表法，1张查表，2.5G内存；(4)二次查表法，2次查表，32K内存；知其然，知其所以然。想法比结论更重要。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
