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