•  05-07-2019
  •  | 
  •  

質問

7ビット値の任意の並べ替えを行う必要があり（はい、テーブルを使用する必要があることはわかっています）、これを行うためのビットハックがあるかどうか疑問に思っています。

例：

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

編集： this に沿って何かを考えていました

キックだけで、AFTKだったので、次の形式のソリューションのブルートフォース検索を試みています。

((In * C1) >> C2) & 0x7f

解決策が見つかりません。

役に立ちましたか？

解決

＆quot; naive＆quot;のコンパイラ出力をご覧ください。コード、それはあなたを驚かせるかもしれません。私はかつてそのようなことをしましたが、コンパイラ（VC ++ 2005）はすべてのANDとシフトの値を完全に変更して、それらをより効率的にしました。たとえば、＆quot;（0x001＆amp; In） ＆gt;＆gt; 3＆quot;。

ただし、はい、リシャッフルが固定関数の場合、おそらくテーブルが最適です。

更新

笑いのために、VC ++ 2005のコンパイラ出力を見てみました...

最初に＆quot; In＆quot;の定数値を試しました。コンパイラは少しもされていなかったため、次のコードを生成しました。

mov eax,469h

ie。完全に最適化されました。

だから...適切な入力を試みてこれを得た：

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx

これは、4つのシフト演算、5つのAND、4つのORです。6つの入力に対しては悪くありません。おそらくほとんどの人が手でできるよりも良いでしょう。

おそらく、アウトオブオーダー実行用に最適化されているため、見かけよりもクロックサイクルが短くなります。 ：-）

他のヒント

最初のステップは、数学的な解決策を理解し、それを最適化することです。

ビットハック

のこちらをご覧ください

一般的な操作、つまり32ビットワード内のビットの順序を逆にする（シフト、AND、OR、AFAICRの各10）ためのビットをいじるハックがたくさんあります。

この場合、入力から出力への明らかに完全に任意のマッピングでは、これをクリーンアップする方法がわかりません。

ルックアップテーブルを使用：）

最適化する前に、「素朴な」方法で意図したとおりに動作することを確認する必要があります。コードを関数にして、このループを実行すると：

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

この出力が生成され、コメントと矛盾します。実際、ビットが失われます。

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

説明したシャッフルを取得するには、次のようにコーディングします。

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top