6

最初の値：

私は実際には2ビット値のコンパクトなシリーズであるバイナリ値を持っています。（つまり、バイナリ値の各2ビットは0、1、2、または3を表します。）したがって、たとえば、0、3、1、2は00110110になります。このバイナリ文字列では、私が気にするのは3（または、代わりに、ビットを反転して、答えが簡単になる場合は0のみを気にすることもできます）。他のすべての数値は関係ありません（理由については後で説明します）。

2番目の値：

同じように表された2ビット値の圧縮された一連の2番目のバイナリ値があります。最初の値と同じ長さです。

算数：

最初の値の3と同じ位置にある2番目の値の2ビットの数値の合計が必要です。言い換えれば、私が持っている場合：

First:  11000011
Second: 01111101

その場合、私の答えは「2」になります（最初の値に「11」が一致したのはこれらだけだったので、「2番目」の最初の数字と最後の数字を足し合わせました）。

これをできるだけ少ないクロックサイクルで実行したいと思います（GPUまたはx86アーキテクチャのいずれかで）。ただし、私は通常、アセンブラーソリューションではなく、アルゴリズムを探しています。各番号から一度に2ビットをマスクして、いくつかのループを実行するよりも速い方法はありますか？

4

1 に答える 1

11

もちろん。

 // the two numbers
 unsigned int a;
 unsigned int b;

ここで、同じ位置で終わる「11」があった場合にのみ、奇数の位置に「1」ビットを含むマスクを作成します。

 unsigned int mask = a & (a >> 1) & 0x55555555;

それを展開して、「11」パターンを元に戻します。

 mask = mask | (mask << 1);

したがって、aが1101100011の場合、マスクは1100000011になります。

次に、bをマスクでマスクします。

 b = b & mask;

次に、bからの（マスクされた）数値の加算を並行して実行できます。

 b = (b & 0x33333333) + ((b & 0xcccccccc) >> 2);
 b = (b & 0x0f0f0f0f) + ((b & 0xf0f0f0f0) >> 4);
 b = (b & 0x00ff00ff) + ((b & 0xff00ff00) >> 8);
 b = (b & 0x0000ffff) + ((b & 0xffff0000) >> 16);

32ビットの数値の場合、合計はbの最下位ビットになります。これは、ビットフィールドの並列加算で一般的に知られているパターンです。32ビットより大きい数値の場合、64ビットの数値の場合はさらに1ラウンド、128ビットの数値の場合は2ラウンドを追加します。

于 2012-05-12T09:34:17.783 に答える