5

v と w を 2 つのビット文字列とします。現在のアプリケーションでは、それらは 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]) ^ ...

主題に関するいくつかのアイデア: 私が気づいたことの 1 つは、この式は次のようにも書けるということです。させて

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])にx記述できます。

x = P(v & Pw)

さて、http://graphics.stanford.edu/~seander/bithacks.htmlで、文字列のパリティを計算する簡単な方法を見つけましたが、これに基づいて高速なアルゴリズムを構築するには、高速なアルゴリズムも必要です。Pw上記のビット文字列を計算する方法。

あるいは、私はこれを完全に間違った方法で行っているのかもしれません。この方法で行うには、非常に多くのパリティ計算があります。これが実際に進むべき道である場合、(プログラムが x86 で実行されると仮定して) アセンブリでパリティ フラグを使用して計算を高速化できるかどうか疑問に思っていました。

最後に、これは私が開発しているアプリケーションで大量に必要とされる計算になるため、速度が非常に重要です。レジスター内ですべての計算を実行できるかどうか、およびこれがメモリ内にルックアップ テーブルを作成するよりも高速になるかどうか疑問に思っていました。

4

3 に答える 3

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 や Intel アーキテクチャでは 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 に答える