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