只使用二进制运算实现汉明重量？

Question

我需要用二进制操作（&, ^, >>）写一个字节汉明重量的表达式，而不需要任何循环，只需要一个公式。虽然有很多算法可以计算汉明重量，但它们都使用算术操作或循环。如果我们采用维基百科中Hamming weight的算法，那么第一项和为D = B^C^(B&C << 1)，但后面两个和更复杂。请问有什么提示吗？

更新: 谢谢大家的帮助，实际上我需要的是以下内容：

int popcount_1(unsigned char in){

unsigned char m1  = 0x55;
unsigned char m2  = 0x33;
unsigned char m4  = 0x0f;
unsigned char B,C = 0;
unsigned char x = in;

x = (x & (x << 1) & (m1 << 1)) | (m1 & (x ^ (x >> 1)));

B = x & m2;
C = (x >>  2) & m2;
x = B ^ C ^ ((B & C) << 1);

B = (x & m4 ) ^ ((x >>  4) & m4);
C = (x & ((x >>  4) & m4)) << 1;
x = B ^ C ^ ((B & C) << 1);
return x;
}

这段代码将会得到变量in的汉明重量。它不包含任何+、-或比较指令，可以在8位微控制器上工作。然而，它需要更多的操作比大多数其他解决方案。现在，我正在尝试简化它。

更新2：@Evgeny Kluev提出了另一种基于64位寄存器的解决方案。

- Roman

---

不，这不是。我正在进行这项工作是为了推导出一种基于汉明重量/距离的差分功耗分析攻击中优化关键搜索的解析表达式。实际上，我已经几乎找到了这个表达式，所以我很快就会发帖。 - Roman

我不确定我理解了，如果只是为了优化，这两个约束条件都不应该存在，你需要“任何最快的方式”（这在很大程度上取决于平台）。 - harold

在x86上，假设字节在连续的内存中，最快的字节大小的popcount技巧是使用pshufb：http://wm.ite.pl/articles/sse-popcount.html - harold

@harold 谢谢你提供的链接，非常有用。 - Roman

@Roman，你最终是如何实现的？我需要为我的64位向量做类似的事情。你能给我一些见解吗？ - Abhishek

Answer 1

我认为最好的方法是O(log n)。这里是一个计算32位整数pop-count的Go代码。如果需要扩展到64位，应该很明显，希望注释能够清楚地说明实际发生了什么：

func popCount(n uint32) int {
  // each bit in n is a one-bit integer that indicates how many bits are set
  // in that bit.

  n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555)
  // Now every two bits are a two bit integer that indicate how many bits were
  // set in those two bits in the original number

  n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333)
  // Now we're at 4 bits

  n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F)
  // 8 bits

  n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF)
  // 16 bits

  n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF)
  // kaboom - 32 bits

  return int(n)
}

- Running Wild

Answer 2

我不确定这是否是您要查找的内容，但这只是一种仅使用移位和按位与运算符的公式：

int weight(unsigned char x)
{
  return ((0x876543210 >>
    (((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >>
    ((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2))
    & 0xf;
}

这里的移位操作被两次用作数组索引的替代方式(用于查找4位哈明重量)。还有一次移位操作使用数组索引执行加法。

- Evgeny Kluev

---

@Evgeny kluev，您能否再解释一下？这样的表达式是否可用于计算64位向量的汉明重量？ - Abhishek

@abhiitd.cs：这种表达式只有在计算8位单词的汉明重量时才有用（在OP中指定了相当严格的限制）。如果您需要64位向量的汉明重量（在相同的限制下），可以使用相同的思路，但得到的表达式会更加复杂。如果您不需要这些限制，将该问题的解决方案扩展到64位是更为合理的：如何计算32位整数中设置位的数量？ - Evgeny Kluev

@EvgenyKluev 非常感谢您的回复。我已经查看了该链接，此外，我还发现了这篇文章Hamming Weight，它解释了如何以更好的并行方式进行注射。实际上，我需要以最有效的方式计算256位的汉明重量，因为它在硬件设计的关键路径中。所以我正在寻找最有效的解决方案，而您的解决方案对我来说令人震惊。 :) - Abhishek

@abhiitd.cs 我认为在硬件中更容易实现，可以避免移位和掩码，并使用简单的加法器，其中有一半不需要进位比特。 - Sophistifunk