关于“计算一个字节里（byte）里边有多少bit被置1”的思考
关于“计算一个字节里（byte）里面有多少bit被置1”的思考
[size=11px]昨天看了一道常见的嵌入式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，即可，可避免多少位机的影响。）。但我想了半天，也没有想出。如果哪位大虾想出，指点我一下，到时必然泪流满面啊（dingzj2000@163.com）。
经过俺的苦思冥想，写出了下面的程序：
#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;
}[/size]
------解决方案--------------------
这个正解，不需考虑正负值问题。
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.****.net/MoreWindows )
[size=11px]昨天看了一道常见的嵌入式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，即可，可避免多少位机的影响。）。但我想了半天，也没有想出。如果哪位大虾想出，指点我一下，到时必然泪流满面啊（dingzj2000@163.com）。
经过俺的苦思冥想，写出了下面的程序：
#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;
}[/size]
------解决方案--------------------
这个正解，不需考虑正负值问题。
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.****.net/MoreWindows )