最上位ビット (MSB) が最下位ビット (LSB) を取得し、その逆になるように Delphi でバイト変数をビット反映する簡単な方法はありますか?
質問する
6298 次
4 に答える
26
コードでは、次のようにできます。
function ReverseBits(b: Byte): Byte;
var
i: Integer;
begin
Result := 0;
for i := 1 to 8 do
begin
Result := (Result shl 1) or (b and 1);
b := b shr 1;
end;
end;
しかし、ルックアップ テーブルははるかに効率的で、256 バイトのメモリしか消費しません。
function ReverseBits(b: Byte): Byte; inline;
const
Table: array [Byte] of Byte = (
0,128,64,192,32,160,96,224,16,144,80,208,48,176,112,240,
8,136,72,200,40,168,104,232,24,152,88,216,56,184,120,248,
4,132,68,196,36,164,100,228,20,148,84,212,52,180,116,244,
12,140,76,204,44,172,108,236,28,156,92,220,60,188,124,252,
2,130,66,194,34,162,98,226,18,146,82,210,50,178,114,242,
10,138,74,202,42,170,106,234,26,154,90,218,58,186,122,250,
6,134,70,198,38,166,102,230,22,150,86,214,54,182,118,246,
14,142,78,206,46,174,110,238,30,158,94,222,62,190,126,254,
1,129,65,193,33,161,97,225,17,145,81,209,49,177,113,241,
9,137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,
5,133,69,197,37,165,101,229,21,149,85,213,53,181,117,245,
13,141,77,205,45,173,109,237,29,157,93,221,61,189,125,253,
3,131,67,195,35,163,99,227,19,147,83,211,51,179,115,243,
11,139,75,203,43,171,107,235,27,155,91,219,59,187,123,251,
7,135,71,199,39,167,103,231,23,151,87,215,55,183,119,247,
15,143,79,207,47,175,111,239,31,159,95,223,63,191,127,255
);
begin
Result := Table[b];
end;
これは、個々のビットで動作するバージョンのコードよりも 10 倍以上高速です。
最後に、競合する回答がある場合、受け入れられた回答に対してあまり否定的にコメントするのは通常好きではありません。この場合、あなたが受け入れた回答には非常に深刻な問題があり、あなたと将来の読者のために明確に述べたい.
この回答に見られるのと同じ Pascal コードと、2 つのアセンブラー バージョンが含まれていた時点で、@Arioch の回答を受け入れました。これらのアセンブラ バージョンは、Pascal バージョンよりもはるかに遅いことがわかりました。これらは Pascal コードの 2 倍遅いです。
高レベルのコードをアセンブラーに変換するとコードが高速になるというのはよくある誤りです。やり方が悪いと、コンパイラーが発行するコードよりも実行速度が遅いコードを簡単に作成できます。アセンブラーでコードを作成する価値がある場合もありますが、適切なベンチマークを行わずにコードを作成してはなりません。
ここでアセンブラを使用することについて特にひどいのは、テーブルベースのソリューションが非常に高速であることは明らかであることです。それがどのように大幅に改善されるか想像するのは難しい.
于 2013-01-18T14:27:11.987 に答える
13
function ByteReverseLoop(b: byte): byte;
var i: integer;
begin
Result := 0; // actually not needed, just to make compiler happy
for i := 1 to 8 do
begin
Result := Result shl 1;
if Odd(b) then Result := Result or 1;
b := b shr 1;
end;
end;
速度が重要な場合は、ルックアップ テーブルを使用できます。プログラムの開始時に一度感じたら、テーブルから値を取得します。バイトをバイトにマップするだけでよいため、256x1 = 256 バイトのメモリが必要になります。また、最近の Delphi バージョンはインライン関数をサポートしているため、速度、読みやすさ、および信頼性の両方が提供されます (関数内に配列ルックアップをカプセル化すると、タイプミスのために値を変更しないことが確実になる場合があります)。
Var ByteReverseLUT: array[byte] of byte;
function ByteReverse(b: byte): byte; inline;
begin Result := ByteReverseLUT[b] end;
{Unit/program initialization}
var b: byte;
for b := Low(ByteReverseLUT) to High(ByteReverseLUT)
do ByteReverseLUT[b] := ByteReverseLoop(b);
このフォーラムで言及されたいくつかの実装の速度比較。
AMD Phenom2 x710 / Win7 x64 / Delphi XE2 32 ビット {$O+}
Pascal AND original: 12494
Pascal AND reversed: 33459
Pascal IF original: 46829
Pascal IF reversed: 45585
Asm SHIFT 1: 15802
Asm SHIFT 2: 15490
Asm SHIFT 3: 16212
Asm AND 1: 19408
Asm AND 2: 19601
Asm AND 3: 19802
Pascal AND unrolled: 10052 Asm Shift unrolled: 4573 LUT、呼ばれる: 3192 Pascal math、呼ばれる: 4614
注: LUT (ルックアップ テーブル) のタイミングは、おそらくかなり楽観的です。タイト ループで実行されているため、テーブル全体が L1 CPU キャッシュに吸い込まれました。実際の計算では、この関数が呼び出される頻度はおそらくはるかに低く、L1 キャッシュはテーブルを完全には保持しません。
Pascal インライン関数呼び出しの結果は偽物です - Delphi はそれらを呼び出さず、副作用がないことを検出しました。しかし、面白いことに、タイミングが異なっていました。
Asm Shift unrolled: 4040
LUT, called: 3011
LUT, inlined: 977
Pascal unrolled: 10052
Pas. unrolled, inlined: 849
Pascal math, called: 4614
Pascal math, inlined: 6517
そして、説明の下に：
Project1.dpr.427: d := BitFlipLUT(i)
0044AC45 8BC3 mov eax,ebx
0044AC47 E89CCAFFFF call BitFlipLUT
Project1.dpr.435: d := BitFlipLUTi(i)
Project1.dpr.444: d := MirrorByte(i);
0044ACF8 8BC3 mov eax,ebx
0044ACFA E881C8FFFF call MirrorByte
Project1.dpr.453: d := MirrorByteI(i);
0044AD55 8BC3 mov eax,ebx
Project1.dpr.460: d := MirrorByte7Op(i);
0044ADA3 8BC3 mov eax,ebx
0044ADA5 E8AEC7FFFF call MirrorByte7Op
Project1.dpr.462: d := MirrorByte7OpI(i);
0044ADF1 0FB6C3 movzx eax,bl
インライン関数へのすべての呼び出しが削除されました。パラメータを渡すことについて、Delphi は次の 3 つの異なる決定を下しました。
- 最初の呼び出しでは、関数呼び出しと一緒にパラメーターを渡す必要がなくなりました
- 2回目の呼び出しでは、関数が呼び出されなかったにもかかわらず、パラメーターの受け渡しを維持しました
- 3回目の呼び出しでは、変更されたパラメーターの受け渡しが維持されました。これは、関数呼び出し自体よりも長いことが証明されました! 変！:-)
于 2013-01-18T14:38:14.447 に答える
13
function BitFlip(B: Byte): Byte;
const
N: array[0..15] of Byte = (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15);
begin
Result := N[B div 16] or N[B mod 16] shl 4;
end;
于 2013-01-18T16:08:34.977 に答える
8
ブルートフォースの使用は簡単で効果的です。
このルーチンは、David の LUT ソリューションと同等ではありません。
アップデート
バイト配列を入力として追加し、結果もバイト配列に割り当てました。これは、LUT ソリューションのパフォーマンスが優れていることを示しています。
function MirrorByte(b : Byte) : Byte; inline;
begin
Result :=
((b and $01) shl 7) or
((b and $02) shl 5) or
((b and $04) shl 3) or
((b and $08) shl 1) or
((b and $10) shr 1) or
((b and $20) shr 3) or
((b and $40) shr 5) or
((b and $80) shr 7);
end;
更新 2
少しググって、見つけましBitReverseObviousた。
function MirrorByte7Op(b : Byte) : Byte; inline;
begin
Result :=
{$IFDEF WIN64} // This is slightly better in x64 than the code in x32
(((b * UInt64($80200802)) and UInt64($0884422110)) * UInt64($0101010101)) shr 32;
{$ENDIF}
{$IFDEF WIN32}
((b * $0802 and $22110) or (b * $8020 and $88440)) * $10101 shr 16;
{$ENDIF}
end;
これは LUT ソリューションに近く、1 回のテストでさらに高速です。
要約すると、MirrorByte7Op()は 3 つのテストで LUT より 5 ～ 30% 遅く、1 つのテストで 5% 高速です。
ベンチマークするコード:
uses
System.Diagnostics;
const
cBit : Byte = $AA;
cLoopMax = 1000000000;
var
sw : TStopWatch;
arrB : array of byte;
i : Integer;
begin
SetLength(arrB,cLoopMax);
for i := 0 TO Length(arrB) - 1 do
arrB[i]:= System.Random(256);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := b;
end;
sw.Stop;
WriteLn('Loop ',b:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := ReflectBits(arrB[i]);
end;
sw.Stop;
WriteLn('RB array in: ',b:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := MirrorByte(arrB[i]);
end;
sw.Stop;
WriteLn('MB array in: ',b:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
b := MirrorByte7Op(arrB[i]);
end;
sw.Stop;
WriteLn('MB7Op array in : ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
arrB[i] := ReflectBits(arrB[i]);
end;
sw.Stop;
WriteLn('RB array in/out: ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
arrB[i]:= MirrorByte(arrB[i]);
end;
sw.Stop;
WriteLn('MB array in/out: ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
sw := TStopWatch.StartNew;
for i := 0 to Pred(cLoopMax) do
begin
arrB[i]:= MirrorByte7Op(arrB[i]);
end;
sw.Stop;
WriteLn('MB7Op array in/out: ',arrB[0]:3,' ',sw.ElapsedMilliSeconds);
ReadLn;
end.
ベンチマークの結果 (XE3、i7 CPU 870):
32 bit 64 bit
--------------------------------------------------
Byte assignment (= empty loop) 599 ms 2117 ms
MirrorByte to byte, array in 6991 ms 8746 ms
MirrorByte7Op to byte, array in 1384 ms 2510 ms
ReverseBits to byte, array in 945 ms 2119 ms
--------------------------------------------------
ReverseBits array in/out 1944 ms 3721 ms
MirrorByte7Op array in/out 1790 ms 3856 ms
BitFlipNibble array in/out 1995 ms 6730 ms
MirrorByte array in/out 7157 ms 8894 ms
ByteReverse array in/out 38246 ms 42303 ms
表の最後の部分に他の提案をいくつか追加しました (すべてインライン化)。おそらく、配列 in と配列 as result を使用してループでテストするのが最も公平です。ReverseBits(LUT) とMirrorByte7Op同等の速度であり、BitFlipNibble(LUT) は x64 で 1 ビット性能が劣ります。
注: の x64 ビット部分に新しいアルゴリズムを追加しましたMirrorByte7Op。64 ビット レジスタをより有効に活用し、命令数を減らします。
于 2013-01-19T15:24:54.377 に答える