读《C程序设计语言》笔记9

求二进制数中1的个数：

　　上一篇随笔最后写到了统计x二进制表示中1的个数，这里继续记录下其他的方法：

　　1.采用的还是位运算，右移位，每次向右移动移位，判断最低位是否为1，程序如下：

/*************************************
	Description;
		统计x中值为1的二进制位数
*************************************/
#include <stdio.h>

int bitcount(unsigned int x)
{
	int b;
	for(b=0; x!=0; x>>=1)
		if(x & 01)
			b++;
	return b;
}
int main()
{
	unsigned int x;
	printf("请输入需要统计的数字(非负整数)：");
	scanf("%d",&x);
	int numberofone=bitcount(x);
	printf("无符号数x二进制表示中1的个数为: %d\n",numberofone);
	system("pause");
	return 0;
}

执行结果是：

　　

小结：该算法采用了循环，但是每次移位一位，在32位的计算机中，unsigned int为32位，也就是要循环32次。习题2-9中给出了表达式x&=(x-1)，该表达式可以删除x中最右边值为1的一个二进制位。这样就可以采用这个表达式来改进算法了。例如：5，...0101(...代表前面28个0)

(...0101) & (...0101-...0001)=...0100

(...0100) & (...0100-...0001)=...0000

两个1只要计算两次即可，每次删除x中最右边值为1的那个二进制位

算法代码如下：

//改进的算法 
int bitcount(unsigned int x)
{
	int b;
	for(b=0; x!=0; x&=x-1)
			b++;
	return b;
}

　该算法在最坏的情况下（即全部为1）才与上面那个算法的循环次数一样。

ps：更详细的描述可参见《编程之美》p.119