c# - hakmem 算法

Question

我看到了这个 hakmem 算法：

int pop(unsigned x) {
  unsigned n;

  n = (x >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x * 0x01010101;
  return x >> 24;
}

是否可以将其更改为长 64 位？

Answer 1

您正在计算所谓的“汉明权重”，对于整数来说，这意味着数字中二进制“1”位的数量。对于二进制数，这也称为“人口计数”。

有几种方法可以实现 64 位。

有关详细信息，请参阅 Wiki 页面。

这是从这里窃取的一个实现：

public int Pop(ulong w) 
{
    w -= (w >> 1) & 0x5555555555555555UL;
    w = (w & 0x3333333333333333UL) + ((w >> 2) & 0x3333333333333333UL);
    w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0fUL;
    return (int)((w * 0x0101010101010101UL) >> 56);
}