eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybkie szukanie ustawionego bitu
Ilość wypowiedzi w tym wątku: 27

  • 1. Data: 2015-08-31 21:58:47
    Temat: Szybkie szukanie ustawionego bitu
    Od: szemrany <s...@o...off>

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


  • 2. Data: 2015-08-31 22:39:28
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: Tomek Kańka <t...@t...eu.org>

    szemrany <s...@o...off> napisał(a)
    > 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?

    A to nie jest "premature optymzation":)?

    > Może jakieś operacje arytmetyczne?

    Jeśłi to tylko jeden bit, to szukaj binarnie.

    --
    Tomek


  • 3. Data: 2015-08-31 22:49:21
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: szemrany <s...@o...off>

    On Mon, 31 Aug 2015 20:39:28 +0000 (UTC), Tomek Kańka wrote:

    >> 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?
    >
    > A to nie jest "premature optymzation":)?

    Raczej nie, to część struktury używanej wielowątkowo i często.

    >> Może jakieś operacje arytmetyczne?
    >
    > Jeśłi to tylko jeden bit, to szukaj binarnie.

    Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
    elementów w tablicy niż tylko 0 i 1.
    Ale może masz co innego na myśli?

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


  • 4. Data: 2015-08-31 23:07:22
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: "AK" <n...@n...com>

    Użytkownik "Tomek Kańka" <t...@t...eu.org> napisał:

    >> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
    >> odkryć, że "pali" się np. czterdziesty ósmy?

    x & (1 << (48 - 1))

    AK


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


  • 5. Data: 2015-08-31 23:21:18
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: Tomek Kańka <t...@t...eu.org>

    szemrany <s...@o...off> napisał(a)
    > On Mon, 31 Aug 2015 20:39:28 +0000 (UTC), Tomek Kańka wrote:
    >
    >>> 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?
    >>
    >> A to nie jest "premature optymzation":)?
    >
    > Raczej nie, to część struktury używanej wielowątkowo i często.
    >
    >>> Może jakieś operacje arytmetyczne?
    >>
    >> Jeśłi to tylko jeden bit, to szukaj binarnie.
    >
    > Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
    > elementów w tablicy niż tylko 0 i 1.


    Jeśli zapalony jest tylko 1 bit, to wyszukujemy binarnie (w sensie
    dzielenia przedziału na połówki). zaczynamy od 2^32 i sprawdzamy, czy
    liczba jest wieksza/mniejsza. Na tej podstawie
    zawężamy przedział. Zapalony bit znajdziemy w 6 krokach.

    --
    Tomek


  • 6. Data: 2015-08-31 23:34:07
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: szemrany <s...@o...off>

    On Mon, 31 Aug 2015 23:07:22 +0200, AK wrote:

    >>> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
    >>> odkryć, że "pali" się np. czterdziesty ósmy?
    >
    > x & (1 << (48 - 1))

    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.

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


  • 7. Data: 2015-08-31 23:37:20
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: szemrany <s...@o...off>

    On Mon, 31 Aug 2015 21:21:18 +0000 (UTC), Tomek Kańka wrote:

    >> Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
    >> elementów w tablicy niż tylko 0 i 1.
    >
    > Jeśli zapalony jest tylko 1 bit, to wyszukujemy binarnie (w sensie
    > dzielenia przedziału na połówki). zaczynamy od 2^32 i sprawdzamy, czy
    > liczba jest wieksza/mniejsza. Na tej podstawie
    > zawężamy przedział. Zapalony bit znajdziemy w 6 krokach.

    No właśnie nie jest tylko jeden, lecz zazwyczaj więcej. Ta liczba 64 bitowa
    to tablica bitów/flag i chce znaleźć pierwszy, dowolny ustawiony bit.

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


  • 8. Data: 2015-08-31 23:40:58
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: bartekltg <b...@g...com>

    W dniu poniedziałek, 31 sierpnia 2015 22:49:24 UTC+2 użytkownik szemrany napisał:
    > On Mon, 31 Aug 2015 20:39:28 +0000 (UTC), Tomek Kańka wrote:
    >
    > >> 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?
    > >
    > > A to nie jest "premature optymzation":)?
    >
    > Raczej nie, to część struktury używanej wielowątkowo i często.
    >
    > >> Może jakieś operacje arytmetyczne?
    > >
    > > Jeśłi to tylko jeden bit, to szukaj binarnie.
    >
    > Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
    > elementów w tablicy niż tylko 0 i 1.

    A to czemu?
    Wyszukiwani binarne oznacza tu tyle, że sprawdzasz
    na raz połowę bitów.
    Tu masz przykład takiego wyszukiwania
    https://graphics.stanford.edu/~seander/bithacks.html
    #IntegerLog
    wyszukuje pierwszy zapalony bit. Obok jest parę innych.

    Masz też wbudowaną funckję __builtin_clz
    (w innym kompilatorze będzie się nazywałą inaczej).

    Jeśli zapalony jest tylko jeden bit, możesz odjać
    jedynkę i policzyć bity, lub...
    wziąć modulo 37 (tylko dla 32 bitowych) lub 67.

    <matma> grupa multiplikatywna liczb modulo 37 i 67 jest
    generowana przez 2<matma>
    wiąc 2^n % 67 będą różnymi małymi liczbami.
    Teraz potrzebna tylko mała tablica odszyfrowująca;-)

    pzdr
    bartekltg


  • 9. Data: 2015-09-01 08:03:15
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: voy <v...@M...pl>

    W dniu 2015-08-31 o 21:58, szemrany pisze:
    > 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?
    >

    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:

    BYTE GetBitCount( UINT uiBits )
    {
    BYTE byCnt = 0;
    while( uiBits )
    {
    ++byCnt;

    uiBits &= (uiBits - 1);
    }

    return byCnt;
    }


    Pozdr :)


  • 10. Data: 2015-09-01 10:31:07
    Temat: Re: Szybkie szukanie ustawionego bitu
    Od: szemrany <s...@o...off>

    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.

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

strony : [ 1 ] . 2 . 3


Szukaj w grupach

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: