原題：
??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)友一修給出的代碼中注釋比較少，而精煉的代碼又比較難理解，所以我來說說我的看法，如果有不對的地方，還請大家多多指導。
關于二進制數(shù)的理解，二進制數(shù)每一位只能為0和1，因此在這個地方，我們可以理解為每一位都可以表示該位中包含1的數(shù)目。
看第一行代碼：x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);
5的二進制是 0101，當x & 0x55555555UL得出的結果是保留了0, 2, 4, 6 ... , 30 位的值，即 0, 2, 4, 6 ,... , 30 位中包含1的數(shù)目；那么自然可以理解(x >> 1) & 0x55555555UL得出的結果是保留了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位，當計算到以32位為最小單位，32位中的數(shù)值表示該32位中1的個數(shù)的時候，答案就揭曉了。
?