在数计数位[复制]

Question

重复：

  

最佳算法来计算一个32位整数组的位的数目？

---

假设你有一个数字。有没有什么办法来计算相等于1这个数字的二进制表示的位，不使用迭代？我的意思是，有没有办法使用一些位运算符和口罩，以做到在一定的时间。我需要的解决方案，这将两种架构的32位和64位工作。啊差点忘了，我需要它的C语言或汇编也不错。

Answer 1

有在 HTTP无环比特计数算法：//graphics.stanford。埃杜/〜seander / bithacks.html 。位计数算法在很多 HTTP：//gurmeetsingh.wordpress的.com / 2008/08/05 /快速位计数例程/

Answer 2

嗯，当然有，但你不会喜欢它。

您当然可以，建立一个查找表中的所有正确的值：

表[1] = 1，表[2] = 1，表[3] = 2，等等。

所以，这会给你一个真快的答案，但它本身是一个完全无用的解决方案，因为该表必须是非常，非常大的。

您可以优化这一点，但它需要一点点的迭代。简单地创建表溶液，区区256条目表中的一个8位版本，然后每个字节迭代中的值进行检查，该表查找的结果求和。是这样的：

short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
   result += tableLookup[ (valueToCheck & 0xFF) ];
   valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.

嗯，看来这是众所周知的（在这里我这样做了我的头顶部）： http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Answer 3

是的，你可以做到这一点通过使用查找表