求一個二進制數中1的個數

來自筆試題 注意位運算符的使用 要注意基礎啊 = = 

看其他部落格介紹又叫

popcount 算法

 實際應用在   漢明碼 (Hamming Code) 的檢驗中 ，（漢明碼 似曾相識啊 好像在組成原理書上有介紹 —— 講存儲器奇偶校驗那節）

#include<stdio.h>
//輸出二進制數中1的個數
int f1(int x)
{
	int count=0;
	for(;x;)
	{
		count+=x&1;//與運算 x & 00..01 
		x>>=1;// x/2	
	}
	return count;
}
int f2(int x)
{
	int count=0;
	for(;x;)
	{
		x&=x-1;//最右側的 1 消除 1..110 & 1...101 =1...100
					 //同理 使用 x&(x+1) 1..100&1...101=1..100 去掉0 
		count++;
	}
	return count;
}
int f3(int x)
{
	/*
	分治思想：統計每相鄰2位，4位，8位一的個數，求和
	為什麼 &0x55555555（0101 0101...） 
	：abcd & (0101)=0b0d abcd>>2&(0101)=0a0c  a|b|c|d->a+b|c+d 
	*/
	//注意 必須加括号 因為單目運算符向右結合 
	//（ 1&1+1&1 ）==（（1&1 +1）&1）
	x=x&0x55555555+((x>>1)&0x55555555);//0101
	x=x&0x33333333+((x>>2)&0x33333333);//0011
	x=x&0x0f0f0f0f+((x>>4)&0x0f0f0f0f);//00001111
	x=x&0x00ff00ff+((x>>8)&0x00ff00ff);//.....
	x=x&0x0000ffff+((x>>16)&0x0000ffff);
	return x;
}
int main()
{
	printf("%d\n%d\n%d\n",f1(192),f2(127),f3(7));
	//printf("%d",(3&1+3)&1);
	return  0;
}