3

このアルゴリズムが 32 ビット システムで MSB を LSB に、または LSB を MSB に変換する方法を説明してもらえますか?

unsigned char b = x;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

コード内で 16 進数の値が LU または U だけで終わるのを見たことがありますが、これはどういう意味ですか?

ありがとう！

4

4 に答える 4

3

b を 8 ビット値として表示しますabcdefgh。これらの文字はそれぞれ 1 ビット (0 または 1) でありa、最上位ビットと最下位ビットがありhます。次に、各操作がそれらのビットに対して何をするかを見てください。

b * 0x0802LU             = 00000abcdefgh00abcdefgh0 
b * 0x0802LU & 0x22110LU = 000000b000f0000a000e0000
b * 0x8020LU             = 0abcdefgh00abcdefgh00000
b * 0x8020LU & 0x88440LU = 0000d000h0000c000g000000
((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU))
                         = 0000d0b0h0f00c0a0g0e0000

したがって、この時点で、ビットがシャッフルされて分散されます。

(....) * 0x10101LU       =                 d0b0h0f00c0a0g0e0000
                         +         d0b0h0f00c0a0g0e000000000000
                         + d0b0h0f00c0a0g0e00000000000000000000
                         = d0b0f0f0dcbahgfedcbahgfe0c0a0g0e0000
(...) * 0x10101LU >> 16  = d0b0f0f0dcbahgfedcba
b                        = hgfedcba

乗算は、シフト/加算/加算 (定数に設定された 3 ビット) と同等であり、ビットを最終的な位置に並べます。次に、最終的なシフトと 8 ビットへの削減により、最終的なビット反転結果が得られます。

于 2013-08-22T00:38:00.647 に答える
3

おそらく、acharは 8 ビットなのでunsigned char b = x、x の下位 8 ビットを取ります。

0x22110 のマスクは、ビット 4、8、13、および 17 (最下位ビットは 0 から数えます) を抽出します。したがって、0x0802 による乗算では、それらのビットに何を配置するかのみを気にします。0x802 では、ビット 1 と 11 がオンになっているため、この乗算では 8 ビットのコピーがbビット 1 から 8 に配置され、別のコピーがビット 11 から 18 に配置されます。オーバーラップがないため、オーバーラップするビットを追加しても影響はありません。より一般的な乗算で。

この製品から、次のビットを取得します。

  • のビット 3 であるビット 4 b。(コピーのビット 4 はビット 1 から始まるため、ビット 4–1 = の 3 b)
  • のビット 7 であるビット 8 b。(8–1 = 7.)
  • のビット 2 であるビット 13 b。(13–11 = 2.)
  • のビット 6 であるビット 17 b。(17–11 = 6.)

同様に、0x88440 によるマスクは、ビット 6、10、15、および 19 を抽出します。0x8020 による乗算はb、ビット 5 から 12 に のコピーを配置し、ビット 15 から 22 に別のコピーを配置します。この積から、これらのビットを取得します。

  • のビット 1 であるビット 6 b。
  • のビット 5 であるビット 10 b。
  • のビット 0 であるビット 15 b。
  • のビット 4 であるビット 19 b。

次に、それらを OR して、以下を生成します。

  • のビット 3 であるビット 4 b。
  • のビット 1 であるビット 6 b。
  • のビット 7 であるビット 8 b。
  • のビット 5 であるビット 10 b。
  • のビット 2 であるビット 13 b。
  • のビット 0 であるビット 15 b。
  • のビット 6 であるビット 17 b。
  • のビット 4 であるビット 19 b。

この結果を と呼びtます。

これに 0x10101 を掛け、右に 16 シフトし、 に代入しbます。代入は に変換されるunsigned charため、下位 8 ビットのみが保持されます。シフト後の下位 8 ビットは、シフト前のビット 24 ～ 31 です。したがって、積のビット 24 から 31 だけを気にします。

乗数 0x10101 には、ビット 0、8、および 16 が設定されています。したがって、結果のビット 24 は、 のビット 24、16、および 8 の合計に、t他の場所からのキャリーを加えたものです。ただし、キャリーはありませんt。乗数のビットのように、設定されたビットが 8 離れていないことに注意してください。したがって、製品内の同じビットに直接寄与するものはありません。積の各ビットは、 の最大 1 ビットの結果ですt。それがどのビットかを把握するだけです。

ビット 24 は、 のビット 8、16、または 24 から取得する必要がありますt。ビット 8 のみ設定可能で、 からビット 7 ですb。この方法ですべてのビットを推測します。

  • ビット 24 は ではビット 8、tではビット 7 ですb。
  • ビット 25 は ではビット 17 でtあり、 ではビット 6 ですb。
  • ビット 26 は ではビット 10 でtあり、 ではビット 5 ですb。
  • ビット 27 は ではビット 19 でtあり、 ではビット 4 ですb。
  • ビット 28 は ではビット 4、tではビット 3 ですb。
  • ビット 29 は のビット 13 でtあり、これは のビット 2 ですb。
  • ビット 30 は ではビット 6、tではビット 1 ですb。
  • ビット 31 は ではビット 15 でtあり、 ではビット 0 ですb。

したがって、積のビット 24 ～ 31 は のビット 7 ～ 0 でbあるため、最終的に生成される 8 ビットは のビット 7 ～ 0 ですb。

于 2013-08-22T00:28:27.160 に答える
0

2番目の質問に答えるにuは、16進定数を符号なしとして扱うことを意味し（より長い幅に拡張する必要がある場合）、それを.lとして扱うことを意味しlongます。

私はあなたの最初の質問に取り組んでいます。

于 2013-08-21T22:54:07.910 に答える
0

乗算と 16 進数として見ると、このアルゴリズムが何をしているのかを視覚化するのは困難です。これを 2 進数に変換し、乗算を同等のシフト演算の合計に置き換えると、より明確になります。基本的に、それが行っていることは、バイトの一部をシフトしてマスクすることによって展開し、その後、その部分をその場で再構築する並列半加算器を実装することです。これはたまたま最初の場所と逆になります。

例えば、

b * 0x0802 = b << 11 | b << 1

b にいくつかの値を (バイナリで) 挿入し、それに従ってください。

于 2013-08-22T00:13:08.817 に答える