Reasumując chcę wszystkim podziękować za uwagi i sugestie oraz chcę
przedstawić wyniki testów. Zrobiłem 4 funkcje operujące na różnych
algorytmach i pomierzyłem ich wydajność.

Założenie: daję do sprawdzenia liczbę, która ma ustawiony dopiero 38 bit (i
inne dalej), pętla wykonuje się 10 mln razy, oto wyniki:

- Metoda klasyczna czyli pętla while i przesuwanie bitów w prawo, aż będzie
ustawiony najmłodsdzy bit

Czas: 813 ms

- Metoda dzielenia połówkowego/binarnego, algorytm z wiki:

function ctz (x)
if x = 0 return 32
n <- 0
if (x & 0x0000FFFF) = 0: n <- n + 16, x <- x >> 16
if (x & 0x000000FF) = 0: n <- n + 8, x <- x >> 8
if (x & 0x0000000F) = 0: n <- n + 4, x <- x >> 4
if (x & 0x00000003) = 0: n <- n + 2, x <- x >> 2
if (x & 0x00000001) = 0: n <- n + 1
return n

Czas: 67 ms

- Metoda z X & -X (pozostawienie tylko najmłodszego ustawionego bitu),
potem sprawdzenie młodszych 32 bitów przez &, jeśli nic nie ma to dodanie
do wyniki 32, przesunięcie starszych 32 bitów w prawo i sprawdzenie czy coś
w nich jest przez &, a gdy jest to switch na wartości od 2 do 32, który
zwraca indeks (dla 256 zwraca 8)

Czas: 51 ms

- Assemblerowa instrukcja BSF użyta dwa razy na starszych i młodszych
bitach liczby 64 bitowej:

BSF EAX, DWORD PTR [&u64]
JNZ @@Exit
BSF EAX, DWORD PTR [&u64 + 4]
JZ @@Exit
ADD EAX, 32
@@Exit:
MOV &Result, EAX

Czas: 28 ms

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"