原題：

??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)友一修指出了答案的缺點，并給出了另外一個效率極高的算法，非常感謝，貼出來跟大家分享。?

/*
?* 平均效率比較低，最壞情況要循環(huán)sizeof(x) * 8次。
?* 看看下面這個函數(shù)，是針對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
}

補充一下：

因為網(wǎng)友一修給出的代碼中注釋比較少，而精煉的代碼又比較難理解，所以我來說說我的看法，如果有不對的地方，還請大家多多指導(dǎo)。

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

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

5的二進制是 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ù)目。把兩者相加起來：

??? 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ù)每兩位看成一個最小單元，x+y的值z即為這個兩位最小單元中，1的個數(shù)。可以看出，巧妙地把兩個加數(shù)種0的空間用來保存進位。那么到現(xiàn)在為止，我們就得到了數(shù)X中，每兩位為最小單位，每兩位中的數(shù)值表示著這兩位中1的個數(shù)。

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

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

?