计算整数上的位 1 的速度与 GCC __builtin__popcount(int) 一样快

我编写了一个算法（摘自“C 编程语言”），可以非常快地计算 1 位的数量：

int countBit1Fast(int n)
{
    int c = 0;
    for (; n; ++c)
        n &= n - 1;
    return c;
}

但一位朋友告诉我__builtin__popcount(int)速度快很多，但便携性较差。我尝试了一下，速度快了很多倍！为什么这么快？我想尽可能快地计算位数，但不拘泥于特定的编译器。

EDIT:我可能会在 PIC 微控制器上使用它，也可能在非英特尔处理器上使用它，所以我需要最大的可移植性。

我编写了一个算法（摘自“C 编程语言”），可以非常快地计算 1 位的数量：

我不明白为什么有人会把你的方法描述为“非常快”。它有点聪明，而且平均来说应该比简单的替代方案更快。它也不依赖于表示的宽度int，这是一个优点。我观察到它对负参数有未定义的行为，但这是按位运算符和函数的常见主题。

让我们分析一下，假设有一个非负参数：

int c = 0;
for (; n; ++c)
    n &= n - 1;

• 执行了多少次循环迭代？

  1 表示值的二进制表示形式中的每 1 位，无论where在每一位所在的值中

• 每次迭代执行多少工作

  • 一个增量c
  • 的一项比较n反对零（当打破循环时再加上一个）
  • 减一n by 1
  • 一个按位“和”

  这忽略了读取和存储，通过将操作数保存在寄存器中，这很可能可以免费或特别便宜。如果我们假设每个操作的成本相同，则每次迭代有四次操作。对于随机 32 位整数，平均迭代 16 次，总共平均 65 次操作。 （最好的情况只是一次操作，但最坏的情况是 129，这并不比简单的实现更好）。

__builtin_popcount()，另一方面，使用一条指令无论支持它的平台上的输入如何，例如您的平台很可能都是如此。然而，即使对于那些没有专用指令的人来说，也可以更快地完成（平均而言）。

@dbush 提出了一种这样的机制，它与您提出的机制具有类似的优点。特别是，它不依赖于预先选择的整数宽度，尽管它确实依赖于where在 1 位驻留在表示中，对于某些参数（较小的参数），它确实比其他参数运行得更快。如果我数对了，那一个就平均了约20次操作在随机 32 位输入上：四次循环迭代中每一次迭代五次（只有 0.4% 的随机输入需要少于四次迭代）。我正在计算每次迭代读取的一个表，我假设可以从缓存中提供该表，但这可能仍然不如对寄存器中已保存的值进行算术运算快。

严格计算的一种是：

int countBit1Fast(uint32_t n) {
    n = (n & 0x55555555u) + ((n >> 1) & 0x55555555u);
    n = (n & 0x33333333u) + ((n >> 2) & 0x33333333u);
    n = (n & 0x0f0f0f0fu) + ((n >> 4) & 0x0f0f0f0fu);
    n = (n & 0x00ff00ffu) + ((n >> 8) & 0x00ff00ffu);
    n = (n & 0x0000ffffu) + ((n >>16) & 0x0000ffffu);
    return n;
}

这很容易计算：五次加法、五次移位、十次按位“与”运算，以及 5 次常量加载，总共25 次操作对于每个输入（对于 64 位输入，它只增加到 30，尽管这些现在是 64 位操作而不是 32 位操作）。然而，该版本本质上取决于输入数据类型的特定大小。