首页 > 代码库 > 【编程之美学习笔记】2.1求二进制数中1的个数
【编程之美学习笔记】2.1求二进制数中1的个数
问题：对于一个字节（8bit）的无符号整型变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能高。
解法一：除、余操作
我们知道，对于二进制操作，除以一个2，原来的数字将会减少一个0，如果除的过程中有余，那么就表示当前位置有一个1，所以可通过相除和判断余数的值来分析。
【时间复杂度O（log2v），log2v为二进制数的位数，空间复杂度O（1）】
1 int Count(int v){2 int num = 0;3 while(v){4 if(v % 2 == 1) num++;5 v = v/ 2;6 }7 return num;8 }
解法二：位操作
我们也知道，向右移位操作同样可以达到相除的目的，对于如何判断移位之后是否有1存在，可以在右移位过程中，将这个八位数字与00000001进行“与”操作，如果结果为1，则表示当前八位数的最后一位为1，否则为0.
【时间复杂度O（log2v），空间复杂度O（1）】
1 int Count(int v){2 int num = 0;3 while(v){4 num += v & 0x01;5 v >>= 1;6 }7 return num;8 }
解法三：高效位操作
我们发现，前面两种操作，对于一些数，比如10000000，就会浪费大量时间在无用的0上，那么能不能让算法的复杂度只与“1”的个数有关呢？
通过观察发现有个规律：使 v = v & (v - 1)，可以去除数 v 的二进制中最后一个1，
比如 01000010 & （01000010 - 00000001）= 01000000 & 01000001 = 01000000
01000000 & （01000000 - 00000001） = 01000000 & 00111111 = 0
【时间复杂度O（M），即二进制中“1”的个数，空间复杂度O（1）】
1 int Count(int v){2 int num = 0;3 while(v){4 v &= (v-1);5 num++;6 }7 return num;8 }
解法四：分支操作
罗列出0~255的情况，并使用分支操作得到答案。但是这个方法看似直接，执行效率却可能低于上述解法，因为分支语句的执行情况要看具体字节的值，例如，若v = 0，在第一个case就能得出答案，但是若v = 255,则要比较255次！因此该解法并不可取，但提供了个很好的思路，即空间换时间的方法。
1 int Count(int v){ 2 int num = 0; 3 switch(v){ 4 case 0x0: num = 0; break; 5 case 0x1: 6 case 0x2: 7 case 0x4: 8 case 0x8: 9 case 0x10:10 case 0x20:11 case 0x40:12 case 0x80: num = 1; break;13 case 0x3:14 case 0x6:15 case 0xc:16 case 0x18:17 case 0x30:18 case 0x60:19 case 0xc0: num = 2; break;20 //...21 }22 return num;23 }*
解法五：查表法
典型的空间换时间的算法，应题目要求，只要把0~255中“1”的个数直接存储在数组中即可
【时间复杂度O（1），空间复杂度O（N）】
1 int CountTable[256]={ 2 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 3 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 4 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 5 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 6 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 7 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 8 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 9 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,10 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,11 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,12 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,13 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,14 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,15 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,16 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,17 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,18 };19 int Count(int v){20 //check parameter21 return CountTable[v];22 }
网上其他解法：以32位整型为例
解法六：归并法
相邻两两相加，然后四个四个相加，以此类推。最后就能得出各位之和。
1 int Count(int v){ 2 int num = v; 3 int a = 0x55555555;//01010101010101010101010101010101 4 //用于相邻两位相加 5 int b = 0x33333333;//00110011001100110011001100110011 6 //用于相邻四位相加 7 int c = 0x0f0f0f0f;//00001111000011110000111100001111 8 int d = 0x00ff00ff;//00000000111111110000000011111111 9 int e = 0x0000ffff;//0000000000000000111111111111111110 num = (num& a) + ((num >> 1)& a);11 num = (num& b) + ((num >> 2)& b);12 num = (num& c) + ((num >> 4)& c);13 num = (num& d) + ((num >> 8)& d);14 num = (num& e) + ((num >> 16)& e);15 return num;16 }
解法七：HAKMEN算法
首先将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后巧妙的用除63取余得到结果。
因为2^6 = 64，所以v_0 + v_1 * 64 + v_2 * 64 * 64 = v_0 + v_1 + v_2(mod 63),等号表示同余。（表示现在还不是很理解orz）
1 int Count(unsigned v){ 2 unsigned n; 3 n = (v >> 1)& 033333333333; 4 v = v - n; 5 n = (n >> 1)& 033333333333; 6 v = v - n; 7 v = (v + (v >> 3))& 030707070707; 8 v = v % 63; 9 return v;10 }
扩展：由解法三的规律可以轻松判断一个数是否是2的幂。
1 int powof2(int v){2 return (v & (v-1)) == 0;3 }
扩展问题：
1.如果变量是32位的DWORD，你会使用上述的哪一个算法，或者改进哪一个算法？
解法三，六，七。（解法五不合适，因为要求的数组太大了：2^32*sizeof(int)）
2.给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A和B的二进制表示中有多少位是不同的？
答案即A^B 中 1 的个数。
【编程之美学习笔记】2.1求二进制数中1的个数