一道算法面试题：怎么以最快的速度计算出一个二进制数中1的个数

一道算法面试题：如何以最快的速度计算出一个二进制数中1的个数？
如何以最快的速度计算出一个二进制数中1的个数？假设这个二进制数位数可以很长，比如有100位以上或更多。。。

大家说说自己的想法。



------解决方案--------------------
这个不是前一段那个101个面试题中的一题吗。

计算整数number的比特位值为1的位数

int getBits(int number)
{
int retval = 0;

for( ; number; number &= number - 1)
retval++;
return retval;
}
------解决方案--------------------
unsigned int
ones32(register unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x > > 1) & 0x55555555);
x = (((x > > 2) & 0x33333333) + (x & 0x33333333));
x = (((x > > 4) + x) & 0x0f0f0f0f);
x += (x > > 8);
x += (x > > 16);
return(x & 0x0000003f);
}


------解决方案--------------------
http://www.everything2.com/index.pl?node_id=1181258
------解决方案--------------------
关键是：number &= (number - 1)

讨论之。

1)：number 为奇数，则number &= (number - 1)萃取末尾1，并将结果赋给number。计数器显然要加1。
2)：number 为偶数，则number &= (number - 1)number最末尾的1置成0，其余不变，并将结果赋给number。若此时number不为0，则说明仍可继续，由于已经将number最末尾的1置成0，因此，计数器也要加1。

详见《高效程序的奥秘》。