求一個(gè)unsigned int 數(shù)的二進(jìn)制表示中有多少個(gè)1？
這是一道面試題可以用以下的一些方案。
第一種是很容易想到的采用循環(huán)的方式并且與1進(jìn)行位與運(yùn)算，具體代碼如下。

1unsigned int GetBitNumOfOne_ByLoop1(unsigned int nValue)
2{
3 const unsigned int nNumOfBitInByte = 8;
4 unsigned int nBitMask = 1;
5 unsigned int nBitNum = 0;
6 for(unsigned int i = 0 ; i < sizeof(nValue) * nNumOfBitInByte ; i++)
7 {
8 (0 < (nValue & nBitMask)) ? nBitNum++ : 0;
9 nBitMask<<=1;
10 }
11 return nBitNum;
12}
13unsigned int GetBitNumOfOne_ByLoop2(unsigned int nValue)
14{
15 const unsigned int nNumOfBitInByte = 8;
16 unsigned int nBitMask = 1;
17 unsigned int nBitNum = 0;
18 for(unsigned int i = 0 ; i < sizeof(nValue) * nNumOfBitInByte ; i++)
19 {
20 (0 < (nValue & nBitMask)) ? nBitNum++ : 0;
21 nValue>>=1;
22 }
23 return nBitNum;
24}

這兩種做法很相像，卻別就是在是對(duì)nBitMask進(jìn)行左移還是對(duì)nValue進(jìn)行右移。
當(dāng)然了以上的兩個(gè)方法存在一個(gè)問(wèn)題：不管如何這個(gè)函數(shù)肯定要循環(huán)32次（對(duì)于32平臺(tái)來(lái)說(shuō)）。
那又沒(méi)有更好的方法？當(dāng)然有，請(qǐng)看下面：
1unsigned int GetBitNumOfOne_ByLoop3(unsigned int nValue)
2{
3 unsigned int nBitNum = 0;
4 while(0 < nValue)
5 {
6 nValue &=(nValue - 1);
7 nBitNum++;
8 }
9 return nBitNum;
10}

假如使用參數(shù)12345（二進(jìn)制是11000000111001）調(diào)用該函數(shù)，該函數(shù)的執(zhí)行情況如下：
第一次進(jìn)入循環(huán)
0 < 11000000111001
11000000111001 &= (11000000111001 - 1) 之后 nValue 的值 是 11000000111000
nBitNum 的值是1
經(jīng)過(guò)本次循環(huán)之后11000000111001 變成了 11000000111000 比之前少了一個(gè)1
第二次進(jìn)入循環(huán)
0 < 11000000111000
11000000111000 &= (11000000111000 - 1) 之后 nValue 的值 是 11000000110000
nBitNum 的值是2
經(jīng)過(guò)本次循環(huán)之后11000000111000 變成了 11000000110000 比之前少了一個(gè)1
第三次進(jìn)入循環(huán)
0 < 11000000110000
11000000110000 &= (11000000110000 - 1) 之后 nValue 的值 是 11000000100000
nBitNum 的值是3
經(jīng)過(guò)本次循環(huán)之后11000000110000 變成了 11000000100000 比之前少了一個(gè)1
經(jīng)過(guò)以上3次循環(huán)情況的說(shuō)明，我相信你一定看出了些什么吧。nValue &=(nValue - 1)，這句
代碼實(shí)際上就是把nValue 的某位及其以后的所有位都變成0，當(dāng)nValue最后變成0的時(shí)候循環(huán)結(jié)束，
且nBitNum 記錄的就是1的個(gè)數(shù)。
上面的做法已經(jīng)很不錯(cuò)了，但是作為程序員的你是否會(huì)有疑問(wèn)，"還有其他的方法嗎？"。
有，當(dāng)然有！請(qǐng)看下面的代碼：
1unsigned int GetBitNumOfOne(unsigned int nValue)
2{
3 nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
4 nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
5 nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);
6 nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);
7 nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);
8
9 return nValue;
10}

假如你是第一次看到這些代碼，你是否能看明白？呵呵，本人第一次看到這些代碼的時(shí)候看了好久才感覺(jué)
好像有點(diǎn)明白。下面我就以一個(gè)例子來(lái)說(shuō)明上面的代碼是如何做到的。
假如參數(shù)是0xffffffff。
第一行代碼：
nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
a的二進(jìn)制表示是：1010
5的二進(jìn)制表示是：0101
0xffffffff 與 0xaaaaaaaa 進(jìn)行與運(yùn)算之后是0x10101010101010101010101010101010
然后再進(jìn)行左移操作后是0x01010101010101010101010101010101
0x55555555 & nValue 進(jìn)行與運(yùn)算之后是0x01010101010101010101010101010101
然后0x01010101010101010101010101010101 & 0x01010101010101010101010101010101
得到0x10101010101010101010101010101010
我們把得到的結(jié)果分成16組0x10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
每組的10單獨(dú)來(lái)看是不是十進(jìn)制的2
我們0x01010101010101010101010101010101和0x01010101010101010101010101010101這兩個(gè)數(shù)也按照上面的方法分成
16個(gè)組0x01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
0x01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
那么這兩個(gè)數(shù)的每一個(gè)組都是01 那么兩個(gè)01 里面有幾個(gè)1，是不是2個(gè)。這是2是不是二進(jìn)制的10，然后16個(gè)10組合起來(lái)是不是
0x10101010101010101010101010101010

第二行代碼：
nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
此時(shí)nValue是0x10101010101010101010101010101010
c的二進(jìn)制表示是：1100
3的二進(jìn)制表示是：0011
0xcccccccc 與 nValue) 進(jìn)行與運(yùn)算之后是0x10001000100010001000100010001000
然后再進(jìn)行左移操作后是0x00100010001000100010001000100010
0x33333333 & nValue 進(jìn)行與運(yùn)算之后是0x00100010001000100010001000100010

然后0x00100010001000100010001000100010 & 0x00100010001000100010001000100010
得到0x01000100010001000100010001000100
我們把得到的結(jié)果分成8組0x0100 0100 0100 0100 0100 0100 0100 0100
每組的0100單獨(dú)來(lái)看是不是十進(jìn)制的4 總共有多少個(gè)4？是不是8個(gè)，8×4=32。

以下的代碼：
nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);
nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);
nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);
請(qǐng)自己按照上面的方法做一遍，就會(huì)發(fā)現(xiàn)規(guī)律：第一次32位數(shù)分成32組，第二次分成16組，第三次分成8，第四次分成4，第五次分成2組。
如果還是不明白請(qǐng)多看看，然后多選擇幾個(gè)參數(shù)進(jìn)行試驗(yàn)，多試幾次肯定會(huì)明白的。

看了這么多解法是不是有中很過(guò)癮的感覺(jué)，當(dāng)我知道有這么多解法是也很過(guò)癮，也很遺憾。遺憾什么呢？遺憾當(dāng)時(shí)我碰到這道面試題的時(shí)候
只想到了采用循環(huán)的方法，可是那個(gè)面試題上明確說(shuō)明不準(zhǔn)使用循環(huán)??！當(dāng)時(shí)很郁悶?。?BR>鄭重聲明：上面最后兩個(gè)解法非本人原創(chuàng)，本人只是總結(jié)歸納，向想出這么好方法的前輩高人致敬！