像 GCC __builtin__popcount(int) 一样快地计算整数上的位 1

Question

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

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

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

编辑：我可以在 PIC 微控制器和非英特尔处理器上使用它，所以我需要最大的便携性。

Answer 1

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

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

让我们分析一下，假设一个非否定的论点：

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

• 执行多少次循环迭代？

  1 表示值的二进制表示中的每 1 位，无论每个位位于值中的哪个位置

• 每次迭代执行多少工作

  • 一个增量 c
  • 一个与n零的比较（在跳出循环时再加上一个）
  • 减n1减1
  • 一个按位“与”

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

__builtin__popcount()，另一方面，无论支持它的平台上的输入如何，都使用单个指令，例如您的平台。然而，即使在那些没有专用指令的情况下，它也可以做得更快（平均而言）。

@dbush 提出了一种这样的机制，它与您提出的机制具有相似的优势。特别是，它不依赖于预选择的整数宽度，尽管它取决于其中在表示中的1个位的驻留，它运行一些参数（较小的）比其他的更快。如果我算对了，那将平均对随机 32 位输入执行大约 20 次操作：四次循环迭代中的每一次执行五次（只有 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 次加法、5 次移位和 10 次按位“与”运算，以及 5 次加载常量，每个输入总共25 次运算（对于 64 位输入，它只会增加到 30现在是 64 位操作而不是 32 位操作）。但是，此版本本质上取决于输入数据类型的特定大小。