加权 popcount 集合/集合位的总和索引

Question

你知道任何聪明的方法来总结所有设置位的索引吗？

我知道密码

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

来自http://bitmath.blogspot.com/2023/01/weighted-popcnt.html?m=1

但是有一种方法可以不用多次使用popcount吗？我尝试在 Intel x86-64 CPU 的汇编中这样做。

Answer 1

一种朴素但可移植的方法是使用查找表。我会让你预先计算表格的值....

uint32_t A073642_nopopcnt(uint64_t n) {
  const uint16_t nibbles[16][16] = {{0, 0, 1, 1, 2, 2, 3, 3, ...},...};
  uint32_t i, sumsetbitpos = 0;
  for (i=0;i<16;i++) {
    sumsetbitpos += nibbles[i][(n >> (i << 2)) & 0xf];
  }
  return sumsetbitpos;
}