以与 GCC builtinpopcount(int) 一样快的速度对整数计数位 1

Question

我写了一个算法（取自"The C Programming Language"）可以非常快速地计算 1 位的数量：

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

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

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

Answer 1

__builtin__popcount(unsigned int) 之所以如此之快，是因为它是一个使用内置硬件指令的 gcc 扩展。如果您愿意用架构可移植性换取编译器可移植性，请研究同样快速的英特尔内部函数，具体而言：

_mm_popcnt_u32(unsigned __int32);
_mm_popcnt_u64(unsigned __int64);

然后您必须包含 <mmintrin.h> 头文件才能使用这些内部函数，但是它们将适用于非 gcc 编译器。您可能还必须提供目标体系结构以使函数内联（这是严格要求的），使用 -march=native.

之类的东西

Answer 2

正如其他人提到的，__buildin__popcount() 很快，因为它使用一条 x86 指令。

如果您想要比您现有的更快但不使用任何特定处理器或编译器的东西，您可以创建一个包含 256 个条目的查找 table：

int bitcount[] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

然后用它来得到每个字节的位数：

int countBit1Fast(int n) 
{
    int i, count = 0;
    unsigned char *ptr = (unsigned char *)&n;
    for (i=0;i<sizeof(int);i++) {
        count += bitcount[ptr[i]];
    }
    return count;
}

Answer 3

I write a algorithm (taken from "The C Programming Language") that counts the number of 1-bits very fast:

我不明白为什么会有人将您的方法描述为 "very fast"。它有点聪明，平均而言它应该比天真的替代品更快。它也不依赖于 int 的表示宽度，这是一个优点。我观察到它对否定参数有未定义的行为，但这是按位运算符和函数的共同主题。

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

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

执行了多少次循环迭代？

1 表示值的二进制表示中的每个 1 位，而不管每个位在值中的位置
每次迭代执行多少工作
- c的一个增量
- n 与零的一次比较（在跳出循环时再加上一个）
- n 减 1
- 一位 'and'
这忽略了读取和存储，通过将操作数保存在寄存器中，这很可能是免费的或特别便宜的。如果我们假设每一个的成本相同，那就是每次迭代四次操作。对于随机的 32 位整数，平均有 16 次迭代，总共 65 次操作平均 。（最好的情况只是一个操作，但最坏的情况是 129，这并不比一个简单的实现好多少）。

另一方面，

__builtin__popcount() 使用 单个指令 而不管支持它的平台上的输入如何，例如您的平台。然而，即使对于那些没有专用指令的那些，它也可以更快地完成（平均而言）。

@dbush 提出了一种这样的机制，它与您提出的机制具有相似的优势。特别是，它不依赖于预先选择的整数宽度，尽管它确实依赖于其中在表示中 1 位所在的位置，但它确实运行对于某些人来说更快参数（较小的）比其他的。如果我没记错的话，在随机的 32 位输入上平均 大约 20 次操作 ：四次循环迭代中每次有五次（只有 0.4% 的随机输入需要少于四次）迭代）。我在那里计算每次迭代一次 table 读取，我认为可以从缓存中提供，但它可能仍然不如对寄存器中已保存的值进行算术运算那么快。

严格计算的一个是：

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 次按位 'and' 运算，以及 5 次常量加载，总共 25 次运算 输入（对于 64 位输入，它只增加到 30，尽管它们现在是 64 位操作而不是 32 位操作）。但是，此版本本质上取决于输入数据类型的特定大小。

以与 GCC builtinpopcount(int) 一样快的速度对整数计数位 1

Count bits 1 on an integer as fast as GCC builtinpopcount(int)

c

bit-manipulation

built-in

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

Count bits 1 on an integer as fast as GCC __builtin__popcount(int)

c

bit-manipulation

built-in

以与 GCC builtinpopcount(int) 一样快的速度对整数计数位 1

Count bits 1 on an integer as fast as GCC builtinpopcount(int)