c++ - 必须有一种非常快速的方法来计算这个按位表达式吗？

Question

令 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]))

现在如果 Pw 是一个位串，其中每个位表示低位的奇偶校验，即 Pw[i] = P(w[i-1]) 那么x 可以这样写:

x = P(v & Pw)

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

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

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

Answer 1

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

  precomputed[v<<8+w]

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