eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybkie szukanie ustawionego bituRe: Szybkie szukanie ustawionego bitu
  • Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.supermedia.pl!news.nask.pl!news.na
    sk.org.pl!news.unit0.net!cyclone01.ams2.highwinds-media.com!voer-me.highwinds-m
    edia.com!peer01.am1!peering.am1!peer01.fr7!news.highwinds-media.com!newsfeed.ne
    ostrada.pl!unt-exc-02.news.neostrada.pl!unt-spo-a-01.news.neostrada.pl!news.neo
    strada.pl.POSTED!not-for-mail
    From: szemrany <s...@o...off>
    Subject: Re: Szybkie szukanie ustawionego bitu
    Newsgroups: pl.comp.programming
    User-Agent: 40tude_Dialog/2.0.15.84
    MIME-Version: 1.0
    Content-Type: text/plain; charset="utf-8"
    Content-Transfer-Encoding: 8bit
    Sender: n...@p...no
    References: <1...@4...net>
    Date: Tue, 1 Sep 2015 14:40:34 +0200
    Message-ID: <wc4ru3v45dm0$.1mtwq7sfflbyu.dlg@40tude.net>
    Lines: 53
    Organization: Telekomunikacja Polska
    NNTP-Posting-Host: 89-71-60-55.dynamic.chello.pl
    X-Trace: 1441111235 unt-rea-a-01.news.neostrada.pl 4778 89.71.60.55:2227
    X-Complaints-To: a...@n...neostrada.pl
    X-Received-Body-CRC: 3884815321
    X-Received-Bytes: 2552
    Xref: news-archive.icm.edu.pl pl.comp.programming:208102
    [ ukryj nagłówki ]


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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: