Количество нулевых битов в числе.

← →
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 © (05.05.11 00:53) [9]

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

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