Как переставить младшие биты двойного слова в обратном порядке?
Первое, что приходит в голову, — в цикле переносить биты из параметра в результат. Реализация этого алгоритма на 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
Множество решений этой увлекательной задачи можно найти интернете. Но, скорее всего, это будет либо цикл, либо гребенка. Если же вы знаете необычный или очень быстрый алгоритм, не стесняйтесь, поделитесь им.
Comments (8)
А если так: @: ror eax,1
А если так:
@: ror eax,1 ; // >> 'C (выдвигаем крайний правый бит в CARRY)
adc ebx,ebx ; // (логический сдвиг влево с установкой крайнего правого бита из CARRY)
dec ecx
jnz @
Наверняка быстрее будет!
А если проверить,
то можно убедиться в том, что это намного медленнее.
Реверс битов
Я делал так:
unsigned int i; // исходное число
unsigned int n; // длина исходного числа (число значащих бит)
unsigned int t; // результат
asm { // зеркальное отражение битов
mov eax, i;
xor ebx, ebx;
mov ecx, n;
@: rcr eax, 1; // >> 'C (выдвигаем крайний бит в CARRY)
rcl ebx, 1; // << 'C (задвигаем из CARRY в крайний бит результата)
loop @, ecx;
mov t, ebx;
}
Реверс битов
Вероятно, скорость этого варианта будет примерно такой же, как у двух первых алгоритмов.
Реверс битов
Должно быть существенно быстрее: в цикле всего 3 самых простых оператора (включая саму команду цикла) и не используются обращения к памяти (всё в регистрах). Имеет шансы побить даже "продвинутые" алгоритмы.
Реверс битов
Проверено, шансов нет.
Реверс битов
Это странно.
По сравнению с первым (явно неоптимальным) ассемблерным алгоритмом, эта реализация д.б. раз в 5 быстрее (просто по числу команд). Делим результаты из таблицы на 5, получаем неплохую цифру. Конечно, есть накладные расходы на вызов подпрограммы ...
Реверс битов
Тут нет ничего странного, т.к. абсолютно все использованные в цикле команды очень медленные.