分类：
2012-03-07 00:28:03
这是一个在面试中经常被问到的问题。这道题有很多的方法来解答，下面是我掌握的一些比较简单的方法。
为什么叫普通法呢？我觉得当大家接触到这个问题的时候，第一时间想到的应该就是这种方法，应用位运算。具体的实现代码如下：
int Bit_Count(unsigned char data)
{
unsigned int count = 0 ; // 计数器
while (data > 0)
{
if(data & 1) // 当前位是1
++count ; // 计数器加1
data >>= 1 ; // 移位
}
return count ;
}
当然在这里面，可以用不同的循环结构，像do…while、for等结构都可以实现的，其效果相差并不是很大的。
这种方法是在网上找到的。之所以叫快速法，因为其运算次数与输入data的大小无关，只与data中1的个数有关。如果data中有k个1，那个这个方法只需要循环k次就可以了。其原理是不断的清楚data的二进制表示中最右边的1，同时累加器累加，直至data减为0。具体的代码如下：
int Bit_Count2(unsigned char data)
{
unsigned int count=0;
while(data!=0)
{
data &=(data-1)
count++;
}
return count;
}
其中的循环结构也可以使用其他的循环结构，达到的效果相差很小。
为什么data &=(data-1)能够清楚最右边的1呢？从二进制的角度来讲，data相当于在data-1的最低位加1。如：8(1000)= 7(0111)+ (0001)，所以8 & 7 = (1000)&(0111)= 0(0000)，清除了8最右边的1(其实就是最高位的1，因为8的二进制中只有一个1)。
位段法实现很简单，定义一个位段结构体。在“位运算”文件中已经对位段做了详细的介绍，这里不做详细的介绍了。直接上代码：
struct byte_data
{
unsigned int a:1;
unsigned int b:1;
unsigned int c:1;
unsigned int d:1;
unsigned int e:1;
unsigned int f:1;
unsigned int g:1;
unsigned int h:1;
};
unsigned int Bit_Count3(unsigned char data)
{
struct byte_data *bd = (struct byte_data *)&data;
return (bd->a+bd->b+bd->c+bd->d+bd->e+bd->f+bd->g+bd->h);
}
这是一个网友推荐的算法，我也不知道为什么叫平行算法。上代码吧！
int Bit_Count4(unsigned char data)
{
data = (data & 0x55) + ((data >> 1) & 0x55) ;
data = (data & 0x33) + ((data >> 2) & 0x33) ;
data = (data & 0x0f) + ((data >> 4) & 0x0f) ;
data = (data & 0x00) + ((data >> 8) & 0x00) ;
return data ;
}
速度不一定是最快的，但是想法绝对是巧妙。原理：先将data写成二进制形式， 然后将二进制位与0x55相与，然后右移移位，再与0x55相与，然后在计算下一位，一次这样计算，右移，直至data为0为止。如7，转换为二进制位0000 0111，先将它和0x55(0101 0101)相与，就可以确定第0位和第2位为1，即1的个数为2，接着右移一位，继续与0x55相与，继而就确定了第1的1，从第一个表达式就可以确定7中1的个数有3个。下面第二个表达式，和上面上面的分析一样，一位一位的计算data 数中1的个数。最后得出7的中1的个数为3。大概就是这么一个过程，相信这样应该会比较好理解一点。
查表法有分为动态建表法和静态表两种方法。
首先说一下动态建表法，动态建表法是因为表示在程序运行过程中运行时动态创建，所以速度上肯定会慢一点。下面先说一下动态建表法的填表原理，根据奇偶性来分析，对于任意的一个整数n:
1、如果它是偶数，那个n的二进制中1的个数与n/2中的1的个数是相同的，比如4 和2的二进制中1的个数都为1,6和4的二进制中1的个数都为2。为什么呢？？因 为n是又n/2左移以为而来，而以为运算不会增加其中1的个数。
2、如果n是奇数，那么n的二进制中1的个数是n/2中1的个数加1，比如7的二进制 中有三个1,7/2=3的二进制中有两个1。为什么呢？？因为当n为奇数时，n相当于 n/2左移一位再加1。
下面具体看以一下动态建表的使用：
int Bit_Count5(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 ;
}
上面程序是实习对一个32位的无符号数的求解方法。对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8=256中01的组合方式，这也是为什么表的大小为256的原因。注意其中的类型转换：unsigned char * p = (unsigned char *) &n，先取到n的地址，然后转换为unsigned char *，这样一个unsigned int对应四个unsigned char，分别取出来计算即可。如：以87654321为例，先将他写成二进制形式8bit一组，共四组，这四组中1的个数分别为4,4,3,2，所以1的个数为13。如下等式：10000111 01100101 01000011 0010001=4+4+3+2=13.
静态表法：静态表即静态的构建一个表。对于本例，我们要求char型数据的二进制数中1的个数，一个char型数据是8位，那我们建一个大小为16的表就可以了！下面是程序的实现：
int Bit_Count6(unsigned int n)
{
static unsigned int table[16] =
{
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
} ;
unsigned int count = 0 ;
unsigned char *p=(unsigned char * )&data;
count=table[p[0]];
return count ;
}
对于一个包含16个元素的表table,table[i]即i中1的个数，这里的i是[0-16]之间任意一个值。
既然有这么多得方法，肯定有一种方法是最快的。但是这个最快的也不是绝对的，对每个数求1的执行速度是不一样的。下面是两种情况：
用5种方法求同一个数的速度比较(假设程序执行10000次)，共测了5次，比较详情见下表 1。
表 1：
|
|
普通法(usec) |
快速法(usec) |
位段法(usec) |
平行算法(usec) |
查表法(usec) |
|
1 |
84 |
79 |
83 |
71 |
89 |
|
2 |
83 |
79 |
83 |
71 |
89 |
|
3 |
81 |
79 |
84 |
71 |
89 |
|
4 |
80 |
80 |
84 |
72 |
89 |
|
5 |
81 |
80 |
83 |
71 |
89 |
从上表可以马虎的看出一些方法的效率。当然这不是绝对的。但是这个表格应该可以说明一些问题。
问题补充：在上面的时间效率的比较中，如过在建表的时候加上static关键字，在同样的条件下，没加static关键字执行的时间是加了static关键字执行时间的一半还要多一点。Static关键字在这里到底起了上面作用？效果会有如此之大的变化？
问题解答(20111128):
在这里涉及到变量编译后在内存中的存储位置。Static修饰的变量是静态变量，存放在静态区，且静态变量只需要在程序开始时进行一次初始化就可以了，不需要每次调用的时候都初始化，静态的变量在程序运行过程中长期有效的。局部变量在每次程序调用的时候都要进行初始化，在程序一次调用之后其内存空间就不存在了，下次再调用的时候又要重新申请内存空门。所以，在这里使用static修饰为静态的数组空间，在程序的执行过程中，其内存空间是一直存在的。
