Реверс битов (перестановка битов в обратном порядке)
Как переставить младшие биты двойного слова в обратном порядке?
Первое, что приходит в голову, — в цикле переносить биты из параметра в результат. Реализация этого алгоритма на Pascal’е выглядит следующим образом:
function ReverseBitsPasLoop(Value, Count: cardinal): cardinal;
begin;
Result:=0;
if Count>0 then repeat;
Result:=Result * 2 + Value and 1;
Value:=Value shr 1;
dec(Count);
until Count<=0;
end;Тот же алгоритм на ассемблере:
function ReverseBitsAsmLoop(Value, Count: cardinal): cardinal; asm push ebx xor ecx, ecx and edx, edx jz @ret @loop: mov ebx, eax and ebx, 1 shr eax, 1 lea ecx, [2*ecx+ebx] sub edx, 1 jnz @loop @ret: mov eax, ecx pop ebx end;
Оба приведенных варианта имеет смысл использовать только для формирования таблиц или выполнения разовых действий, т.к. они работают довольно медленно из-за наличия цикла.
Небольшое отступление. Существует ассемблерная реализация циклического алгоритма, не использующая внутри цикла таблицы, сдвиги, вращения и условные переходы. Попробуйте найти ее.
Генри Уоррен в “Алгоритмических трюках для программистов” приводит решение задачи без циклов:
function ReverseBitsPasShift(Value, Count: cardinal): cardinal;
begin;
if Count=0 then Result:=0
else begin;
Value:=(Value and $55555555) shl 1 or (Value shr 1) and $55555555;
Value:=(Value and $33333333) shl 2 or (Value shr 2) and $33333333;
Value:=(Value and $0F0F0F0F) shl 4 or (Value shr 4) and $0F0F0F0F;
Value:=(Value shl 24) or ((Value and $FF00) shl 8) or ((Value shr 8) and $FF00) or (Value shr 24);
Result:=Value shr (32-Count);
end;
end;Гребенка Уоррена на ассемблере
function ReverseBitsAsmShift(Value, Count: cardinal): cardinal; asm neg edx jz @zero push edx mov ecx, eax shr eax, 1 and eax, $55555555 and ecx, $55555555 add ecx, ecx lea edx, [eax+ecx] add eax, ecx shr edx, 2 and edx, $33333333 and eax, $33333333 add eax, eax add eax, eax lea ecx, [eax+edx] add eax, edx shr ecx, 4 and ecx, $0F0F0F0F and eax, $0F0F0F0F shl eax, 4 lea eax, [eax+ecx] bswap eax pop ecx shr eax, cl ret @zero: xor eax, eax end;
работает даже несколько быстрее алгоритма, использующего вместо сдвигов вращения:
// Step Bits // ---- -------------------------------- // 33222222222211111111110000000000 // 10987654321098765432109876543210 // (1) - - - - - - - - - - - - - - - - // 32222222222111111111100000000003 // 18967452301896745230189674523010 // (2) -- -- -- -- -- -- -- -- // 32222222211111111001100000000223 // 14567012367892345890145670123890 // (3) ---- ---- ---- ---- // 31111222200111111000000002222223 // 16789012389012345012345674567890 // (4) -------- -------- // 30000000000111111111122222222223 // 10123456789012345678901234567890 function ReverseBitsAsmRotate(Value, Count: cardinal): cardinal; asm neg edx jz @zero push edx mov ecx, eax // (1) rol eax, 2 and eax, $55555555 and ecx, $AAAAAAAA lea edx, [eax+ecx] // (2) rol edx, 4 and edx, $66666666 add eax, ecx and eax, $99999999 lea ecx, [eax+edx] // (3) rol ecx, 8 and ecx, $78787878 add eax, edx and eax, $87878787 lea edx, [eax+ecx] // (4) rol edx, 16 and edx, $7F807F80 add eax, ecx and eax, $807F807F add eax, edx rol eax, 1 pop ecx shr eax, cl ret @zero: xor eax, eax end;
Но самым эффективным решением задачи, конечно, будет табличное. Ты знал, ты знал!
var
PasTable: array[0..3, 0..255] of cardinal;
procedure InitPasTable;
var
i, j, v1, v2: integer;
begin;
for i:=0 to 255 do begin;
v1:=i;
v2:=0;
for j:=0 to 7 do begin;
v2:=v2 * 2 + v1 and 1;
v1:=v1 shr 1;
end;
PasTable[0,i]:=v2 shl 24;
PasTable[1,i]:=v2 shl 16;
PasTable[2,i]:=v2 shl 8;
PasTable[3,i]:=v2;
end;
end;
function ReverseBitsPasTable(Value, Count: cardinal): cardinal;
begin;
if Count>0
then Result:=(PasTable[0, Value and $FF]
or PasTable[1, Value shr 8 and $FF]
or PasTable[2, Value shr 16 and $FF]
or PasTable[3, Value shr 24 and $FF]
) shr (32-Count)
else Result:=0;
end;Если использовать ассемблер, то без ущерба для скорости размер таблицы может быть уменьшен в 4 раза:
var
AsmTable: array[-1..255] of cardinal;
procedure InitAsmTable;
var
i, j, v1, v2: integer;
begin;
AsmTable[-1]:=0;
for i:=0 to 255 do begin;
v1:=i;
v2:=0;
for j:=0 to 7 do begin;
v2:=v2 * 2 + v1 and 1;
v1:=v1 shr 1;
end;
AsmTable[i]:=v2;
end;
end;
function ReverseBitsAsmTable(Value, Count: cardinal): cardinal;
asm
neg edx
jz @zero
push edx
mov ecx, eax
movzx edx, ah
movzx eax, al
shr ecx, 16
mov eax, [eax*4+AsmTable+1]
or eax, [edx*4+AsmTable+2]
movzx edx, ch
movzx ecx, cl
or eax, [ecx*4+AsmTable+3]
or eax, [edx*4+AsmTable+4]
pop ecx
shr eax, cl
ret
@zero:
xor eax, eax
end;Скорость работы рассмотренных алгоритмов для различного количества бит на доступных мне машинах приведена в таблицах ниже:
Time (msec) of 128*1024*1024 runs
on i5-2300 for different bit counts
==================================================
Function 8 16 24 32
--------------------------------------------------
ReverseBitsAsmTable 390 359 343 344
ReverseBitsPasTable 483 406 390 405
ReverseBitsAsmShift 500 483 484 483
ReverseBitsAsmRotate 578 592 593 593
ReverseBitsPasShift 796 780 795 796
ReverseBitsAsmLoop 920 1576 2277 2964
ReverseBitsPasLoop 1061 1950 2917 3901 Time (msec) of 128*1024*1024 runs
on E6850 for different bit counts
==================================================
Function 8 16 24 32
--------------------------------------------------
ReverseBitsAsmTable 391 359 360 359
ReverseBitsPasTable 438 406 406 406
ReverseBitsAsmShift 516 531 532 531
ReverseBitsAsmRotate 531 547 547 531
ReverseBitsPasShift 953 938 953 953
ReverseBitsAsmLoop 937 1922 2610 3078
ReverseBitsPasLoop 1031 2891 4031 4125Множество решений этой увлекательной задачи можно найти интернете. Но, скорее всего, это будет либо цикл, либо гребенка. Если же вы знаете необычный или очень быстрый алгоритм, не стесняйтесь, поделитесь им.