Текущий архив: 2011.08.14;
Скачать: CL | DM;

Вниз

Количество нулевых битов в числе.   Найти похожие ветки 

← →
Leon-Z ©   (2011-03-03 20:39) [0]

Как посчитать кол-во нулевых битов в числе?
Например дано число: num: Byte;
Существуют по крайней мере 2 способа: простой и быстрый.
Можете рассказать о них, пожалуйса ?

---

← →
Inovet ©   (2011-03-03 21:01) [1]

1. По таблице в массиве, индекс - число, елемент - результат
0, 1, 1, 2, 1, 2, 2, 3, ..., 8

2. Сдвигом вправо в цикле пока не 0, результат сдвига = 1 - увеличить счётчик.

Первый быстрее, по сложности так и проще тоже первый.

---

← →
Leon-Z ©   (2011-03-03 21:13) [2]

> Inovet ©   (03.03.11 21:01) [1]

Большое, большое - пре-большое СПАСИБО !!!

---

← →
han_malign   (2011-03-04 08:43) [3]

есть еще средний:
dw:= dw and $55555555 + (dw and $AAAAAAAA) shr 1;
dw:= dw and $33333333 + (dw and $CCCCCCCC) shr 2;
dw:= (dw + dw shr 4) and $0F0F0F0F;
dw:= (dw + dw shr 8);
cnt:= (dw + dw shr 16) and $FF;

---

← →
Leonid Troyanovsky ©   (2011-03-04 18:00) [4]

han_malign   (04.03.11 08:43) [3]

Здесь как-то было объемное обсуждение,
в завершение которого были представлены
тестовые программы и их результаты.

К сожалению, я не помню, кто их скомпилировал,
(подозреваю, что Sha), а в delphimaster.net оный
топик не находится.

Так как я принял участие в тестировании, могу
представить сохраненные исходники:


unit BitCount;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls, ExtCtrls;

type
 TForm1 = class(TForm)
   Memo1: TMemo;
   Button1: TButton;
   Timer1: TTimer;
   procedure Button1Click(Sender: TObject);
   procedure Timer1Timer(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

var
 Form1: TForm1;

implementation

{$R *.dfm}

const
 BitCnt: array[0..255] of byte = (
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8);

function ElementCount1(pSet: PByte; ByteSize: integer): integer;
var
 n: integer;
begin;
 Result:=0;
 for n:=0 to ByteSize-1 do begin;
   Inc(Result, BitCnt[pSet^]);
   Inc(pSet);
   end;
 end;

function ElementCount4(pSet : PByteArray; ByteSize : Integer): Integer;
begin
Result := 0;
While (ByteSize >= 4) do begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]] + BitCnt[pSet[2]] + BitCnt[pSet[3]]);
Inc(PByte(pSet), 4);
Dec(ByteSize, 4);
end;
If (ByteSize >= 2) then begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]]);
Inc(PByte(pSet), 2);
Dec(ByteSize, 2);
end;
If (ByteSize = 1) then
Inc(Result, BitCnt[pSet[0]]);
end;

function ElementCount2(pSet: pIntegerArray; Bound: integer): integer;
var
 v, i: integer;
begin;
 Result:=0;
 i:=Bound shr 2;
 if Bound and 3<>0 then begin;
   v:=0;
   if Bound and 1<>0 then v:=pByte(integer(pSet) + Bound - 1)^;
   if Bound and 2<>0 then v:=v shl 16 + pWord(@pSet[i])^;
   v:=v - v shr 1 and $55555555;
   v:=v and $33333333 + v shr 2 and $33333333;
   Result:=(v + v shr 4) and $0F0F0F0F;
   end;
 while i>0 do begin;
   v:=pSet[i-1];
   v:=v - v shr 1 and $55555555;
   v:=v and $33333333 + v shr 2 and $33333333;
   Result:=Result + (v + v shr 4) and $0F0F0F0F;
   dec(i);
   end;
 Result:=(Result + Result shr 8) and $00FF00FF;
 Result:=(Result + Result shr 16) and $1FF;
 end;

function ElementCountForSetOfChar4(pSet: PByteArray): Integer;
var
 i: integer;
begin;
 Result:=0;
 i:=32;
 repeat;
   Result:=Result + BitCnt[pSet[i-1]];
   Result:=Result + BitCnt[pSet[i-2]];
   Result:=Result + BitCnt[pSet[i-3]];
   Result:=Result + BitCnt[pSet[i-4]];
   Result:=Result + BitCnt[pSet[i-5]];
   Result:=Result + BitCnt[pSet[i-6]];
   Result:=Result + BitCnt[pSet[i-7]];
   Result:=Result + BitCnt[pSet[i-8]];
   i:=i-8;
   until i=0;
 end;

function ElementCountForSetOfChar2(pSet: pIntegerArray): integer;
var
 s, u, v, i: integer;
begin;
 Result:=0;
 i:=8;
 repeat;
   v:=pSet[i-1];
   u:=v;
   v:=v and $AAAAAAAA;
   v:=v shr 1;
   u:=u-v;
   v:=u;
   u:=u and $CCCCCCCC;
   v:=v xor u;
   u:=u shr 2;
   s:=u+v;

   v:=pSet[i-2];
   u:=v;
   v:=v and $AAAAAAAA;
   v:=v shr 1;
   u:=u-v;
   v:=u;
   u:=u and $CCCCCCCC;
   v:=v xor u;
   u:=u shr 2;
   u:=u+v;

   u:=u+s;

   v:=u;
   u:=u and $F0F0F0F0;
   v:=v xor u;
   u:=u shr 4;
   u:=u+v;

   Result:=Result + u;
   i:=i-2;
   until i=0;

 v:=Result;
 Result:=Result and $FF00FF00;
 v:=v xor Result;
 Result:=Result shr 8;
 Result:=Result + v;

 v:=Result;
 Result:=Result shr 16;
 Result:=Result + v;
 Result:=Result and $1FF;
 end;

type
 MyBaseType = 0..255;
 MySetType = Set of MyBaseType;
var
 MySet: MySetType;
 TimerCount: integer= 0;

procedure TForm1.Button1Click(Sender: TObject);
begin;
 Randomize;
 TimerCount:=10;
 Memo1.Lines.Clear;
 end;

procedure TForm1.Timer1Timer(Sender: TObject);
var
 t1, t2, t3: cardinal;
 i, c1, c2: integer;
 e: MyBaseType;
begin;
 if TimerCount>0 then begin;
   MySet:=[];
   for e:=Low(MyBaseType) to High(MyBaseType) do begin;
     RandSeed:=RandSeed * $08088405 + 1;
     if RandSeed<0 then include(MySet, e);
     end;
   dec(TimerCount);
   t1:=GetTickCount;
   for i:=1 to 100000000 do c1:=ElementCountForSetOfChar5(@MySet);
   t2:=GetTickCount;
   for i:=1 to 100000000 do c2:=ElementCountForSetOfChar4(@MySet);
   t3:=GetTickCount;
   Memo1.Lines.Add(IntToStr(t2-t1));
   Memo1.Lines.Add(IntToStr(t3-t2));
   if c1<>c2 then Memo1.Lines.Add("ERROR -----------------");
   Memo1.Lines.Add("");
   end;
 end;

end.


Если кто вдруг  вспомнит этот код, то, с удовольствием
услышим комментарии.

--
Regards, LVT.

---

← →
Leonid Troyanovsky ©   (2011-03-04 18:02) [5]

> Leonid Troyanovsky ©   (04.03.11 18:00) [4]

Вот еще пара функций:

function ElementCountForSetOfChar3(pSet: pointer): integer;
asm
 push esi
 mov esi, eax
 push edi    
 push ebx
 mov edi, 4
 xor eax, eax

@loop:
 mov ebx, [esi]       //  v:=pSet[i-1];
 mov ecx, ebx         //  u:=v;
 and ebx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr ebx, 1           //  v:=v shr 1;
 mov edx, [esi+4]     //  v:=pSet[i-2];         (moved)
 sub ecx, ebx         //  u:=u-v;
 mov ebx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor ebx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;
 add esi, 8           //  i:=i-2;               (moved)
 add ebx, ecx         //  s:=u+v;

 mov ecx, edx         //  u:=v;
 and edx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr edx, 1           //  v:=v shr 1;
 sub ecx, edx         //  u:=u-v;
 mov edx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor edx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;

 add ebx, edx         //  u:=u+v;
 add ebx, ecx         //  u:=u+s;

 mov edx, ebx         //  v:=u;
 and ebx, $F0F0F0F0   //  u:=u and $F0F0F0F0;
 xor edx, ebx         //  v:=v xor u;
 shr ebx, 4           //  u:=u shr 4;

 add eax, edx         //  u:=u+v;
 add eax, ebx         //  Result:=Result + u;

 sub edi, 1
 jg @loop             //  until i=0;

 mov edx, eax         //  v:=Result;
 and eax, $FF00FF00   //  Result:=Result and $FF00FF00;
 xor edx, eax         //  v:=v xor Result;
 shr eax, 8           //  Result:=Result shr 8;
 add eax, edx         //  Result:=Result + v;

 mov edx, eax         //  v:=Result;
 shr eax, 16          //  Result:=Result shr 16;
 add eax, edx         //  Result:=Result + v;
 and eax, $1FF        //  Result:=Result and $1FF;

 pop ebx
 pop edi
 pop esi
 end;

function ElementCountForSetOfChar5(pSet: pointer): integer;
asm
 push esi
 push edi
 push ebx
 xor esi, esi
 mov edi, 4

@loop:
 mov ebx, [eax]       //  v:=pSet[i-1];
 mov ecx, ebx         //  u:=v;
 and ebx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr ebx, 1           //  v:=v shr 1;
 mov edx, [eax+4]     //  v:=pSet[i-2];         (moved)
 sub ecx, ebx         //  u:=u-v;
 mov ebx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor ebx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;
 add eax, 8           //  i:=i-2;               (moved)
 add ebx, ecx         //  s:=u+v;

 mov ecx, edx         //  u:=v;
 and edx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr edx, 1           //  v:=v shr 1;
 sub ecx, edx         //  u:=u-v;
 mov edx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor edx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;

 add ebx, edx         //  u:=u+v;
 add ebx, ecx         //  u:=u+s;

 mov edx, ebx         //  v:=u;
 and ebx, $F0F0F0F0   //  u:=u and $F0F0F0F0;
 xor edx, ebx         //  v:=v xor u;
 shr ebx, 4           //  u:=u shr 4;

 add esi, edx         //  u:=u+v;
 add esi, ebx         //  Result:=Result + u;

 sub edi, 1
 jg @loop             //  until i=0;

 mov eax, esi         //  v:=Result;
 and esi, $FF00FF00   //  Result:=Result and $FF00FF00;
 xor eax, esi         //  v:=v xor Result;
 shr esi, 8           //  Result:=Result shr 8;
 pop ebx
 add esi, eax         //  Result:=Result + v;

 mov eax, esi         //  v:=Result;
 shr esi, 16          //  Result:=Result shr 16;
 pop edi
 add eax, esi         //  Result:=Result + v;
 and eax, $1FF        //  Result:=Result and $1FF;

 pop esi
 end;


--
Regards, LVT.

---

← →
Leonid Troyanovsky ©   (2011-03-04 18:04) [6]

> Leonid Troyanovsky ©   (04.03.11 18:02) [5]

А вот результаты на моей домашней Windows 7 (D6):
4883
3136

2574
2683

4789
3573

2199
2434

3713
3401

3074
4446

3167
4867

3853
4290

3526
3416

2605
5102

--
Regards, LVT.

---

← →
xayam ©   (2011-05-04 21:12) [7]

> Leonid Troyanovsky ©   (04.03.11 18:00) [4]
> Здесь как-то было объемное обсуждение,
> в завершение которого были представлены
> тестовые программы и их результаты.
> К сожалению, я не помню, кто их скомпилировал,
> (подозреваю, что Sha), а в delphimaster.net оный
> топик не находится.

http://www.delphimaster.net/view/2-1214996937  ?

PS По исходникам легко находится

---

← →
Amoeba_   (2011-05-04 23:50) [8]

А вот ф-ии из библиотеки QStrings.

Q_CountOfFreeBits возвращает число сброшенных (нулевых) битов в байтовом
 массиве, адресуемом параметром P, длиной L байт.

Q_CountOfSetBits возвращает число установленных (единичных) битов в байтовом
 массиве, адресуемом параметром P, длиной L байт.


function Q_CountOfSetBits(P: Pointer; L: Cardinal): Cardinal;
asm
       PUSH    EBX
       PUSH    ESI
       MOV     EBX,EAX
       XOR     EAX,EAX
       SUB     EDX,2
       JS      @@nx
@@lp:   MOVZX   ECX,BYTE PTR [EBX+EDX]
       MOVZX   ESI,BYTE PTR [EBX+EDX+1]
       MOVZX   ECX,BYTE PTR [ECX+BitTable]
       ADD     EAX,ECX
       MOVZX   ESI,BYTE PTR [ESI+BitTable]
       ADD     EAX,ESI
       SUB     EDX,2
       JNS     @@lp
@@nx:   INC     EDX
       JZ      @@qt2
       POP     ESI
       POP     EBX
       RET
@@qt2:  MOVZX   ECX,BYTE PTR [EBX]
       MOVZX   ECX,BYTE PTR [ECX+BitTable]
       ADD     EAX,ECX
       POP     ESI
       POP     EBX
end;

function Q_CountOfFreeBits(P: Pointer; L: Cardinal): Cardinal;
asm
       PUSH    EDX
       CALL    Q_CountOfSetBits
       NEG     EAX
       POP     EDX
       LEA     EAX,[EAX+EDX*8]
end;


---

← →
KilkennyCat ©   (2011-05-05 00:53) [9]

главное - вовремя :)

---

← →
Германн ©   (2011-05-05 01:52) [10]

> KilkennyCat ©   (05.05.11 00:53) [9]

Это Хайям увидел ошибку у себя и решил эксгумировать все сообщения LVT, которые указывали на эту ошибку. Зачем ему это понадобилось - непонятно. :)

---

Страницы: 1 вся ветка

Текущий архив: 2011.08.14;
Скачать: CL | DM;

Наверх

Память: 0.52 MB
Время: 0.01 c