ビットを破壊する方法(モルト化されていませんか?)
-
01-10-2019 - |
質問
32ビットINTからビットを破壊する最も効率的な方法は何ですか?この特定のケースでは、私は奇妙なビットのみを心配していますが、両方のセットのソリューションを一般化するのは簡単だと確信しています。
たとえば、変換したいです 0b01000101
の中へ 0b1011
. 。最も速い方法は何ですか?
編集:
このアプリケーションでは、均等なビットがすべてゼロであることを保証できます。その事実を利用して、速度を改善したりスペースを縮小したりできますか?
解決
アプリケーションで他のすべてのビットが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ビットで動作します。
他のヒント
速度に関しては、2^32のエントリを備えたルックアップテーブル16ビットの幅を打ち負かすのは難しいです!しかし、それほど多くのメモリを余裕がない場合は、256エントリのテーブルの4つのルックアップに加えて、それらを一緒に縫うためのいくつかのシフトとアンドがより良い選択かもしれません。あるいは、スイートスポットはその間のどこかにあるかもしれません...それはあなたが利用できるリソースと、あなたが実行する必要があるルックアップの数にわたってルックアップテーブルの初期化のコストがどのように償却されるかによって異なります。
どのようにわかりません 素早い そうなるでしょうが、あなたは次のようなことをすることができます
int a = 0b01000101;
int b = 0;
int i = 0;
while (a > 0) {
b |= (a & 1) << i;
a >>= 2;
}
これにより、すべての奇数ビットがAから引き離され、それらをbに置きます。
所属していません StackOverflow