有没有一种简单的方法在Delphi中反转比特字节变量，使得最高有效位（MSB）变成最低有效位（LSB），反之亦然？
在Delphi中如何对一个字节进行位反转？
13
- blerontin
7
3查找表有16个元素，每个元素的4位需要翻转并将它们反向组合。 - Warren P
@Warren 或 256 字节表，然后单个 XLAT 汇编指令 :-) - Arioch 'The
3XLAT 很慢...在我记忆中，它的 x64 操作码已经不再可用。在旧的 8086/80286 上，XLAT 有意义。但现代 CPU 上标准 mov 操作码中的索引查找更快。这样的查找甚至可以在 Pascal 中编码，使用一个数组：如果元素大小为 1/4/8/16，则会使用专用操作码前缀。使用汇编语言并非编写快速代码的必要条件。 - Arnaud Bouchez
2@Warren 对于小块数据来说这样做很愚蠢，因为使用字节表格更快、更简单，并且不会占用太多内存。（我认为 Delphi 不适用于非常小的微控制器。） - starblue
尽管我实际上是在 Delphi 中寻找解决方案，但对于小型 8 位微控制器有一个不错的 Pascal 编译器：E-LAB。逐个四位地解决方案可能在那里是有意义的。 - blerontin
显示剩余2条评论
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倍以上。
最后，我通常不喜欢在我有竞争性答案的情况下过于负面地评论被接受的答案。但在这种情况下，您接受的答案存在非常严重的问题，我想为您和任何未来的读者清楚地说明。
您在那时接受了 @Arioch 的答案，该答案包含与本答案中所示的带有两个汇编版本的 Pascal 代码相同的Pascal代码 。结果证明，这些汇编版本比Pascal代码慢得多。它们比Pascal代码慢两倍。
把高级代码转换为汇编代码就能得到更快的代码是一种常见的谬论。如果你做得不好，那么你很容易会产生比编译器生成的代码运行更慢的代码。有时候编写汇编代码是值得的，但您必须在适当的基准测试之前才能这样做。
特别令人无法容忍的是，在这里使用汇编语言的方式是如此明显，即表格解决方案将极其快速。很难想象如何将其大幅改进。
- David Heffernan
17
很好的面试问题素材。 - Warren P
不过，查找表需要您的函数进行填充 :-) - Arioch 'The
+1 如果可以用256字节的内存换取速度，那么这是一个非常好的选择，我现在就会这样做(: - user497849
LUT版本确实更快，这也是我的选择。+1 - Rudy Velthuis
@LURD 如果你好奇，我想知道是否可以设计一个测试，以对比的方式测量这些函数，但不会让整个LUT存储在CPU L1缓存中。因为实际的LUT受到RAM或至少是L2/L3缓存延迟的限制。 - Arioch 'The
显示剩余12条评论
14
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;
- Ondrej Kelle
2
就像沃伦所说的那样。模仿IntToHex :-) 但实际上我看不出这有什么意义。对于限制速度的大规模使用，应该使用256字节的查找表；对于偶尔轻松使用，则根本不需要表格。这种计算+查找方法似乎都不适用于任何一种情况。 - Arioch 'The
6我的唯一意思是：现在是星期五下午。 :-) 干杯。 - Ondrej Kelle
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-bit {$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和展开：10052 汇编位移展开：4573 LUT（查找表）调用：3192 Pascal数学，调用：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做出了三个不同的决定：
- 对于第一次调用，它消除了参数传递以及函数调用。
- 对于第二次调用，它保留了参数传递，尽管函数没有被调用。
- 对于第三次调用，它保留了改变后的参数传递方式，这种方式证明比函数调用本身要慢！奇怪！:-)
- Arioch 'The
13
1汇编语言仅为您设置了未来目标的维护工作，与查找相比，性能仍然不佳。也许您应该建议不要使用汇编语言。 - David Heffernan
1查找表比任何一次处理1到8位的变体快10倍以上。 - David Heffernan
@DavidHeffernan 我之前在问题级别的评论中也提到了查找表。然而，我绝对反对硬编码“神奇值”，就像您最近的编辑所做的那样。如果确实需要，查找表应该在程序初始化时计算。 - Arioch 'The
重点是，我的背景来自于制作库，其中1）我无法控制如何运行（编译器版本、选项），2）实际计算不是常量字节到字节的映射，LUT在那里几乎没有帮助。关于“我宁愿测量而不是尝试预测” - 抱歉，我不这么认为。我认为你只有在我放置ASM代码后才开始测量。如果谈论单人应用程序，那么对我个人而言，这些ASM函数比LUT引入的额外间接级别更容易阅读和理解。 - Arioch 'The
1陷阱在于将“Result := 0”冗余行复制到汇编程序中。这使得函数变慢了一倍...
而你成功地找到了优化的最佳点，真是幸运。
你根据我的代码进行了测量，如果我没有放置它，我怀疑你会设计自己的汇编实现来进行测量。 - Arioch 'The
显示剩余8条评论
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解决方案，在一个测试中速度更快。
总之，MirrorByte7Op()在3个测试中比LUT慢5-30％，在一个测试中比LUT快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
我在表格的最后部分添加了一些其他提议（全部内联）。循环测试一个数组作为输入和一个数组作为输出可能更加公平。 ReverseBits（LUT）和MirrorByte7Op在速度上可比，紧随其后的是BitFlipNibble（LUT），在x64上略微表现不佳。
注意：我为MirrorByte7Op的x64位部分添加了一个新的算法。它更好地利用了64位寄存器，并且指令更少。
- LU RD
11
2在我的基准测试程序中，这段代码在x86上比LUT慢7倍，在x64上比LUT慢3倍。不确定为什么LUT在x64上比x86慢那么多。我的基准测试程序会对一个1GB的字节数组进行位反转操作，数组中的可能字节模式均匀分布。 - David Heffernan
1包含我的简单基准测试。这两个程序例程都与字节模式无关。我将尝试使用字节数组。 - LU RD
1我想知道你是否计划修复这个答案中的基准测试。我不喜欢这个答案具有误导性的特点。 - David Heffernan
2编译器会很高兴！基准测试可能非常棘手。值得在 CPU 窗口中逐步查看代码实际运行情况！感谢更新。 - David Heffernan
@Arioch'The 当我写下那条评论时，它是正确的。但是这个答案已经被编辑过了。也许现在是时候停止深挖并接受你犯了错误了。我们都会犯错。我知道我也会。关键是要认识到这一点。 - David Heffernan
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接