问题描述:
对于1个字节(8bit)无符号整型变量,求其二进制表示中“1”的个数
解法一:除2取余
(对于二进制操作,除以一个2,原来的数字会减少一个0。如果除的过程中有余数,就表示当前位置有一个1)
int Count(BYTE v) { int num = 0; while(v) { if(v%2==1) num++; v=v/2; } return num; }
解法二:位移操作
(对于二进制向右移位操作同样可以达到解法一的目的,但是比除、余操作效率高)
int Count(BYTE v) { int num = 0; while(v) { num+=v&0x01; v>>=1; } return num; }
解法三:
只考虑有1的情况(清除最低位的1)
int Count(BYTE v) { int num = 0; while(v) { v&=(v-1); num++; } return num; }
解法四:分支操作
(看似直接,但是执行效率可能会低于解法二、三)空间换时间
int Count(BYTE v) { int num = 0; switch(v) { case 0x0: num = 0; break; case 0x1: case 0x2: case 0x4: case 0x8: case 0x10: case 0x20: case 0x40: case 0x80: num = 1; break; case 0x3: case 0x6: case 0xc: case 0x18: case 0x30: case 0x60: case 0xc0: num = 2; break; //... } return num; }
解法五:查表法
空间换时间
把0~255中“1”的个数直接存储在数组中,v作为数组下标,countTable[v]就是v中“1”的个数。算法时间复杂度仅为O(1)
int countTable[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; int Count(BYTE v) { return countTbale[v]; }
扩展问题:
问题1:对于32位的DWORD,可以动态建表或静态建表
1)动态建表
由于表示在程序运行时动态创建的,所以速度上肯定会慢一些,
把这个版本放在这里,有两个原因
1.填表的方法,这个方法的确很巧妙。
2.类型转换,这里不能使用传统的强制转换,而是先取地址再转换成对应的指针类型。
代码如下:
int BitCount(unsigned int n) { // 建表 unsigned char BitsSetTable256[256] = {0} ; // 初始化表 for (int i= 0; i<256; i++) BitsSetTable256[i]=(i&1)+BitsSetTable256[i/2]; unsigned int c = 0 ; // 查表 unsigned char *p=(unsigned char *) &n; //一个字节一个字节 c=BitsSetTable256[p[0]]+BitsSetTable256[p[1]]+ BitsSetTable256[p[2]]+BitsSetTable256[p[3]]; return c ; }
2)静态建表
首先构造一个包含256个元素的表table,table[i]即i中1的个数,
这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n,
我们将其拆分成四个8bit,然后分别求出每个8bit中1的个数,再累加求和即可,这里用移位的方法,每次右移8位,并与0xff相与,取得最低位的8bit,累加后继续移位,如此往复,直到n为0。所以对于任意一个32位整数,需要查表4次。以十进制数2882400018为例,其对应的二进制数为10101011110011011110111100010010,对应的四次查表过程如下:红色表示当前8bit,绿色表示右移后高位补零。
第一次(n & 0xff) 10101011110011011110111100010010
第二次((n >> 8) & 0xff) 00000000101010111100110111101111
第三次((n >> 16) & 0xff)00000000000000001010101111001101
第四次((n >> 24) & 0xff)00000000000000000000000010101011
代码如下:
int BitCount7(unsigned int n) { unsigned int table[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; return table[n & 0xff] + table[(n >> 8) & 0xff] + table[(n >> 16) & 0xff] + table[(n >> 24) & 0xff] ; }
2.问题2,给定A和B,问把A变为B需要改变多少位?也就是说有多少位不同?
首先异或,则不同的位结果为1,然后统计异或结果中1的个数;