Rozdział 10. Poszukiwanie szybszych metod zliczania bitów w stanie wysokim

Henry S. Warren, Jr.

PODSTAWOWYM I POZORNIE PROSTYM ALGORYTMEM KOMPUTEROWYM jest zliczanie bitów ustawionych na 1 (ang. population count lub sideways sum). Algorytm ten sprawdza liczbę bitów w słowie komputerowym, które mają ustawiony wysoki stan. Funkcja zliczania bitów o stanie logicznym 1 ma wiele zastosowań — od prostych po bardzo wyrafinowane[39]. Jeśli na przykład zbiory są reprezentowane przez łańcuchy bitów, funkcja ta zwróci rozmiar zbioru. Może też służyć do generowania losowych liczb całkowitych o rozkładzie dwumianowym. Te i inne zastosowania zostały opisane w końcowej części niniejszego rozdziału.

Mimo że zastosowania tej operacji nie są bardzo popularne, wiele ...

Get Piękny kod. Tajemnice mistrzów programowania now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.