24

32ビット整数からビットをデインターリーブする最も効率的な方法は何ですか？この特定のケースでは、奇数ビットのみを気にしますが、両方のセットのソリューションを一般化するのは簡単だと確信しています。

たとえば、に変換0b01000101したい0b1011。最も速い方法は何ですか？

編集：

このアプリケーションでは、偶数ビットがすべてゼロであることを保証できます。その事実を利用して、速度を向上させたり、スペースを削減したりできますか？

4

3 に答える 3

35

アプリケーションで他のすべてのビットが 0 であることがわかっている場合、次のように実行できます。

x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff;

最初のステップは次のようになります。

  0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p   x
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0   x >> 1
  --------------------------------
= 0aabbccddeeffgghhiijjkkllmmnnoop   x | (x >> 1)
& 00110011001100110011001100110011   0x33333333
  --------------------------------
= 00ab00cd00ef00gh00ij00kl00mn00op   (x | (x >> 1)) & 0x33333333

次に、2 番目のステップで一度に 2 ビットを処理します。

于 2010-07-12T23:54:19.987 に答える
1

速度に関しては、2^32 エントリの 16 ビット幅のルックアップ テーブルに勝るものはありません。しかし、それほどメモリに余裕がない場合は、256 エントリのテーブルに 4 つのルックアップを追加し、それらをつなぎ合わせるためにいくつかのシフトと AND を使用することをお勧めします。あるいは、スイート スポットはその中間にあるかもしれません...それは、利用可能なリソースと、実行する必要があるルックアップの数に対してルックアップ テーブルの初期化コストがどのように償却されるかによって異なります。

于 2010-06-29T01:52:36.227 に答える
0

どれほど速いかはわかりませんが、次のようなことができます

int a = 0b01000101;
int b = 0;
int i = 0;
while (a > 0) {
    b |= (a & 1) << i;
    a >>= 2;
}

これは、すべての奇数ビットを a から引き出して、b に配置します。

于 2010-06-29T22:56:57.053 に答える