C无符号64位整数的总体计数，最大值为15

Question

我在windows c应用程序中大量使用人口计数(汉明权重)函数，并且必须尽可能地对其进行优化以提高性能。在我使用该函数的一半以上的情况下，我只需要知道该值最多为15。该软件可以在各种处理器上运行，无论是旧的还是新的。当英特尔的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)是否有比上述函数(对于无符号64位整数)更快的软件实现(对于Intel和AMD CPU)？

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);
}

内联函数(如上所述使用inline关键字)也可以提高性能。

Answer 2

如果您使用的是32位计算机，请将w拆分为两个32位字，分别计算每一半的you计数，然后将其相加。这将消除一些不必要的操作，这些操作是从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上，它会稍微慢一些。