2013-05-25 10 views
5

は、私が効率的に次のタスクを実行しようとしている:マスクと集約ビット

INPUT VALUE: 01101011 
MASK:  00110010 
MASK RESULT: --10--1- 
AGGREGATED: 00000101 

私は、この例では、私が達成しようとしているものを明確に説明したいと考えています。非純粋な方法でこれを行う最善の方法は何ですか?

答えて

7

この操作は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); 
+0

非常に良い、ありがとうございました! –

+0

@FilippoBistaffaマスクが定数(またはループ定数)の場合は、実質的に最適化できます。 – harold

+0

はい、私のシナリオでは定数ですが、この種の最適化はコンパイラによって自動的に行われると思います。それとも明示的に行う方が良いですか? –