Реверс битов (перестановка битов в обратном порядке)

Сентябрь 13, 2011 — Шарахов А.П.

Как переставить младшие биты двойного слова в обратном порядке?

Первое, что приходит в голову, — в цикле переносить биты из параметра в результат. Реализация этого алгоритма на 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, получаем неплохую цифру. Конечно, есть накладные расходы на вызов подпрограммы ...

Реверс битов

Тут нет ничего странного, т.к. абсолютно все использованные в цикле команды очень медленные.