原題：

??Write the function int bitCount(short input) that takes a short as input and
? returns an int.? The function returns the number of bits set in the input
? variable.? For instance:
? bitCount(7) --> 3
? bitCount(2543) --> 9
? bitCount(11111) --> 9

? 該題在《面試系列1...》中有解答，網(wǎng)友一修指出了答案的缺點(diǎn)，并給出了另外一個(gè)效率極高的算法，非常感謝，貼出來(lái)跟大家分享。?

/*
?* 平均效率比較低，最壞情況要循環(huán)sizeof(x) * 8次。
?* 看看下面這個(gè)函數(shù)，是針對(duì)32位的，至于其它位數(shù)稍加修改就可以了。
?*
?* return number of bits set
?*/

unsigned int bitcount32(unsigned int x)
{
??? x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
??? x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
??? // Version 1
??? x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
??? x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
??? x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
??? return x;
#else
??? // Version 2
??? x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
??? x += x >> 8; // 0-16 in 8 bits
??? x += x >> 16; // 0-32 in 8 bits
??? return x & 0xff;
#endif
}

補(bǔ)充一下：

因?yàn)榫W(wǎng)友一修給出的代碼中注釋比較少，而精煉的代碼又比較難理解，所以我來(lái)說(shuō)說(shuō)我的看法，如果有不對(duì)的地方，還請(qǐng)大家多多指導(dǎo)。

關(guān)于二進(jìn)制數(shù)的理解，二進(jìn)制數(shù)每一位只能為0和1，因此在這個(gè)地方，我們可以理解為每一位都可以表示該位中包含1的數(shù)目。

看第一行代碼：x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);

5的二進(jìn)制是 0101，當(dāng)x & 0x55555555UL得出的結(jié)果是保留了0, 2, 4, 6 ... , 30 位的值，即 0, 2, 4, 6 ,... , 30 位中包含1的數(shù)目；那么自然可以理解(x >> 1) & 0x55555555UL得出的結(jié)果是保留了1, 3, 5, 7, ... , 31 位的值，即 1, 3, 5, 7, ..., 31 位中包含1的數(shù)目。把兩者相加起來(lái)：

??? xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx

? +0101 0101 0101 0101 0101 0101 0101 0101

------------------------------------------------------------------------

??? 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x??????????????????????????? （這里的x即為x中?0, 2, 4, ... , 30?位的值）

?

??? 0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx

? +0101 0101 0101 0101 0101 0101 0101 0101

------------------------------------------------------------------------

??? 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y??????????????????????????? （這里的y即為x中 1, 3, 5 , ... , 31 位的值）

?

??? 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x

? +0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y

------------------------------------------------------------------------

??? zz zz zz zz zz zz zz zz

??? 可以把32位的X數(shù)每?jī)晌豢闯梢粋€(gè)最小單元，x+y的值z(mì)即為這個(gè)兩位最小單元中，1的個(gè)數(shù)?？梢钥闯?，巧妙地把兩個(gè)加數(shù)種0的空間用來(lái)保存進(jìn)位。那么到現(xiàn)在為止，我們就得到了數(shù)X中，每?jī)晌粸樽钚挝?，每?jī)晌恢械臄?shù)值表示著這兩位中1的個(gè)數(shù)。

??? 依此類推，接下來(lái)我們用同樣的方法計(jì)算以4位為最小單位，4位中的數(shù)值表示該4位中1的個(gè)數(shù)，即：x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);

??? 然后是 8位， 16位，當(dāng)計(jì)算到以32位為最小單位，32位中的數(shù)值表示該32位中1的個(gè)數(shù)的時(shí)候，答案就揭曉了。

?