воскресенье, 7 апреля 2013 г.

"Быстрый" подсчёт числа взведённых бит


unit Bits;
 
interface
 
function  l3BitCount(X: Longint): Longint;
  {* - "быстро" подсчитать число бит. }
function  l3BitCountPrim(X: Longint): Longint;
  {* - подсчитать число бит. }
 
implementation
 
var
 
 l3BitTable: array[0..255] of Longint;
 
procedure LoadBitTable;
var
 i : Longint;
begin
 for i := 0 to 255 do
  l3BitTable[i] := l3BitCountPrim(i);
end;
 
function l3BitCountPrim(X: Longint): Longint;
  {-}
var
 Y : Long;
begin
 Y := X;
 Y := Y - ((Y shr 1) and $55555555);
 Y := (Y and $33333333) + ((Y shr 2) and $33333333);
 Y := Y + Y shr 4;
 Y := Y and $0f0f0f0f;
 Y := Y + Y shr 8;
 y := Y + Y shr 16;
 Result := Y and $000000ff;
end;
 
function l3BitCount(X: Longint): Longint;
  register;
  {-}
asm
   test eax,eax
   jz @@Done
 
   push ebx
   mov ebx,eax
 
   xor ecx,ecx
   xor edx,edx
 
   mov cl,bl
   mov dl,bh
 
   shr ebx,16
   mov eax, dword ptr [l3BitTable+ecx*4]
 
   add eax, dword ptr [l3BitTable+edx*4]
   mov cl,bl
 
   add eax, dword ptr [l3BitTable+ecx*4]
   mov dl,bh
 
   add eax, dword ptr [l3BitTable+edx*4]
   pop ebx
@@Done:
end;
 
initialization
 LoadBitTable;
end.


-- позже я напишу про "ассоциативные битовые массивы". Для "экономии на спичках". Когда у объекта бывает множество различных доступных свойств, но в реальности свойств с изменёнными значениями, по сравнению с параметрами по-умолчанию, - немного.

Тогда можно сначала хранить битовую маску для обозначения того - какое свойство у объекта отличается от значения по-умолчанию, а какое - нет. И храним только значения отличающиеся от значений по-умолчанию. А из битовой маски достаточно просто получаем смещение к интересующему значению.

Комментариев нет:

Отправить комментарий