101道经典面试题 - 09

09. Give a very good method to count the number of ones in a "n" (e.g 32) bit number.

译：给出一个好方法，求一个数的比特位值为1的位数.

18 个解决方案

#1

应该是对所有字节查表求1的个数
然后相加吧
非常期待下面的题呵呵

#2

上面有理,
但接下来仍要考虑如何快速统计一个字节中的'1'的个数?

#3

对于unsigned char，取值从0到255，所以用一个256字节的表就可以描述所有的情况，折中的做法可能是每次检测4位，这样表的大小降到16

#4

诸位可能没有理解题意，要求是求出有多少个1就行了，不必求1在第几位；所以考虑一般的位运算就可以解决，无须额外的辅助

#5

一般的位运算复杂度为O(n)，如果使用辅助的空间，可以降到O(1)

#6

老问题了
int getBits(int number)
{
   int retval = 0;
   for ( ; number; number &= number - 1 ) retval++;
   return retval;
}

#7

查表的方法因为我没想过，所以批评错了，呵呵；iceheart(冷酷的心) 用的是经典方法，
利用了 number &= number - 1 可以消去一个1的规律，这个方法的确是很美的；

#8

忘了在那里见过的：
x = (x & 0x55555555) + ((x>>1) & 0x55555555);
x = (x & 0x33333333) + ((x>>2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x>>4) & 0x0f0f0f0f);
x += (x>>8);
x += (x>>16);
return (x & 0x00ff);

当 1 比较少时还是 iceheart 的快。

#9

x = (x & 0x55555555) + ((x>>1) & 0x55555555);
x = (x & 0x33333333) + ((x>>2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x>>4) & 0x0f0f0f0f);
x += (x>>8);
x += (x>>16);
return (x & 0x00ff);

－－－－－－－－－－－－－－
不是很懂，可否解释一下？

#10

将 16 进制写成 2 进制就容易看清楚了。

最开始的输入可以看成是：
每 1 bit为一个单位，每个单位的数记录着该单位内 bit 的数目。

第一句就是将每个单位扩展到 2-bit，
如：
0-1 为 1 个单位，bit1.bit0 合起来代表的数记录着 0-1 的 bit 的数目。
2-3 为 1 个单位，bit3.bit2 合起来代表的数记录着 2-3 的 bit 的数目。
。。。

第二句就是将每个单位扩展到 4-bit，
余下类似。

因为 DWORD 最多只有 32-bit（要5-bit记录），
所以当单位大于 4-bit 时可以不做太多 and 的操作，
而等到返回结果时才清理一下。

#11

iceheart的方法太牛了！

#12

dengsf(drklnk@Radical_Dreamer) 的方法是需要很强的思考力才能想出来

#13

请问如何知道你的程序比别人的快那？是分析出来的还是有工具可以测量，谢谢！

#14

int ret=0;

while(num)
{
ret++;
num=num & (num-1)
}

#15

unsigned count(unsigned X)
{
  X=(X&0x55) + ((X>>1)&0x55);
  X=(X&0x33) + ((X>>2)&0x55);
  X=(X&0x0F) + ((X>>4)&0x0F);
  return X;
}
假设X是8位的ABCDEFGH;
X&0x55      得到 0B0D0F0H,
(X>>1)&0x55 得到 0A0C0E0G,
相加得到0|(B+A)|0|(D+C)|0|(E+F)|0|(H+G),其中用|来分隔开每一位,这样更好看清楚:)
然后
X&0x33      得到 0|0|0|(D+C)|0|0|0|(H+G),
(X>>2)&0x33 得到 0|0|0|(B+A)|0|0|0|(F+E),
对应位相加得到   0|0|0|(D+C+B+A)|0|0|0|(H+G+F+E)
接着
X&0x0F      得到0|0|0|0|0|0|0|(H+G+F+E),
(X>>4)&0x0F 得到0|0|0|0|0|0|0|(D+C+B+A),
相加得到
H+G+F+E+D+C+B+A（各位相加得到的不就是1的个数吗？）

该方法出自<Hackers Delight>这本书，有兴趣的可以读读

#16

dengsf(drklnk@Radical_Dreamer) 不错..
翻译了个 pascal的..

x:= (x and $55555555) + ( (x shr 1) and $55555555);
x:=(x and $33333333) + (x shr 2) and $33333333;
x:=(x and $0f0f0f0f) + (x shr 4) and $0f0f0f0f;
x := x+(x shr 8);
x := x+(x shr 16);

#17

以前见过的，白纸人生的做法应该是最简单的

#18

int fun(int i)
{
int num =0;
while (i>0)
{
i&=(i-1);
++num;
}
return num;
}

#1