3

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

編集：私はこれ に沿って何かを考えていました

キックのために、私は AFTK だったので、次の形式のソリューションを力ずくで検索しようとしています。

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

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

4

4 に答える 4

5

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

ビットハックはこちら

于 2009-03-09T01:54:26.550 に答える
4

「素朴な」コードのコンパイラ出力を見てください。驚くかもしれません。私はかつてそのようなことをしたことがあり、コンパイラ (VC++2005) はすべての AND とシフトの値を完全に変更して、より効率的にしました。たとえば、「(0x001 & In) >> 3」。

しかし、はい、再シャッフルが固定機能である場合は、おそらくテーブルが最適です.

アップデート

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

まず、「In」の定数値を試してみましたが、コンパイラは少しもだまされず、次のコードを生成しました。

mov eax,469h

すなわち。それは完全に最適化されました。

だから...私は適切な入力を試み、これを得ました：

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 つの入力としては悪くありません。おそらく、ほとんどの人が手作業で行うよりも優れています。

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

于 2009-03-08T23:30:47.193 に答える
2

一般的な操作、つまり 32 ビット ワードのビットの順序を逆にするためのビット操作のハックがたくさんあります (シフト、AND および OR、AFAICR のそれぞれに 10 個)。

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

ルックアップテーブルを使用してください:)

于 2009-03-08T23:30:23.840 に答える
0

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

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 ;
于 2009-04-02T21:51:02.367 に答える