W dniu wtorek, 1 września 2015 10:31:11 UTC+2 użytkownik szemrany napisał:
> On Tue, 1 Sep 2015 08:03:15 +0200, voy wrote:
>
> >> Może jakieś operacje arytmetyczne?
> >
> > Nie bardzo wiem o co Ci chodzi :),
> > ale masz tu przykład funkcji, która zlicza ilość ustawionych bitów,
> > iterując tylko po ustawionych:
>
> Ok, jeszcze raz, na liczbach 32 bitowych, żeby było prościej:
>
> - mam np. liczbe 1234567890
> - binarnie to jest 01001001100101100000001011010010
> - chcę teraz wyliczyć/znaleźć indeks pierszego zapalonego bitu
> - indeks liczę od prawej strony, jak wagi bitów
> - wynik: 1 (indeks bazujący na 0)
>
> drugi przykład:
> - liczba np. 4255820448
> - binarnie 11111101101010101010101010100000
> - wynik 5
>
> I jak pisałem w pierwszym poście, czego raczyłeś nie wziąć pod uwagę,
> rozwiązanie bazujące na pętli odrzucam jako oczywiste i najprostsze.
> Szukam innego, szybszego.

http://stackoverflow.com/questions/757059/position-o
f-least-significant-bit-that-is-set

do góry

On Monday, August 31, 2015 at 9:58:51 PM UTC+2, szemrany wrote:
> Hejka,
>
> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
> ustawione jakieś bity, ale czasem nie.
> Jak najszybciej znaleźć indeks ustawionego bitu?
> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
> odkryć, że "pali" się np. czterdziesty ósmy?
> Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
> w najgorszym razie trzeba przeiterować 63 razy.
> Może da się szybciej?
> Może jakieś operacje arytmetyczne?
>
> --
> 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ę"

( x & ~(x-1) )

do góry

On Tue, 1 Sep 2015 02:57:01 -0700 (PDT), M.M. wrote:

> ( x & ~(x-1) )

Lub (x & -x ). To jest też w linku, który podał godek.
Ale to zwraca wartość bitu, a nie indeks, czyli problem przesuwania nadal
pozostaje.

--
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ę"

do góry

Użytkownik "szemrany" <s...@o...off> napisał w wiadomości
news:1i3y3j1aqrgzm.oc3pbikd1n92.dlg@40tude.net...
> Hejka,
>
> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
> ustawione jakieś bity, ale czasem nie.
> Jak najszybciej znaleźć indeks ustawionego bitu?

Proponuję rozwiązanie sprzętowe za pomocą rozkazu BSR.
W rejestrze RAX umieszczamy liczbę do sprawdzenia np.:

mov rax, 10000000b
bsr rbx, rax

Po wykonaniu powyższych rozkazów w rejstrze RBX bedzie warość 7


Pozdrawiam
Radek

do góry

Użytkownik "szemrany" <s...@o...off> napisał:

> Hmm... tak, tylko, że ja pytam jak odkryć, że to akurat czterdziesty ósmy -
> bo tego nie wiem, a nie jak sprawdzić czy czterdziesty ósmy jest ustawiony,
> bo to trywialne.

Szukaj polowkowo.

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus

do góry

On Tue, 1 Sep 2015 12:30:28 +0200, Radoslaw Szwed wrote:

> mov rax, 10000000b
> bsr rbx, rax

Tylko, że rejest RAX wymaga x64, a ja kompiluję na 32 bity. Ale już ten
rozkaz też biorę pod uwagę i go w testach zastosuję do dwóch połówek po 32
bity.

--
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ę"

do góry

On 01.09.2015 13:04, szemrany wrote:
> On Tue, 1 Sep 2015 12:30:28 +0200, Radoslaw Szwed wrote:
>
>> mov rax, 10000000b
>> bsr rbx, rax
>
> Tylko, że rejest RAX wymaga x64, a ja kompiluję na 32 bity. Ale już ten
> rozkaz też biorę pod uwagę i go w testach zastosuję do dwóch połówek po 32
> bity.

Nie musisz używaś assemblera.

__builtin_ctz //gcc
_BitScanForward, _BitScanForward64 //VS

pzdr
bartekltg

do góry

On Tue, 01 Sep 2015 13:37:58 +0200, bartekltg wrote:

> Nie musisz używaś assemblera.
>
> __builtin_ctz //gcc
> _BitScanForward, _BitScanForward64 //VS
>
> pzdr
> bartekltg

Piszę w Delphi ;-)

--
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ę"

do góry

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ę"

do góry

On 01.09.2015 14:29, szemrany wrote:
> On Tue, 01 Sep 2015 13:37:58 +0200, bartekltg wrote:
>
>> Nie musisz używaś assemblera.
>>
>> __builtin_ctz //gcc
>> _BitScanForward, _BitScanForward64 //VS
>>
>> pzdr
>> bartekltg
>
> Piszę w Delphi ;-)

Toto jeszcze żyje? ;-)

Freepascal ma tu wbudowane:
http://wiki.freepascal.org/FPC_New_Features_2.6.0#Bi
tscan_intrinsics

delphi prawdopodobnie też, ale trzeba poszukać w ichniejszej
dokumentacji... której na szybko nie wygoglalem;-)

Z tego co pamietam procedury w asm pisało się tam bardzo przyjemnie,
więc jak nie znajdziesz, zrób jak Radosław radzi i napisz samemu.
bsf/bsr dzialają tak samo na 32 bitach, trzeba tylko pamitać,
w czym przychodzi zmienna i gdzie umieścić wynik.

pzdr
bartekltg

do góry