c++ - C 无符号 64 位整数的种群计数，最大值为 15

Question

我在 Windows C 应用程序中大量使用人口计数(汉明权重)函数，并且必须尽可能优化它以提高性能。在我使用该函数的情况下，超过一半的情况我只需要知道最大 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) 是否有比上述函数(对于无符号 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 关键字)也应该提高性能。