c - 计算数字中的位数

Question

复制：

计算 32 位整数中设置位数的最佳算法？

---

假设你有一个号码。有没有办法计算该数字的二进制表示中等于 1 的位，而不是使用迭代？我的意思是，有没有办法使用一些按位运算符和掩码在恒定时间内做到这一点。我需要适用于 32 位和 64 位架构的解决方案。啊差点忘了，我需要的是C语言或者汇编也不错。

Answer 1

在http://graphics.stanford.edu/~seander/bithacks.html有一个没有循环的位计数算法。http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/上有很多位计数算法

Answer 2

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

当然，您可以构建一个包含所有正确值的查找表：

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

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

你可以稍微优化一下，但它只需要一点迭代。只需创建一个 8 位版本的表解决方案，一个只有 256 个条目的表，然后遍历要检查的值中的每个 BYTE，对表查找的结果求和。就像是：

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

是的，您可以使用查找表来做到这一点。