5

让 v 和 w 是两个位串。在当前应用程序中，它们由 8 位组成。我正在寻找计算以下表达式的最快方法。

x = (v[1] & w[0]) ^ (v[2] & w[1]) ^ (v[2] & w[0]) ^ (v[3] & w[2]) ^ (v[3]) & w[1]) ^ (v[3] & w[0]) ^ ...

关于这个主题的一些想法：我注意到的一件事是这个表达式也可以写成如下。让

P(w[k]) = w[k] ^ w[k-1] ^ ... ^ w[0]

表示 w 的最低k + 1位的奇偶性。然后

x = (v[1] & P(w[0])) ^ (v[2] & P(w[1])) ^ (v[3] & P(w[2])) ^ ... ^ (v[7] & P(w[6]))

现在 ifPw是一个位串，其中每个位表示低位的奇偶校验，即Pw[i] = P(w[i-1])thenx可以写如下：

x = P(v & Pw)

现在，在http://graphics.stanford.edu/~seander/bithacks.html我找到了一种快速计算字符串奇偶性的方法，但是为了基于此构建快速算法，我还需要快速计算上述位串的方法Pw。

或者也许我完全以错误的方式处理这个问题，有很多奇偶校验计算要以这种方式完成。如果这确实是要走的路，我想知道是否有可能（假设程序将在 x86 上运行）在汇编中使用奇偶校验标志来加速计算。

最后，这将是我正在开发的应用程序中大量需要的计算，因此速度真的很重要。我想知道是否可以在寄存器中完成整个计算，以及这是否比在内存中创建查找表更快。

4

3 回答 3

5

如果 v 和 w 真的是 8 位，那么您可以预先计算所有 256^2 组合并将结果存储在 65K 字节的表中。这将很容易放入缓存中。然后你的计算变成：

  precomputed[v<<8+w]

这是一些机器时钟和热缓存行查找。可能很难被击败。

于 2013-11-13T16:24:32.883 回答
3

在 x86 上，为低 8 位算术运算自动计算奇偶校验位。基本上所需的操作减少到：

 Pw = Lookup_256[w];
 v &= Pw;                 // get the Parity as side effect on x86, or

 v  = Lookup_256[v] >> 7; // Reuse the table to get parity for bit 7

编辑

^通过认识到部分乘积 (v[i] & w[j]) 是乘法的内部部分并且与运算符的连接使整个运算无进位（或多项式），可以实现更高级别的优化和并行实现。

整体运算将是 Parity(((v >> 1) Px w) & 0xff)，其中 Px 表示多项式乘法，例如 NEON 和带有 PCLMULQDQ 指令的 intel 架构支持。英特尔指令（不幸的是）以 64 位字运行，这使得合并几个独立的向量 v,w 以同时相乘成为可能，但很难。

于 2013-11-13T16:55:03.473 回答
0

大概是这样的吧？

register int v, w, parity=0;
/* ... */
v >>= 1; /* Discard lsb? */
while (v) {
  parity ^= v ^ w;
  w = (w & 1) ^ (w >> 1);
  v >>= 1;
}
parity &= 1;
于 2013-11-13T14:09:37.357 回答