zliczanie bitów

[arigo]

Zły algorytm, przełożony na assembler, albo nawet na kod maszynowy, jest nadal złym algorytmem.

a co to ma do niemoznosci rzetelnego porownywania wydajnosci algorytmow w jezykach wysokiego poziomu?

[Fibik]

Może nie miało mieć? Już nie pamiętam.

[drunkard]

Żeby zakończyć w miarę merytorycznie wrzucę kod wygenerowany przez Borland C++ 5.5 z przeprosinami dla kompilatora że posądzałem go o korzystanie ze stosu dla wyników pośrednich.

; int nbits1 (byte b4[])
;
push ebp
mov ebp,esp
mov eax,dword ptr [ebp+8]
;
; {
; return t8[b4[0]] + t8[b4[1]] + t8[b4[2]] + t8[b4[3]];
;
?live16385@16: ; EAX = b4
@1:
xor edx,edx
mov dl,byte ptr [eax]
xor ecx,ecx
mov cl,byte ptr [edx+_t8]
xor edx,edx
mov dl,byte ptr [eax+1]
movzx edx,byte ptr [edx+_t8]
add ecx,edx
xor edx,edx
mov dl,byte ptr [eax+2]
movzx edx,byte ptr [edx+_t8]
add ecx,edx
movzx eax,byte ptr [eax+3]
movzx eax,byte ptr [eax+_t8]
add ecx,eax
mov eax,ecx
;
; }

[Fibik]

Zamiast tego podwójnego indeksowania (i przekazywania wskaźnika do tablicy 4 bajtów),
można to zrobić inaczej:

int nbits(uint n)
{
return t8[n & 0xFF] + t8[(n >> 8) & 0xFF] + t8[(n >> 16) & 0xFF] + t8[(n >> 24) & 0xFF];
}

To jest szybsze (taką wersję testowałem).

Stos jest używany, raczej do przekazywania parametrów i na zmienne lokalne (jeśli jest ich sporo).
Borland 5 ma chyba opcję wyboru kompilatora: borland lub intel. Ten drugi dużo lepiej optymalizuje.