无符号64位整数最大值为15的C人口统计

Question

我在一款Windows C应用程序中频繁使用汉明重量（population count）函数，并需要尽可能地优化它以提高性能。我使用该函数的超过一半情况下，只需要知道最大值为15。该软件将在各种处理器上运行，包括新老处理器。当Intel的SSE4.2或AMD的SSE4a存在时，我已经利用了POPCNT指令，但希望尽可能地优化软件实现（作为后备，如果没有SSE4）。

目前，我在64位（平台）模式下拥有以下函数的软件实现：

int population_count64(unsigned __int64 w) {
    w -= (w >> 1) & 0x5555555555555555ULL;
    w = (w & 0x3333333333333333ULL) + ((w >> 2) & 0x3333333333333333ULL);
    w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
    return int((w * 0x0101010101010101ULL) >> 56);
}

总结一下：

(1) 我想知道是否有可能在我只需要最大值为15的情况下对其进行优化。

(2) 是否有比上述函数更快的软件实现（适用于Intel和AMD CPU的无符号64位整数）？

- BitTwiddler1011

---

我认为 return int(w * 0x0101010101010101ULL) >> 56 会过早地将乘法的结果截断为 int，而 int 可能只有32位宽。 - j_random_hacker

其他可能的非常小的优化包括：(a) 如果您总是一次处理多个64位值，则在某些迭代中跳过最后一步或两步; (b) 查看是否可以稍微重新排列以更频繁地使用相同的常量--这些常量可能能够进入寄存器，这可能比在某些CPU上始终使用立即值更快（减少指令解码时间）（进行基准测试并查看）。 - j_random_hacker

真的吗？能解释一下 truncate 部分吗？记住这是在64位模式下。 - BitTwiddler1011

你将乘法的64位结果转换为32位的“int”。无论输入是什么，这个函数都应该返回零。我认为你在最后一行放错了右括号。 - slacker

@slacker：实际上，由于移位大于类型的宽度，它引发了UB。 - R.. GitHub STOP HELPING ICE

Answer 1

确实可以针对“最大15”的情况优化您的函数。以下是一些简化操作的示例：

inline int population_count64_max15(unsigned __int64 w)
{
  w -= (w >> 1) & 0x5555555555555555ULL;
  w  = (w & 0x3333333333333333ULL) + ((w >> 2) & 0x3333333333333333ULL);

  return int((w * 0x1111111111111111ULL) >> 60);
}

使用内联关键字（如上所示）内联函数应该也能提高性能。

- Jaap Weidemann

Answer 2

如果您使用的是32位机器，请将w分成两个32位字，分别计算每个半部分的popcount，然后相加。这将消除一些不必要的操作，这些操作需要从32位操作中合成64位操作（移位、乘法等）。如果您交错计算，则还可以增加并行性。

如果您正在编译64位代码，可以尝试以下方法：

int popcnt64(uint64_t w)
{
   uint64_t w1 = (w & 0x2222222222222222) + ((w+w) & 0x2222222222222222);
   uint64_t w2 = (w >> 1 & 0x2222222222222222) + (w >> 2 & 0x2222222222222222);
   w1 = w1 + (w1 >> 4) & 0x0f0f0f0f0f0f0f0f;
   w2 = w2 + (w2 >> 4) & 0x0f0f0f0f0f0f0f0f;
   return (w1 + w2) * 0x0101010101010101 >> 57;
}

这个方法包含更多的操作，但是给CPU提供了更多的并行执行机会。在较新的CPU上，它应该会稍微快一些，在其他CPU上则会稍微慢一些。

- slacker

---

这个会在64位处理器上比已接受的答案更快还是更慢？那么在32位处理器上呢？ - jjxtra