は、私が効率的に次のタスクを実行しようとしている:マスクと集約ビット
INPUT VALUE: 01101011
MASK: 00110010
MASK RESULT: --10--1-
AGGREGATED: 00000101
私は、この例では、私が達成しようとしているものを明確に説明したいと考えています。非純粋な方法でこれを行う最善の方法は何ですか?
は、私が効率的に次のタスクを実行しようとしている:マスクと集約ビット
INPUT VALUE: 01101011
MASK: 00110010
MASK RESULT: --10--1-
AGGREGATED: 00000101
私は、この例では、私が達成しようとしているものを明確に説明したいと考えています。非純粋な方法でこれを行う最善の方法は何ですか?
この操作はcompress_right
またはちょうどcompress
と呼ばれ、ハードウェアをサポートしないで実装するのは適度ではありません。この機能を実現するハッカーの喜び「7-4圧縮、または一般化抽出物」からの非ナイーブコードは、この動作のための命令pext
を有するであろう
unsigned compress(unsigned x, unsigned m) {
unsigned mk, mp, mv, t;
int i;
x = x & m; // Clear irrelevant bits.
mk = ~m << 1; // We will count 0's to right.
for (i = 0; i < 5; i++) {
mp = mk^(mk << 1); // Parallel suffix.
mp = mp^(mp << 2);
mp = mp^(mp << 4);
mp = mp^(mp << 8);
mp = mp^(mp << 16);
mv = mp & m; // Bits to move.
m = m^mv | (mv >> (1 << i)); // Compress m.
t = x & mv;
x = x^t | (t >> (1 << i)); // Compress x.
mk = mk & ~mp;
}
return x;
}
BMI2(後ハズウエルで実装さ)です。
マスクは一定である(一定のかが、複数回再利用)した場合、比較的明らか最適化はmv
ループ中に取り5つの値を事前に計算しています。この(実際には上記と同じアルゴリズム)
mk = ~m << 1;
for (i = 0; i < 5; i++) {
mp = mk^(mk << 1);
mp = mp^(mp << 2);
mp = mp^(mp << 4);
mp = mp^(mp << 8);
mp = mp^(mp << 16);
mv = mp & m;
mask[i] = mv;
m = m^mv | (mv >> (1 << i));
mk = mk & ~mp;
}
はまだ複雑に見えますが、ここではすべてが一定であるので、それを事前にすることができますようにそれは、independantlyに計算できるようにmv
の計算は、x
に依存しません計算します(コンパイラが実行できない場合は、を実行し、結果をコードに貼り付けるだけです)。コードの「実部」、実行時に実際に実行する必要があり、コードはこれです:
x = x & m;
t = x & mask[0];
x = x^t | (t >> 1);
t = x & mask[1];
x = x^t | (t >> 2);
t = x & mask[2];
x = x^t | (t >> 4);
t = x & mask[3];
x = x^t | (t >> 8);
t = x & mask[4];
x = x^t | (t >> 16);
(これはハッカーの喜びでもあり、少し異なるフォーマット済み)
多くの例が簡単になることができます例えば、
0
となります。x
です。x & 1
です。(x >> k) & m
です。m = 0x80000000
の場合、結果はx >> 31
です。m
は、2つの他の電力である場合m
は「完全な逆シャフルアルゴリズム」を使用することができ、交互にされた場合、結果は、(x >> numberOfTrailingZeros(m)) & 1
m
がいくつかの「グループ」で構成されている場合、「ビットグループ移動」アルゴリズムを使用できます(グループをマスクする、最初にシフトする(最初にシフトする)、またはシフトしたグループをまとめて洗練されたアプローチが存在する)、これは実際にはおそらく最も重要なケースです。、あなたの質問からマスクは、このようなコードで、ケースを「移動ビットグループ」に下落するだろう:
return ((x >> 1) & 1) | ((x >> 3) & 6);
非常に良い、ありがとうございました! –
@FilippoBistaffaマスクが定数(またはループ定数)の場合は、実質的に最適化できます。 – harold
はい、私のシナリオでは定数ですが、この種の最適化はコンパイラによって自動的に行われると思います。それとも明示的に行う方が良いですか? –