关于“计算一个字节里（byte）里面有多少bit被置1”的思考

昨天看了一道常见的嵌入式C语言面试题“计算一个字节里（byte）里面有多少bit被置1”，从技术上来说，写出这个程序并不是很难，采用“按位与”和“移位操作（右移）”即可。可当我写了一半的时候，遇到了一个问题，假如所输入的字节中是负数，而编译器遇右移操作时，是采用“算术移位”，那可是一个麻烦的事了。下面就让我分析一下。
在网上常见的实现这个程序的代码如下：
#include <stdio.h>

unsigned count_bit1(int date)
{
    unsigned count=0;        //置0计数
    while(date)
    {
       count+=date&1;   //检查Num最后一位是否为1
       date>>=1;        //位移一位
    }
    return count;
} 

int main()
{
int view;
unsigned all_bit1;

scanf("%d",&view);
all_bit1=count_bit1(view);
printf("%d\n",all_bit1);

return 0;
}

在分析之前，先说一下“右移操作”这个事儿。如果右移操作一个数是非负数，那么左边全是补0，比如：3>>1  0000 0011（假如是8位机）>>1 其结果就是0000 0001。但假如这个数是负数，可能有两种情况，就是“逻辑移位”或者“算术移位”，这视编译器而定。逻辑移位移左边补0，算术移位左边补1。比如-3>>1  1111 1101>>1 。 假如是逻辑移位，其结果就是0111 1110，假如是算术移位，其结果就是1111 1110。
好了，下面我们再来分析一下这个程序，假如你的人品很好，使用的编译器是“逻辑移位”，这个程序，并不会出现问题，可以得出正确的结果。而假如是“算术移位”，又是输入的负数，那么此时date这个数，从左向右，不断的填入1，移位8次后，data就是1111 1111了，下面移位也是如此。那么此时while（date）必然都是为真，就成为死循环，一直停在这里运行。我用了TC 2.0和C–Free 5.0试了一下，都是这种情况。所以这个程序移植性并不是很好。
避免这种情况的一个方法，就是采用“左移操作”，这个的确可以避免上面的问题，但是又遇到了一个问题，就是和data按位与的标准值应该怎么取。在前面的程序中，采用的是“左移操作”，选1即可。当然你也可以说取1000 0000 。这也是一个方法，但这是在8位机上，假如16位，就是1000 0000 0000 0000,32位机就是….，显然也不是具有很好的移植性。当然可以实现某种变化，避免具体是多少位机，自动生成需要标准值，这是最好的方法（一个典型的列子，就是实现一个字节全为1，只要~0，即可，可避免多少位机的影响。）。但我想了半天，也没有想出。如果哪位大虾想出，指点我一下，到时必然泪流满面啊（[e-mail]）。
经过俺的苦思冥想，写出了下面的程序：
#include <stdio.h>

unsigned count_bit1(int data)
{
unsigned count=0;
int bit_1=1;
while(bit_1)
{
if(data&bit_1)
{
count+=1;
}
        bit_1<<=1;
}
return count;
}

int main()
{
int view;
unsigned all_bit1;

scanf("%d",&view);
all_bit1=count_bit1(view);
printf("%d\n",all_bit1);

return 0;
}

既然对输入的值进行移位，会产生一些问题，那我们为什么不用标准值进行移位呢？先定义一个bit_1=1,这避免的具体多少位机的影响，对其“左移操作”，就避免“算术移位”，将产生的值每次和data按位与，最终bit_1=0，结束。
当然这个程序也存在一个问题，就是效率可能没有上面的那个高，因为不管输入什么样的值，都需要移动你机器的位数（假如是32位机，就移动32次）。即使你的data的值是1，也需要移动32次。但是为了实现良好的移植性，牺牲一点可能较低的效率，也是可取的。



在网上还看到了另一个版本的程序，其可读性较差，在输入一个负数是，虽然不是进入死循环，但却得到一个错误的值。
#include <stdio.h>

unsigned count_bit1(int data)
{
    unsigned count=0;        //置0计数
    
while(data)
    {
       count+=data%2;   //检查Num最后一位是否为1
       data/=2;        //位移一位
    }
    return count;
} 

int main()
{
int view;
unsigned all_bit1;

scanf("%d",&view);
all_bit1=count_bit1(view);
printf("%d\n",all_bit1);

return 0;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

1.为啥要用int而不是unsigned int？用unsigned int就没有符号位的问题

2.普遍用的求一个数有几位置1的代码是这样子的, 32位的这样子:

int b1c( unsigned x )
{
x = (x&0x55555555) + ((x&0xaaaaaaaa)>>1);
x = (x&0x33333333) + ((x&0xcccccccc)>>2);
x = (x&0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);
x = (x&0x00ff00ff) + ((x&0xff00ff00)>>8);
x = (x&0x0000ffff) + ((x&0xffff0000)>>16);
return x;
}

这个问题叫做汉明距离 请楼主自行wiki英文的hamming weight和hamming code 或者中文的汉明距离

3．  二进制中1的个数

统计二进制中1的个数可以直接移位再判断，当然像《编程之美》书中用循环移位计数或先打一个表再计算都可以。本文详细讲解一种高效的方法。以34520为例，可以通过下面四步来计算其二进制中1的个数二进制中1的个数。

第一步：每2位为一组，组内高低位相加

      10 00 01 10  11 01 10 00

  -->01 00 01 01  10 01 01 00

第二步：每4位为一组，组内高低位相加

      0100 0101 1001 0100

  -->0001 0010 0011 0001

第三步：每8位为一组，组内高低位相加

      00010010 00110001

  -->00000011 00000100

第四步：每16位为一组，组内高低位相加

      00000011 00000100

  -->00000000 00000111

这样最后得到的00000000 00000111即7即34520二进制中1的个数。类似上文中对二进制逆序的做法不难实现第一步的代码：

       x = ((x & 0xAAAA) >> 1) + (x & 0x5555);

好的，有了第一步，后面几步就请读者完成下吧，先动动笔再看下面的完整代码：
[cpp] view plaincopy

    //二进制中1的个数  by MoreWindows( http://blog.csdn.net/MoreWindows )   
    #include <stdio.h>  
    template <class T>  
    void PrintfBinary(T a)  
    {  
        int i;  
        for (i = sizeof(a) * 8 - 1; i >= 0; --i)  
        {  
            if ((a >> i) & 1)  
                putchar('1');  
            else   
                putchar('0');  
            if (i == 8)  
                putchar(' ');  
        }  
        putchar('\n');  
    }  
    int main()  
    {  
        printf("二进制中1的个数 --- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");  
          
        unsigned short a = 34520;  
        printf("原数    %6d的二进制为:  ", a);  
        PrintfBinary(a);  
          
        a = ((a & 0xAAAA) >> 1) + (a & 0x5555);  
        a = ((a & 0xCCCC) >> 2) + (a & 0x3333);  
        a = ((a & 0xF0F0) >> 4) + (a & 0x0F0F);  
        a = ((a & 0xFF00) >> 8) + (a & 0x00FF);     
        printf("计算结果%6d的二进制为:  ", a);     
        PrintfBinary(a);  
        return 0;  
    }  

更多0