Linux下的位运算应用---求一个char类型的1的个数

这是一个在面试中经常被问到的问题。这道题有很多的方法来解答，下面是我掌握的一些比较简单的方法。

         为什么叫普通法呢？我觉得当大家接触到这个问题的时候，第一时间想到的应该就是这种方法，应用位运算。具体的实现代码如下：

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修饰为静态的数组空间，在程序的执行过程中，其内存空间是一直存在的。