fast algor - nr pierwszego ustawionego bita

Mamy integer z 32 bity i teraz chcę z tego numer pierwszego bita z 1: 0, 1, 2, itd.

Jak to najszybciej załatwić, może jest jakiś jeden rozkaz w asm do tego?
Są takie raskazy: bs

Na piechotę od cholery czasu to zajmuje; jakoś tak to wygląda

function fbit(z : uint) : integer;
begin

  i := 0;

  if z = 0 then i := -1 // nie ma bitów
  else while (z and 1) = 0 do begin

     z := z shr 1; inc(i);

  end;
 
 fbit := i;

end;

O! Chyba znalazłem coś:
http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html

Aż 40 cykli na 486?
Przecież to nie jest skomplikowane... jak np. dzielenie!

Ciekawe ile cykli jest na nowszych procesorach.

Można pominąć przesuwanie bitów: "z shr 1". Sprawdzać po kolei: (z and 1), (z and 2), (z and 4), (z and 8) itd.

Wersja bez ASM - jeśli używasz FPC:
http://www.freepascal.org/docs-html/rtl/system/bsfword.html

vpiotr napisał(a):

Wersja bez ASM - jeśli używasz FPC:
http://www.freepascal.org/docs-html/rtl/system/bsfword.html

Zmartwię zapewne was: FPC używa wewnętrznie assemblera do tego jak się domyślam. (Sprawdziłem, to nawet nie jest traktowane jako procedura ale jako wewnętrzny operator więc można się spodziewać dobrego kodu wynikowego).
I jeżeli już to pytacz szuka http://www.freepascal.org/docs-html/rtl/system/bsfdword.html

Aż 40 cykli na 486?
Przecież to nie jest skomplikowane... jak np. dzielenie!

Instrukcje które nie są często używane są słabo zoptymalizowane. Jak się domyślam to optymalność użycia tej pojedyńczej instrukcji nie musi być wcale lepsza niż porządny kod assemblera bez tej instrukcji na wszystkich procesorach. Dosyć często tak jest z instrukcjami które używa się raczej rzadko.

Można pominąć przesuwanie bitów: "z shr 1". Sprawdzać po kolei: (z and 1), (z and 2), (z and 4), (z and 8) itd.

Jeżeli dobrze domyślam się stanu flag po shr to można sobie darować and.

ruh5jdgeuh napisał(a):

vpiotr napisał(a):

Wersja bez ASM - jeśli używasz FPC:
http://www.freepascal.org/docs-html/rtl/system/bsfword.html

Zmartwię zapewne was: FPC używa wewnętrznie assemblera do tego jak się domyślam. (Sprawdziłem, to nawet nie jest traktowane jako procedura ale jako wewnętrzny operator więc można się spodziewać dobrego kodu wynikowego).

To jest "intrinsic" czyli Pascalowa wersja instrukcji x86, prawdopodobnie tylko dla tej rodziny procesorów.
Tym chciałeś nas zmartwić? Nikt tu nie pisał o ARM-ie...

To jest "intrinsic" czyli Pascalowa wersja instrukcji x86, prawdopodobnie tylko dla tej rodziny procesorów.

Tak, zresztą kod sam to wskazuje:

{$if defined(cpui386) or defined(cpux86_64)}
{$define FPC_HAS_INTERNAL_BSX_BYTE}
{$define FPC_HAS_INTERNAL_BSX_WORD}
{$define FPC_HAS_INTERNAL_BSX_DWORD}
{$endif} 

Natomiast jeżeli procesorem nie jest x86 lub x64, instrukcja ta jest emulowana. To samo zresztą tyczy się wielu podobnych instrukcji typu rol/ror.

Tym chciałeś nas zmartwić? Nikt tu nie pisał o ARM-ie...

Nie, zmartwienie jest takie że ta procedura która mówiłeś że jest bez asma, jest w rzeczywistości napisana na tym.

8wit3tyiqrt38 napisał(a):

Nie, zmartwienie jest takie że ta procedura która mówiłeś że jest bez asma, jest w rzeczywistości napisana na tym.

Ale wewnętrznie - jeśli już. Dla programisty to duży plus, bo nie musi się wgłębiać w jej detale.

ruh5jdgeuh napisał(a):

Instrukcje które nie są często używane są słabo zoptymalizowane. Jak się domyślam to optymalność użycia tej pojedyńczej instrukcji nie musi być wcale lepsza niż porządny kod assemblera bez tej instrukcji na wszystkich procesorach. Dosyć często tak jest z instrukcjami które używa się raczej rzadko.

Od Pentium 4 ten rozkaz ma chyba już tylko 6 cykli, więc raczej nie zrobisz szybciej.

W takiej pętli pewnie wyjdzie z 10 cykli na jeden krok, czyli cała operacja do 300.

ergo napisał(a):

Można pominąć przesuwanie bitów: "z shr 1". Sprawdzać po kolei: (z and 1), (z and 2), (z and 4), (z and 8) itd.

if z and 1 then 0
else if z and 2 then 1
...

Takie coś proponujesz?

To już lepiej binarnie to robić:

if z and $ffff then // dolna połowa
if z and $ff then
if z and $f then
if z and 3 then
if z and 1 then i := 0
else i := 1
else ...
else ...
else // tu tak samo ale z hiword
...

jakoś tak - góra 5 testów - 2^5 = 32.

A może tak:

if z=0 then fbit:=-1;
else fbit:=Trunc(Log2(z));

Obecne procesory są w zasadzie takie same jak ten pentium 4 (chyba prawie sprzed 10 lat),
jedynie nawtykali kilka rdzeni, cache trójpoziomowe, i inne bajery - rozszerzenia tego MMX/sse
czyli nowe rozkazy i na większych rejestrach...
no i ta wirtualizacja, rządzenie energią, chłodzie - tryby turbo i inne takie pierdoły nieważne w programowaniu.

A ten logarytm to niepoważny pomysł.
Zresztą to źle oblicza - od tyłu, czyli najstarszy bit, zamiast najmłodszy.

http://en.wikipedia.org/wiki/Find_first_set