面试系列8返回整数中为1的位数（优化版）

原题：
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...》中有解答，网友一修指出了答案的缺点，并给出了另外一个效率极高的算法，非常感谢，贴出来跟大家分享。
/*
* 平均效率比较低，最坏情况要循环sizeof(x) * 8次。
* 看看下面这个函数，是针对32位的，至于其它位数稍加修改就可以了。
*
* 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
}
补充一下：
因为网友一修给出的代码中注释比较少，而精炼的代码又比较难理解，所以我来说说我的看法，如果有不对的地方，还请大家多多指导。
关于二进制数的理解，二进制数每一位只能为0和1，因此在这个地方，我们可以理解为每一位都可以表示该位中包含1的数目。
看第一行代码：x = (x & 0x55555555ul) + ((x >> 1) & 0x55555555ul);
5的二进制是 0101，当x & 0x55555555ul得出的结果是保留了0, 2, 4, 6 ... , 30 位的值，即 0, 2, 4, 6 ,... , 30 位中包含1的数目；那么自然可以理解(x >> 1) & 0x55555555ul得出的结果是保留了1, 3, 5, 7, ... , 31 位的值，即 1, 3, 5, 7, ..., 31 位中包含1的数目。把两者相加起来：
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数每两位看成一个最小单元，x+y的值z即为这个两位最小单元中，1的个数。可以看出，巧妙地把两个加数种0的空间用来保存进位。那么到现在为止，我们就得到了数x中，每两位为最小单位，每两位中的数值表示着这两位中1的个数。
依此类推，接下来我们用同样的方法计算以4位为最小单位，4位中的数值表示该4位中1的个数，即：x = (x & 0x33333333ul) + ((x >> 2) & 0x33333333ul);
然后是 8位， 16位，当计算到以32位为最小单位，32位中的数值表示该32位中1的个数的时候，答案就揭晓了。
trackback: http://tb.blog.csdn.net/trackback.aspx?postid=812845