題目：給定一個(gè)無(wú)符號(hào)32位整數(shù)x，求x的二進(jìn)制表示法中含1的個(gè)數(shù)？
第一種算法：
int OneCount(unsigned int x)
{
for(int count=0; x>0; count++)
x&=x-1;//把最后面的1變0
return count;
}
上面算法的時(shí)間復(fù)雜度就是1的個(gè)數(shù)。
第二種算法（查表法）：
const int idx[256]={0,1,1,,8}//0~255中含1的個(gè)數(shù)
int OneCount(unsigned int x)
{
int count=0;
for(; x>0; x>>=8)
count+=idx[x&255];
return count;
}
上面算法最多只需要4次循環(huán)，用空間換取時(shí)間。
第二種算法的另一種形式：
const int idx[256]={0,1,1,..,8}
int OneCount(unsigned int x)
{
unsigned char* p=(unsigned char*)&x;
return idx[*p]+idx[*(p+1)]+idx[*(p+2)]+idx[*(p+3)];
}
第三種算法：
int OneCount(unsigned int x)
{
x=(x&0x55555555UL)+((x>>1)&0x55555555UL); //1
x=(x&0x33333333UL)+((x>>2)&0x33333333UL);//2
x=(x&0x0f0f0f0fUL)+((x>>4)&0x0f0f0f0fUL); //3
x=(x&0x00ff00ffUL)+((x>>8)&0x00ff00ffUL); //4
x=(x&0x0000ffffUL)+((x>>16)&0x0000ffffUL);//5
return x;
}
解釋：比如對(duì)于一個(gè)8位的整數(shù)122，用二進(jìn)制表達(dá)0111 1010（abcd efgh），第1行代碼的功能是x=0b0d 0f0h+0a0c 0e0g，兩位一組，分別計(jì)算四組（a,b; c,d; e,f; g,h; ）中1的個(gè)數(shù)，本例中x=0101 0000+0001 0101=0110 0101（更新的abcd efgh），在此基礎(chǔ)上，再分組，就是第二行的功能x=00cd 00gh+00ab 00ef，四位一組（abcd； efgh），分別計(jì)算這兩組包含1的個(gè)數(shù)，本例中x=0010 0001+0001 0001=0011 0010（更新abcd efgh），再8位一組，如第三行所示，x=0000 efgh+0000abcd=0000 0010+0000 0011=0000 0101=5，所以該整數(shù)122共包含5個(gè)1。
本算法思想：歸并，對(duì)于一個(gè)32位的整數(shù)，先分成16組，統(tǒng)計(jì)每組（2位）中1的個(gè)數(shù)，再將統(tǒng)計(jì)的結(jié)果兩兩合并，得到8組，在此基礎(chǔ)上又合并得到4組，2組，1組，進(jìn)而得到最終結(jié)果。