Popcount 汇编/设置位的总索引

Question

我想对设置位的所有索引求和。

\n

http://bitmath.blogspot.com/2023/01/weighted-popcnt.html?m=1 \n有一个有趣的实现：

\n

// sum of indexes of set bits\nint A073642(uint64_t n)\n{\n    return __popcnt64(n & 0xAAAAAAAAAAAAAAAA) +\n          (__popcnt64(n & 0xCCCCCCCCCCCCCCCC) << 1) +\n          (__popcnt64(n & 0xF0F0F0F0F0F0F0F0) << 2) +\n          (__popcnt64(n & 0xFF00FF00FF00FF00) << 3) +\n          (__popcnt64(n & 0xFFFF0000FFFF0000) << 4) +\n          (__popcnt64(n & 0xFFFFFFFF00000000) << 5);\n}\n

\n

（Godbolt：针对 MSVC、GCC 和 clang 的 x86-64-v3（AVX2，如 Haswell）编译器生成的 asm，有趣的是，它自动矢量化了四个 popcount。）

\n

但是，我正在寻找一种无需多次使用 popcount 即可实现的方法。

\n

我尝试在装配中执行此操作。popcount 操作相当快，但它可以用较少数量的指令完成，因为在每个 popcount 中我们重复相同的阶段（特别是如果硬件 popcount 不可用，比如在 RISC-V 上，或者 Nehalem 之前的 x86） 。

\n

这就像一个“位拼图\xe2\x80\x9d”，我可能应该使用一些智能掩码和汇编的基本指令（算术/逻辑运算、条件移动/设置/跳转），但我不\xe2\x80\ x99不知道怎么做。

\n

我可以\xe2\x80\x99t使用AVX-512。

\n

Answer 1

一种简单但可移植的方法是使用查找表。我尝试将性能与上面的功能进行比较。当使用 -mpopcnt 标志编译时，popcount 版本的速度明显更快，大约 30 个周期时速度提高了 2-3 倍。如果没有 popcount 编译器标志，这个函数的速度大约是原来的两倍。

static inline uint32_t A073642_nopopcnt(uint64_t n) {
  static const uint8_t nibbles[16][16] = {
{0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6},
{0, 4, 5, 9, 6, 10, 11, 15, 7, 11, 12, 16, 13, 17, 18, 22},
{0, 8, 9, 17, 10, 18, 19, 27, 11, 19, 20, 28, 21, 29, 30, 38},
{0, 12, 13, 25, 14, 26, 27, 39, 15, 27, 28, 40, 29, 41, 42, 54},
{0, 16, 17, 33, 18, 34, 35, 51, 19, 35, 36, 52, 37, 53, 54, 70},
{0, 20, 21, 41, 22, 42, 43, 63, 23, 43, 44, 64, 45, 65, 66, 86},
{0, 24, 25, 49, 26, 50, 51, 75, 27, 51, 52, 76, 53, 77, 78, 102},
{0, 28, 29, 57, 30, 58, 59, 87, 31, 59, 60, 88, 61, 89, 90, 118},
{0, 32, 33, 65, 34, 66, 67, 99, 35, 67, 68, 100, 69, 101, 102, 134},
{0, 36, 37, 73, 38, 74, 75, 111, 39, 75, 76, 112, 77, 113, 114, 150},
{0, 40, 41, 81, 42, 82, 83, 123, 43, 83, 84, 124, 85, 125, 126, 166},
{0, 44, 45, 89, 46, 90, 91, 135, 47, 91, 92, 136, 93, 137, 138, 182},
{0, 48, 49, 97, 50, 98, 99, 147, 51, 99, 100, 148, 101, 149, 150, 198},
{0, 52, 53, 105, 54, 106, 107, 159, 55, 107, 108, 160, 109, 161, 162, 214},
{0, 56, 57, 113, 58, 114, 115, 171, 59, 115, 116, 172, 117, 173, 174, 230},
{0, 60, 61, 121, 62, 122, 123, 183, 63, 123, 124, 184, 125, 185, 186, 246}};
  uint32_t i, sumsetbitpos = 0;
  for (i=0;i<16;i++) {
    sumsetbitpos += nibbles[i][(n >> (i << 2)) & 0xf];
  }
  return sumsetbitpos;
}