8 bitów reprezentujących liczbę 7 wygląda następująco:
00000111
Ustawione są trzy bity.
Jakie są algorytmy do określania liczby ustawionych bitów w 32-bitowej liczbie całkowitej?
algorithm
binary
bit-manipulation
hammingweight
iec10967
Matt Howells
źródło
źródło
Odpowiedzi:
Jest to znane jako „ Hamming Weight ”, „popcount” lub „sideside add”.
Algorytm „najlepszego” naprawdę zależy od tego, na którym procesorze się znajdujesz i jaki jest wzorzec użytkowania.
Niektóre procesory mają wbudowaną pojedynczą instrukcję, a inne mają instrukcje równoległe, które działają na wektory bitowe. Instrukcje równoległe (takie jak x86
popcnt
, na procesorach, na których są obsługiwane) prawie na pewno będą najszybsze. Niektóre inne architektury mogą mieć powolną instrukcję zaimplementowaną za pomocą pętli mikrokodowanej, która testuje bit na cykl ( wymagane cytowanie ).Wstępnie wypełniona metoda wyszukiwania tabel może być bardzo szybka, jeśli procesor ma dużą pamięć podręczną i / lub wykonujesz wiele instrukcji w ciasnej pętli. Może to jednak ucierpieć z powodu kosztu „braku pamięci podręcznej”, gdy procesor musi pobrać część tabeli z pamięci głównej. (Poszukaj każdego bajtu osobno, aby utrzymać mały stół).
Jeśli wiesz, że twoje bajty będą w większości zera lub przeważnie zera, to istnieją bardzo wydajne algorytmy dla tych scenariuszy.
Uważam, że bardzo dobrym algorytmem ogólnego przeznaczenia jest, znany jako „równoległy” lub „algorytm SWAR o zmiennej precyzji”. Wyraziłem to w pseudo-języku podobnym do C, może być konieczne dostosowanie go do określonego języka (np. Użycie uint32_t dla C ++ i >>> w Javie):
W przypadku JavaScript: wymuszanie na liczbę całkowitą w
|0
celu zwiększenia wydajności: zmień pierwszy wiersz nai = (i|0) - ((i >> 1) & 0x55555555);
Jest to najlepsze zachowanie w najgorszym przypadku spośród omawianych algorytmów, więc skutecznie poradzi sobie z każdym wzorcem użytkowania lub wartościami, które na niego rzucisz.
Jak działa ten bit SWAR:
Pierwszym krokiem jest zoptymalizowana wersja maskowania w celu odizolowania bitów nieparzystych / parzystych, przesunięcia w celu wyrównania ich i dodania. Skutecznie robi to 16 osobnych dodatków w 2-bitowych akumulatorach ( SWAR = SIMD w rejestrze ). Jak
(i & 0x55555555) + ((i>>1) & 0x55555555)
.Następny krok obejmuje nieparzyste / parzyste osiem z tych 16-bitowych 2-bitowych akumulatorów i dodaje ponownie, generując 8x 4-bitowe sumy. Tym razem
i - ...
optymalizacja nie jest możliwa, więc maskuje tylko przed / po zmianie. Używanie tej samej0x33...
stałej za każdym razem zamiast0xccc...
przed przesunięciem jest dobrą rzeczą podczas kompilacji dla ISA, które muszą konstruować 32-bitowe stałe oddzielnie w rejestrach.Ostatni krok zmiany i dodania
(i + (i >> 4)) & 0x0F0F0F0F
poszerza się do 4x 8-bitowych akumulatorów. Maskuje po dodaniu zamiast wcześniej, ponieważ maksymalna wartość w dowolnym 4-bitowym akumulatorze wynosi4
, jeśli wszystkie 4 bity odpowiednich bitów wejściowych zostały ustawione. 4 + 4 = 8, które nadal mieszczą się w 4 bitach, więc przenoszenie między elementami gryzącymi jest niemożliwei + (i >> 4)
.Jak dotąd jest to po prostu dość normalny SIMD wykorzystujący techniki SWAR z kilkoma sprytnymi optymalizacjami. Kontynuacja tego samego wzoru przez 2 kolejne kroki może zostać rozszerzona do 2x 16-bitowych, a następnie 1x 32-bitowych. Istnieje jednak bardziej wydajny sposób na maszynach z szybkim mnożeniem sprzętowym:
Kiedy mamy już mało „elementów”, mnożenie przez magiczną stałą może zsumować wszystkie elementy do górnego elementu . W tym przypadku elementy bajtowe. Mnożenie odbywa się poprzez przesunięcie w lewo i dodawanie, więc pomnożenie
x * 0x01010101
wyników wx + (x<<8) + (x<<16) + (x<<24)
. Nasze 8-bitowe elementy są wystarczająco szerokie (i zawierają wystarczająco małe liczby), aby nie powodować przeniesienia do tych 8 górnych bitów.Wersja 64-bitowa może wykonywać 8x 8-bitowe elementy w 64-bitowej liczbie całkowitej z mnożnikiem 0x0101010101010101 i wyodrębnić wysoki bajt za pomocą
>>56
. Więc nie wymaga żadnych dodatkowych kroków, tylko szersze stałe. Tego używa GCC__builtin_popcountll
w systemach x86, gdypopcnt
instrukcja sprzętowa nie jest włączona. Jeśli możesz użyć do tego wbudowanych lub wewnętrznych elementów, zrób to, aby dać kompilatorowi możliwość optymalizacji pod kątem celu.Z pełną kartą SIMD dla szerszych wektorów (np. Zliczanie całej tablicy)
Ten bitowy algorytm SWAR mógłby być równoległy do wykonania w wielu elementach wektorowych jednocześnie, zamiast w jednym rejestrze liczb całkowitych, w celu przyspieszenia procesorów z SIMD, ale bez użytecznej instrukcji popcount. (np. kod x86-64, który musi działać na dowolnym procesorze, nie tylko Nehalem lub nowszym).
Jednak najlepszym sposobem na użycie instrukcji wektorowych dla popcount jest zwykle użycie losowego zmieniania w celu przeszukiwania tabeli dla 4 bitów jednocześnie z każdym bajtem równolegle. (4 bity indeksują tablicę 16 wpisów przechowywaną w rejestrze wektorowym).
W procesorach Intela sprzętowa 64-bitowa instrukcja popcnt może przewyższyć implementację SSSE3
PSHUFB
-bit-równolegle o współczynnik 2, ale tylko wtedy, gdy kompilator dobrze to zrobi . W przeciwnym razie SSE może znacznie wyprzedzić. Nowsze wersje kompilatora są świadome problemu fałszywej zależności popcnt na platformie Intel .Bibliografia:
źródło
unsigned int
, aby łatwo pokazać, że jest wolny od jakichkolwiek komplikacji. Byłobyuint32_t
też bezpieczniej, ponieważ masz to, czego oczekujesz na wszystkich platformach?>>
jest zdefiniowany w implementacji dla wartości ujemnych. Argument należy zmienić (lub rzutować) naunsigned
, a ponieważ kod jest 32-bitowy, prawdopodobnie powinien być używanyuint32_t
.Weź również pod uwagę wbudowane funkcje kompilatorów.
Na przykład w kompilatorze GNU możesz po prostu użyć:
W najgorszym przypadku kompilator wygeneruje wywołanie funkcji. W najlepszym przypadku kompilator wyda instrukcję procesora, aby szybciej wykonać tę samą pracę.
Wewnętrzne funkcje GCC działają nawet na wielu platformach. Popcount stanie się głównym nurtem w architekturze x86, więc sensowne jest teraz, aby zacząć korzystać z wewnętrznych funkcji. Inne architektury mają popularność od lat.
Na x86 można powiedzieć kompilatorowi, że może przyjąć obsługę
popcnt
instrukcji z-mpopcnt
lub-msse4.2
włączyć instrukcje wektorowe, które zostały dodane w tej samej generacji. Zobacz opcje GCC x86 .-march=nehalem
(lub-march=
jakikolwiek inny procesor, który chcesz przyjąć i dostroić kod) może być dobrym wyborem. Uruchomienie wynikowego pliku binarnego na starszym procesorze spowoduje błąd nieprawidłowej instrukcji.Aby zoptymalizować pliki binarne dla komputera, na którym je zbudujesz, użyj
-march=native
(z gcc, clang lub ICC).MSVC zapewnia wewnętrzną
popcnt
instrukcję x86 , ale w przeciwieństwie do gcc, jest naprawdę wewnętrzną instrukcją sprzętową i wymaga wsparcia sprzętowego.Używanie
std::bitset<>::count()
zamiast wbudowanegoTeoretycznie każdy kompilator, który wie, jak efektywnie przeliczać docelowy procesor, powinien udostępnić tę funkcjonalność poprzez ISO C ++
std::bitset<>
. W praktyce lepiej byłoby w przypadku niektórych docelowych procesorów w przypadku hackowania bitów AND / shift / ADD.W przypadku architektur docelowych, w których popcount sprzętowy jest opcjonalnym rozszerzeniem (jak x86), nie wszystkie kompilatory mają takie,
std::bitset
które wykorzystują je, gdy są dostępne. Na przykład MSVC nie ma możliwości włączeniapopcnt
obsługi w czasie kompilacji i zawsze używa wyszukiwania tabeli , nawet z/Ox /arch:AVX
(co implikuje SSE4.2, chociaż technicznie istnieje osobny bit funkcjipopcnt
.)Ale przynajmniej dostajesz coś przenośnego, który działa wszędzie, a dzięki gcc / clang z odpowiednimi opcjami docelowymi, dostajesz popcount sprzętowy dla architektur, które go obsługują.
Zobacz asm z gcc, clang, icc i MSVC w eksploratorze kompilatorów Godbolt.
x86-64
gcc -O3 -std=gnu++11 -mpopcnt
emituje to:gcc -O3 -std=gnu++11
Emituje PowerPC64 (dlaint
wersji arg):To źródło nie jest specyficzne dla x86 lub GNU, ale dobrze się kompiluje tylko dla x86 z gcc / clang / icc.
Zauważ też, że awaria gcc dla architektur bez popcount z pojedynczą instrukcją to wyszukiwanie tabel w bajtach po czasie. Na przykład nie jest to cudowne dla ARM .
źródło
std::bitset::count
. po wstawieniu kompiluje się w jednym__builtin_popcount
wywołaniu.Moim zdaniem „najlepszym” rozwiązaniem jest to, które może odczytać inny programista (lub oryginalny programista dwa lata później) bez obszernych komentarzy. Możesz chcieć najszybszego lub najmądrzejszego rozwiązania, które niektórzy już dostarczyli, ale wolę czytelność niż spryt.
Jeśli chcesz zwiększyć szybkość (i zakładając, że dobrze ją dokumentujesz, aby pomóc swoim następcom), możesz skorzystać z wyszukiwania w tabeli:
Chociaż opierają się one na określonych rozmiarach typów danych, więc nie są tak przenośne. Ponieważ jednak wiele optymalizacji wydajności i tak nie jest przenośnych, może to nie stanowić problemu. Jeśli chcesz mieć przenośność, trzymam się czytelnego rozwiązania.
źródło
if ((value & 1) == 1) { count++; }
zcount += value & 1
?Od Hacker's Delight, str. 66, rysunek 5-2
Wykonuje się w ~ 20-tej instrukcji (zależnej od łuku), bez rozgałęzień.
Hacker's Delight jest zachwycający! Wysoce polecany.
źródło
Integer.bitCount(int)
wykorzystuje tę samą dokładną implementację.pop
zamiastpopulation_count
(lubpop_cnt
jeśli musisz mieć abreviation). @MarcoBolis Zakładam, że będzie to prawdą we wszystkich wersjach Javy, ale oficjalnie będzie to zależało od implementacji :)Myślę, że najszybszy sposób - bez użycia tabel odnośników i popcount - jest następujący. Liczy ustawione bity za pomocą zaledwie 12 operacji.
Działa, ponieważ można policzyć całkowitą liczbę ustawionych bitów, dzieląc na dwie połowy, licząc liczbę ustawionych bitów w obu połowach, a następnie dodając je. Znany również jako
Divide and Conquer
paradygmat. Przejdźmy do szczegółów ...Liczba bitów w dwóch bitów może być
0b00
,0b01
lub0b10
. Spróbujmy to rozpracować na 2 bitach ..Oto, co było wymagane: ostatnia kolumna pokazuje liczbę ustawionych bitów w każdej parze bitów. Jeśli numer dwa bit jest
>= 2 (0b10)
następnieand
produkuje0b01
, produkuje inny0b00
.To stwierdzenie powinno być łatwe do zrozumienia. Po pierwszej operacji mamy liczbę ustawionych bitów co dwa bity, teraz sumujemy tę liczbę co 4 bity.
Następnie podsumowujemy powyższy wynik, dając nam całkowitą liczbę ustawionych bitów w 4 bitach. Ostatnie zdanie jest najtrudniejsze.
Rozbijmy to dalej ...
Jest podobny do drugiego stwierdzenia; zamiast tego liczymy ustawione bity w grupach po 4. Wiemy - dzięki naszym wcześniejszym operacjom - że każda skórka ma w sobie liczbę ustawionych bitów. Spójrzmy na przykład. Załóżmy, że mamy bajt
0b01000010
. Oznacza to, że pierwsza końcówka ma zestaw 4 bitów, a druga ma zestaw 2 bitów. Teraz dodajemy te skubki razem.Daje nam liczbę ustawionych bitów w bajcie, w pierwszej części,
0b01100010
i dlatego maskujemy ostatnie cztery bajty wszystkich bajtów w liczbie (odrzucając je).Teraz każdy bajt zawiera liczbę ustawionych bitów. Musimy dodać je wszystkie razem. Sztuką jest pomnożenie wyniku,
0b10101010
który ma interesującą właściwość. Jeśli nasz numer ma cztery bajty,A B C D
spowoduje to utworzenie nowej liczby z tymi bajtamiA+B+C+D B+C+D C+D D
. Liczba 4-bajtowa może mieć ustawione maksymalnie 32 bity, które można przedstawić jako0b00100000
.Teraz potrzebujemy tylko pierwszego bajtu, który ma sumę wszystkich ustawionych bitów we wszystkich bajtach, i otrzymujemy to
>> 24
. Ten algorytm został zaprojektowany dla32 bit
słów, ale można go łatwo modyfikować dla64 bit
słów.źródło
c =
chodzi Wygląda na to, że należy go wyeliminować. Ponadto zasugeruj dodatkowy zestaw parenów A ”(((v + (v >> 4)) i 0xF0F0F0F) * 0x1010101) >> 24”, aby uniknąć niektórych klasycznych ostrzeżeń.popcount(int v)
i dlapopcount(unsigned v)
. Dla przenośności, rozważpopcount(uint32_t v)
itp. Naprawdę podoba się część * 0x1010101.return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
więc nie musimy liczyć liter, aby zobaczyć, co faktycznie robisz (ponieważ odrzuciłeś pierwszy0
, przypadkowo myślałem, że użyłeś niewłaściwego (odwróconego) wzoru bitowego jako maski - dopóki nie zauważyłem, że jest tylko 7 liter, a nie 8).Nudziłem się i zaplanowałem miliard iteracji trzech podejść. Kompilator to gcc -O3. Procesor to wszystko, co wkładają w Macbooka pierwszej generacji.
Najszybszy jest po 3,7 sekundy:
Drugie miejsce zajmuje ten sam kod, ale wyszukuje 4 bajty zamiast 2 półsłów. Zajęło to około 5,5 sekundy.
Trzecie miejsce zajęło kręcące się nieco „sideways add” podejście, które zajęło 8,6 sekundy.
Czwarte miejsce zajęło __builtin_popcount () GCC w haniebnej 11 sekundzie.
Liczenie pojedynczych kroków było o wiele wolniejsze i nudziło mnie oczekiwanie na zakończenie.
Jeśli więc zależy Ci przede wszystkim na wydajności, zastosuj pierwsze podejście. Jeśli zależy ci, ale nie wystarcza na wydanie 64 KB pamięci RAM, zastosuj drugie podejście. W przeciwnym razie zastosuj czytelne (ale powolne) podejście do jednego bitu na raz.
Trudno wymyślić sytuację, w której chciałbyś zastosować podejście polegające na kręceniu bitów.
Edycja: podobne wyniki tutaj .
źródło
Jeśli akurat używasz Javy,
Integer.bitCount
zrobi to wbudowana metoda .źródło
Pozwól mi wyjaśnić ten algorytm.
Algorytm ten oparty jest na algorytmie Dziel i rządź. Załóżmy, że istnieje 8-bitowa liczba całkowita 213 (11010101 w systemie binarnym), algorytm działa w ten sposób (za każdym razem łączymy dwa sąsiednie bloki):
źródło
To jedno z tych pytań, w którym pomaga poznać Twoją mikroarchitekturę. Właśnie zsynchronizowałem dwa warianty w gcc 4.3.3 skompilowanym z -O3 przy użyciu wstawek C ++ w celu wyeliminowania narzutu wywołania funkcji, miliarda iteracji, zachowując sumę wszystkich obliczeń, aby upewnić się, że kompilator nie usunie niczego ważnego, używając rdtsc do pomiaru czasu ( cykl zegara precyzyjny).
Niezmodyfikowany zachwyt hakera zajął 12,2 gigacyklu. Moja równoległa wersja (licząca dwa razy więcej bitów) działa w 13,0 gigacyklach. Łącznie 10,5 s upłynęło dla obu razem na 2,4 GHz Core Duo. 25 gigocykli = nieco ponad 10 sekund przy tej częstotliwości zegara, więc jestem pewien, że moje czasy są prawidłowe.
Ma to związek z łańcuchami zależności instrukcji, które są bardzo złe dla tego algorytmu. Mogłem prawie dwukrotnie podwoić prędkość, używając pary rejestrów 64-bitowych. W rzeczywistości, gdybym był sprytny i dodał wcześniej x + ya, mógłbym się ogolić. Wersja 64-bitowa z kilkoma drobnymi poprawkami wyszedłaby nawet, ale znów liczy dwa razy więcej bitów.
Ze 128-bitowymi rejestrami SIMD jest to jeszcze jeden czynnik dwa, a zestawy instrukcji SSE często mają również sprytne skróty.
Nie ma powodu, aby kod był szczególnie przejrzysty. Interfejs jest prosty, do algorytmu można się odwoływać on-line w wielu miejscach i jest on podatny na kompleksowy test jednostkowy. Programista, który się na nią natknie, może nawet się czegoś nauczyć. Te operacje bitowe są niezwykle naturalne na poziomie maszyny.
OK, postanowiłem przetestować ulepszoną wersję 64-bitową. Dla tego jednego rozmiaru (długi bez znaku) == 8
To wygląda dobrze (choć nie testuję dokładnie). Teraz czasy wyszły na 10,70 gigacyklów / 14,1 gigacyklów. Ta późniejsza liczba zsumowała 128 miliardów bitów i odpowiada 5,9 s, jakie upłynęły na tym komputerze. Wersja nierównoległa trochę przyspiesza, ponieważ pracuję w trybie 64-bitowym i lubi rejestry 64-bitowe nieco lepiej niż rejestry 32-bitowe.
Zobaczmy, czy jest tu trochę więcej rurociągów OOO. To było trochę bardziej zaangażowane, więc faktycznie trochę przetestowałem. Każdy termin sam w sobie wynosi 64, a łączna suma 256.
Przez chwilę byłem podekscytowany, ale okazuje się, że gcc gra sztuczki w trybie -O3, chociaż w niektórych testach nie używam słowa kluczowego inline. Kiedy pozwalam gcc grać lewami, miliard wywołań pop4 () wymaga 12,56 gigacyklów, ale ustaliłem, że to składanie argumentów jako wyrażeń stałych. Bardziej realistyczna liczba wydaje się wynosić 19,6 gc dla kolejnego przyspieszenia o 30%. Moja pętla testowa wygląda teraz tak, upewniając się, że każdy argument jest wystarczająco inny, aby powstrzymać gcc od trików.
Upłynęło 256 miliardów bitów zsumowanych w 8,17s. Działa do 1,02 dla 32 milionów bitów, jak porównano w 16-bitowej tabeli wyszukiwania. Nie można porównywać bezpośrednio, ponieważ druga ławka nie podaje prędkości zegara, ale wygląda na to, że spoliczkowałem smark z edycji tabeli 64 KB, co jest tragicznym użyciem pamięci podręcznej L1.
Aktualizacja: postanowiłem zrobić to, co oczywiste i stworzyć pop6 (), dodając cztery kolejne zduplikowane linie. Przyszedł do 22,8 gc, upłynęło 384 miliardy bitów zsumowanych w 9,5 s. Jest więc kolejne 20% teraz przy 800 ms dla 32 miliardów bitów.
źródło
Dlaczego nie podzielić iteracyjnie przez 2?
Zgadzam się, że nie jest to najszybszy, ale „najlepszy” jest nieco niejednoznaczny. Twierdziłbym jednak, że „najlepsze” powinno mieć element jasności
źródło
Kręcenie bitów Hacker's Delight staje się o wiele wyraźniejsze, gdy zapisujesz wzory bitów.
Pierwszy krok dodaje parzyste bity do bitów nieparzystych, tworząc sumę bitów w każdym z dwóch. Pozostałe kroki dodają porcje wysokiego rzędu do porcji niskiego rzędu, podwajając rozmiar porcji do samego końca, aż do ostatecznego obliczenia zajmującego całą int.
źródło
Aby uzyskać szczęśliwe medium między tabelą wyszukiwania 2 32 i iteracją każdego bitu z osobna:
Od http://ctips.pbwiki.com/CountBits
źródło
Można to zrobić w
O(k)
, gdziek
jest ustawiona liczba bitów.źródło
n &= (n-1)
formy.To nie jest najszybsze ani najlepsze rozwiązanie, ale znalazłem na swojej drodze to samo pytanie i zacząłem myśleć i myśleć. w końcu zdałem sobie sprawę, że można to zrobić w ten sposób, jeśli rozwiążesz problem od strony matematycznej i narysujesz wykres, a następnie okaże się, że jest to funkcja, która ma pewną część okresową, a następnie uświadomisz sobie różnicę między okresami ... więc proszę bardzo:
źródło
def f(i, d={0:lambda:0, 1:lambda:1, 2:lambda:1, 3:lambda:2}): return d.get(i, lambda: f(i//4) + f(i%4))()
Funkcja, której szukasz, jest często nazywana „sumą boczną” lub „liczbą ludności” liczby binarnej. Knuth omawia to w wersji sprzed Fascicle 1A, str. 11-12 (chociaż w tomie 2, 4.6.3- (7) było krótkie odniesienie).
Locus classicus jest artykuł Petera Wegenera "techniką licznikowe w Binary Komputer", od Communications of the ACM , tom 3 (1960) Numer 5, strona 322 . Podaje tam dwa różne algorytmy, jeden zoptymalizowany dla liczb, które mają być „rzadkie” (tj. Mają małą liczbę) i jeden dla przeciwnego przypadku.
źródło
źródło
Kilka otwartych pytań: -
możemy zmodyfikować algo, aby obsługiwał liczbę ujemną w następujący sposób:
teraz, aby rozwiązać drugi problem, możemy napisać algo w stylu: -
dla pełnego odniesienia patrz:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
źródło
Myślę, że metoda Briana Kernighana też się przyda ... Przechodzi tyle iteracji, ile jest ustawionych bitów. Jeśli więc mamy 32-bitowe słowo z ustawionym tylko wysokim bitem, przejdzie ono tylko raz przez pętlę.
źródło
Korzystam z poniższego kodu, który jest bardziej intuicyjny.
Logika: n & (n-1) resetuje ostatni ustawiony bit n.
PS: Wiem, że to nie jest rozwiązanie O (1), ale ciekawe rozwiązanie.
źródło
O(ONE-BITS)
. Rzeczywiście jest to O (1), ponieważ jest co najwyżej 32 jednobitowe.Co masz na myśli mówiąc „Najlepszy algorytm”? Skrócony kod czy kod na czczo? Twój kod wygląda bardzo elegancko i ma stały czas wykonania. Kod jest również bardzo krótki.
Ale jeśli szybkość jest głównym czynnikiem, a nie rozmiar kodu, myślę, że następujące może być szybsze:
Myślę, że nie będzie to szybsze dla wartości 64-bitowej, ale wartość 32-bitowa może być szybsza.
źródło
Napisałem szybkie makro bitcount dla maszyn RISC około 1990 roku. Nie używa zaawansowanej arytmetyki (mnożenie, dzielenie,%), pobierania pamięci (zbyt wolno), rozgałęzień (zbyt wolno), ale zakłada, że procesor ma 32-bitowy przesuwnik lufy (innymi słowy, >> 1 i >> 32 wykonują taką samą liczbę cykli). Zakłada się, że małe stałe (takie jak 6, 12, 24) nie kosztują nic do załadowania do rejestrów lub są przechowywane w tymczasach i wielokrotnie używane.
Przy tych założeniach zlicza 32 bity w około 16 cyklach / instrukcjach na większości maszyn RISC. Zauważ, że 15 instrukcji / cykli jest zbliżonych do dolnej granicy liczby cykli lub instrukcji, ponieważ wydaje się, że potrzeba co najmniej 3 instrukcji (maska, przesunięcie, operator), aby zmniejszyć liczbę dodatków o połowę, więc log_2 (32) = 5, 5 x 3 = 15 instrukcji jest quasi-niższe.
Oto sekret pierwszego i najbardziej złożonego kroku:
więc jeśli wezmę pierwszą kolumnę (A) powyżej, przesunę ją o 1 bit w prawo i odejmę od AB, otrzymam wynik (CD). Rozszerzenie do 3 bitów jest podobne; możesz to sprawdzić za pomocą 8-rzędowego stołu boolowskiego, takiego jak mój powyżej, jeśli chcesz.
źródło
jeśli używasz C ++, inną opcją jest użycie metaprogramowania szablonu:
użycie byłoby:
możesz oczywiście dalej rozwinąć ten szablon, aby używać różnych typów (nawet automatycznego wykrywania rozmiaru bitów), ale dla uproszczenia wyjaśniłem.
edit: zapomniałem wspomnieć, że jest to dobre, ponieważ powinno działać w dowolnym kompilatorze C ++ i po prostu rozwija pętlę dla Ciebie, jeśli do liczenia bitów używana jest stała wartość (innymi słowy, jestem prawie pewien, że jest to najszybsza metoda ogólna znajdziesz)
źródło
constexpr
.Szczególnie podoba mi się ten przykład z pliku fortuny:
Najbardziej mi się podoba, ponieważ jest taki ładny!
źródło
Java JDK1.5
Integer.bitCount (n);
gdzie n jest liczbą, której 1 należy liczyć.
sprawdź także
źródło
Znalazłem implementację zliczania bitów w tablicy za pomocą instrukcji SIMD (SSSE3 i AVX2). Ma 2-2,5 razy lepszą wydajność niż w przypadku użycia funkcji wewnętrznej __popcnt64.
Wersja SSSE3:
Wersja AVX2:
źródło
Zawsze używam tego w programowaniu konkurencyjnym i jest łatwy do napisania i wydajny:
źródło
Istnieje wiele algorytmów do zliczania ustawionych bitów; ale myślę, że najlepszy jest ten szybszy! Możesz zobaczyć szczegółowe informacje na tej stronie:
Bit Twiddling Hacks
Proponuję ten:
Zliczanie bitów ustawionych na 14, 24 lub 32-bitowe słowa przy użyciu instrukcji 64-bitowych
Ta metoda wymaga wydajnego 64-bitowego procesora z szybkim podziałem modułu. Pierwsza opcja wymaga tylko 3 operacji; druga opcja zajmuje 10; a trzecia opcja zajmuje 15.
źródło
Szybkie rozwiązanie C # przy użyciu wstępnie obliczonej tabeli liczby bitów z rozgałęzieniem na wielkości wejściowej.
źródło
(0xe994 >>(k*2))&3
, bez dostępu do pamięci ...Oto przenośny moduł (ANSI-C), który może porównywać każdy twój algorytm z dowolną architekturą.
Twój procesor ma 9 bitów? Żaden problem :-) W tej chwili implementuje 2 algorytmy, algorytm K&R i bajtową tablicę odnośników. Tabela przeglądowa jest średnio 3 razy szybsza niż algorytm K&R. Jeśli ktoś wymyśli sposób, aby uczynić algorytm „Hacker's Delight” przenośnym, możesz go dodać.
.
źródło
co możesz zrobić to
logika tego polega na tym, że bity n-1 są odwrócone od ustawionego najbardziej na prawo bitu n. jeśli n = 6, tj. 110, to 5 oznacza 101, bity są odwrócone od najbardziej ustawionego po prawej bitu n. więc jeśli my i ci dwaj, zrobimy najbardziej prawy bit 0 w każdej iteracji i zawsze przejdziemy do następnego najbardziej ustawionego bitu ustawionego, dlatego licząc ustawiony bit. Najgorsza złożoność czasu będzie O (logn), gdy każdy bit zostanie ustawiony.
źródło