Jak policzyć liczbę ustawionych bitów w 32-bitowej liczbie całkowitej?

868

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?

Matt Howells
źródło
101
To jest waga Hamminga BTW.
Purfideas
11
Jaka jest do tego rzeczywista aplikacja? (Nie należy tego traktować jako krytyki - jestem po prostu ciekawy.)
jonmorgan
8
Obliczanie bitu parzystości (patrz), który był używany jako proste wykrywanie błędów w komunikacji.
Dialecticus,
8
@Dialecticus, obliczanie bitu parzystości jest tańsze niż obliczanie masy Hamminga
finnw
15
@spookyjon Powiedzmy, że masz wykres reprezentowany jako macierz przylegania, która jest zasadniczo nieco ustawiona. Jeśli chcesz obliczyć liczbę krawędzi wierzchołka, sprowadza się do obliczenia masy Hamminga jednego rzędu w zestawie bitów.
fuz 10.1011

Odpowiedzi:

850

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):

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

W przypadku JavaScript: wymuszanie na liczbę całkowitą w |0celu 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:

i = i - ((i >> 1) & 0x55555555);

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 samej 0x33...stałej za każdym razem zamiast 0xccc...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)) & 0x0F0F0F0Fposzerza się do 4x 8-bitowych akumulatorów. Maskuje po dodaniu zamiast wcześniej, ponieważ maksymalna wartość w dowolnym 4-bitowym akumulatorze wynosi 4, 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żliwe i + (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 * 0x01010101wyników w x + (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_popcountllw systemach x86, gdy popcntinstrukcja 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:

Matt Howells
źródło
87
ha! uwielbiam funkcję NumberOfSetBits (), ale powodzenia w przejrzeniu kodu. :-)
Jason S
37
Może powinien użyć unsigned int, aby łatwo pokazać, że jest wolny od jakichkolwiek komplikacji. Byłoby uint32_tteż bezpieczniej, ponieważ masz to, czego oczekujesz na wszystkich platformach?
Craig McQueen,
35
@nonnb: W rzeczywistości, jak napisano, kod jest błędny i wymaga konserwacji. >>jest zdefiniowany w implementacji dla wartości ujemnych. Argument należy zmienić (lub rzutować) na unsigned, a ponieważ kod jest 32-bitowy, prawdopodobnie powinien być używany uint32_t.
R .. GitHub ZATRZYMAJ LÓD
6
To nie jest naprawdę magia. Dodaje zestawy bitów, ale robi to z kilkoma sprytnymi optymalizacjami. Link do Wikipedii podany w odpowiedzi dobrze wyjaśnia, co się dzieje, ale przejdę do kolejnej linii. 1) Policz liczbę bitów w każdej parze bitów, umieszczając tę ​​liczbę w tej parze bitów (będziesz miał 00, 01 lub 10); „sprytnym” bitem jest tutaj odejmowanie, które pozwala uniknąć jednej maski. 2) Dodaj pary tych par bitów do odpowiadających im skórek; nic mądrego tutaj, ale każdy skubek będzie miał teraz wartość 0-4. (kont.)
dash-tom-bang
8
Inna uwaga, dotyczy to rejestrów 64 i 128 bitowych, po prostu odpowiednio rozszerzając stałe. Co ciekawe (dla mnie) te stałe to również ~ 0/3, 5, 17 i 255; poprzednie trzy to 2 ^ n + 1. Wszystko to ma sens, im więcej się na niego gapisz i zastanawiasz się pod prysznicem. :)
dash-tom-bang
214

Weź również pod uwagę wbudowane funkcje kompilatorów.

Na przykład w kompilatorze GNU możesz po prostu użyć:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

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ę popcntinstrukcji z -mpopcntlub -msse4.2włą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ą popcntinstrukcję 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 wbudowanego

Teoretycznie 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::bitsetktóre wykorzystują je, gdy są dostępne. Na przykład MSVC nie ma możliwości włączenia popcntobsługi w czasie kompilacji i zawsze używa wyszukiwania tabeli , nawet z /Ox /arch:AVX(co implikuje SSE4.2, chociaż technicznie istnieje osobny bit funkcji popcnt.)

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ą.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Zobacz asm z gcc, clang, icc i MSVC w eksploratorze kompilatorów Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcntemituje to:

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret
unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax
    ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

gcc -O3 -std=gnu++11Emituje PowerPC64 (dla intwersji arg):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

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 .

Peter Cordes
źródło
5
Zgadzam się, że jest to ogólnie dobra praktyka, ale na XCode / OSX / Intel odkryłem, że generuje on wolniejszy kod niż większość podanych tutaj sugestii. Zobacz moją odpowiedź, aby poznać szczegóły.
5
Intel i5 / i7 ma instrukcję POPCNT SSE4, która to robi, używając rejestrów ogólnego przeznaczenia. GCC w moim systemie nie emituje tej instrukcji przy użyciu tej wewnętrznej funkcji, chyba z powodu braku opcji -march = nehalem.
matja
3
@matja, mój GCC 4.4.1 emituje instrukcję popcnt, jeśli skompiluję z -msse4.2
Nils Pipenbrinck
74
użyj c ++ std::bitset::count. po wstawieniu kompiluje się w jednym __builtin_popcountwywołaniu.
deft_code,
1
@nlucaroni Cóż, tak. Czasy się zmieniają. Napisałem tę odpowiedź w 2008 roku. Obecnie mamy natywną liczbę popcount, a funkcja wewnętrzna skompiluje się do pojedynczej instrukcji asemblera, jeśli platforma na to pozwoli.
Nils Pipenbrinck
184

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.

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

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:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

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.

paxdiablo
źródło
21
Zamiast dzielić przez 2 i komentować go jako „bity shift ...”, powinieneś po prostu użyć operatora shift (>>) i pominąć komentarz.
indyw.
9
czy nie byłoby bardziej sensowne, aby zastąpić if ((value & 1) == 1) { count++; }z count += value & 1?
Ponkadoodle,
21
Nie, najlepsze rozwiązanie nie jest w tym przypadku najbardziej czytelne. Tutaj najlepszy algorytm jest najszybszy.
NikiC,
21
To całkowicie twoja opinia, @nikic, chociaż oczywiście możesz mnie zagłosować. W pytaniu nie było wzmianki o tym, jak określić „najlepiej”, słowa „wydajność” lub „szybko” nigdzie nie widać. Dlatego zdecydowałem się na czytelny.
paxdiablo
3
Czytam tę odpowiedź 3 lata później i uważam ją za najlepszą odpowiedź, ponieważ jest czytelna i ma więcej komentarzy. Kropka.
waka-waka-waka
98

Od Hacker's Delight, str. 66, rysunek 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

Wykonuje się w ~ 20-tej instrukcji (zależnej od łuku), bez rozgałęzień.

Hacker's Delight jest zachwycający! Wysoce polecany.

Kevin Little
źródło
8
Metoda Java Integer.bitCount(int)wykorzystuje tę samą dokładną implementację.
Marco Bolis,
Mamy trochę problemów z tym - jak by to zmieniło, gdybyśmy dbali tylko o 16-bitowe wartości zamiast 32-bitowych?
Jeremy Blum
Być może rozkosz hakerów jest zachwycająca, ale dobrze bym kopnął każdego, kto dzwoni do tego popzamiast population_count(lub pop_cntjeś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 :)
Maarten Bodewes
I to nie wymaga mnożenia, jak kod w zaakceptowanej odpowiedzi.
Alex
Zauważ, że przy generalizacji do wersji 64-bitowej występuje problem. Wynik nie może wynosić 64 z powodu maski.
Albert van der Horst
76

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.

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

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 Conquerparadygmat. Przejdźmy do szczegółów ...

v = v - ((v >> 1) & 0x55555555); 

Liczba bitów w dwóch bitów może być 0b00, 0b01lub 0b10. Spróbujmy to rozpracować na 2 bitach ..

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

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ępnie andprodukuje 0b01, produkuje inny 0b00.

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

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.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

Następnie podsumowujemy powyższy wynik, dając nam całkowitą liczbę ustawionych bitów w 4 bitach. Ostatnie zdanie jest najtrudniejsze.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Rozbijmy to dalej ...

v + (v >> 4)

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.

0b01000010 + 0b01000000

Daje nam liczbę ustawionych bitów w bajcie, w pierwszej części, 0b01100010i dlatego maskujemy ostatnie cztery bajty wszystkich bajtów w liczbie (odrzucając je).

0b01100010 & 0xF0 = 0b01100000

Teraz każdy bajt zawiera liczbę ustawionych bitów. Musimy dodać je wszystkie razem. Sztuką jest pomnożenie wyniku, 0b10101010który ma interesującą właściwość. Jeśli nasz numer ma cztery bajty, A B C Dspowoduje to utworzenie nowej liczby z tymi bajtami A+B+C+D B+C+D C+D D. Liczba 4-bajtowa może mieć ustawione maksymalnie 32 bity, które można przedstawić jako 0b00100000.

Teraz potrzebujemy tylko pierwszego bajtu, który ma sumę wszystkich ustawionych bitów we wszystkich bajtach, i otrzymujemy to >> 24. Ten algorytm został zaprojektowany dla 32 bitsłów, ale można go łatwo modyfikować dla 64 bitsłów.

vidit
źródło
O co 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ń.
chux - Przywróć Monikę
4
Ważną cechą jest to, że ta 32-bitowa procedura działa zarówno dla, jak popcount(int v)i dla popcount(unsigned v). Dla przenośności, rozważ popcount(uint32_t v)itp. Naprawdę podoba się część * 0x1010101.
chux - Przywróć Monikę
sos ? (książka, link, nazwiska inwertorów itp.) BARDZO mile widziane. Ponieważ wtedy możemy wkleić to w naszych bazach kodów z komentarzem do źródła.
v.oddou
1
Myślę, że dla większej przejrzystości ostatni wiersz powinien być zapisany jako: return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;więc nie musimy liczyć liter, aby zobaczyć, co faktycznie robisz (ponieważ odrzuciłeś pierwszy 0, 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).
emem
To mnożenie przez 0x01010101 może być powolne, w zależności od procesora. Na przykład w moim starym PowerBooku G4 1 mnożenie było tak powolne jak 4 uzupełnienia (nie tak złe jak podział, gdzie 1 podział był tak powolny jak 23 uzupełnienia).
George Koehler
54

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:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

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 .

Mike F.
źródło
49
@ Mike, podejście oparte na tabeli jest nie do pobicia, jeśli tabela znajduje się w pamięci podręcznej. Dzieje się tak w mikro-testach porównawczych (np. Wykonuj miliony testów w ciasnej pętli). Jednak brak pamięci podręcznej zajmuje około 200 cykli, a nawet najbardziej naiwny popcount będzie tutaj szybszy. Zawsze zależy od zastosowania.
Nils Pipenbrinck,
10
Jeśli nie wywołujesz tej procedury kilka milionów razy w ciasnej pętli, to nie masz powodu, aby w ogóle dbać o jej wydajność i równie dobrze możesz zastosować naiwne, ale czytelne podejście, ponieważ utrata wydajności będzie znikoma. I FWIW, 8-bitowy LUT staje się gorący w pamięci podręcznej w ciągu 10-20 połączeń.
6
Nie wydaje mi się, żeby tak trudno było wyobrazić sobie sytuację, w której jest to wywołanie typu liść wykonane metodą - w rzeczywistości ciężkie podnoszenie - w Twojej aplikacji. W zależności od tego, co się dzieje (i wątków), mniejsza wersja może wygrać. Napisano wiele algorytmów, które pokonują swoich rówieśników ze względu na lepszą lokalizację odniesienia. Dlaczego nie to też?
Jason
Wypróbuj to z clang, jest znacznie mądrzejszy przy implementacji wbudowanych.
Matt Joiner,
3
GCC nie wyemituje instrukcji popcont, chyba że zostanie wywołany z -msse4.2, wielkość liter jest szybsza niż dodawanie z boku.
lvella,
54

Jeśli akurat używasz Javy, Integer.bitCountzrobi to wbudowana metoda .

Noether
źródło
Kiedy firma Sun udostępniła różne interfejsy API, musi używać pewnej logiki w tle, prawda?
Vallabh Patade
2
Na marginesie, implementacja Javy wykorzystuje ten sam algorytm wskazany przez Kevina Little .
Marco Bolis,
2
Pomijając implementację, jest to prawdopodobnie najostrzejsza wiadomość dla deweloperów utrzymujących Twój kod po tobie (lub gdy wrócisz do niego 6 miesięcy później)
divillysausages
31
unsigned int count_bit(unsigned int x)
{
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
  return x;
}

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):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+
abcdabcd987
źródło
7
Algorytm ten jest wersją opublikowaną przez Matta Howellsa, zanim został zoptymalizowany pod kątem tego, że stał się nieczytelny.
Lefteris E,
29

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).

inline int pop2 (unsigned x, unsigned y)
{
    x = x - ((x >> 1) i 0x55555555);
    y = y - ((y >> 1) i 0x55555555);
    x = (x i 0x33333333) + ((x >> 2) i 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) i 0x33333333);
    x = (x + (x >> 4)) i 0x0F0F0F0F;
    y = (y + (y >> 4)) i 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    return (x + y) & 0x000000FF;
}

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

inline int pop2 (unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) i 0x5555555555555555);
    y = y - ((y >> 1) i 0x5555555555555555);
    x = (x i 0x3333333333333333) + ((x >> 2) i 0x333333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) i 0x333333333333333333);
    x = (x + (x >> 4)) i 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) i 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    zwraca x & 0xFF;
}

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.

inline int pop4 (unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v)
{
  wyliczenie {m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF};

    x = x - ((x >> 1) i m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) i m1);
    v = v - ((v >> 1) i m1);
    x = (x i m2) + ((x >> 2) i m2);
    y = (y & m2) + ((y >> 2) i m2);
    u = (u & m2) + ((u >> 2) i m2);
    v = (v i m2) + ((v >> 2) i m2);
    x = x + y; 
    u = u + v; 
    x = (x i m3) + ((x >> 4) i m3);
    u = (u & m3) + ((u >> 4) i m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    zwraca x & 0x000001FF;
}

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.

   hitime b4 = rdtsc (); 
   dla (bez znaku długie i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i) 
      suma + = pop4 (i, i ^ 1, ~ i, i | 1); 
   hitime e4 = rdtsc (); 

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.

183351
źródło
2
Najlepsza forma nie-asemblerowa, jaką widziałem, jednocześnie rozwijając 24 32-bitowe słowa. dalkescientific.com/writings/diary/popcnt.c , stackoverflow.com/questions/3693981/... , dalkescientific.com/writings/diary/archive/2008/07/05/…
Matt Joiner
28

Dlaczego nie podzielić iteracyjnie przez 2?

liczba = 0
podczas gdy n> 0
  jeśli (n% 2) == 1
    liczyć + = 1
  n / = 2  

Zgadzam się, że nie jest to najszybszy, ale „najlepszy” jest nieco niejednoznaczny. Twierdziłbym jednak, że „najlepsze” powinno mieć element jasności

Daniel
źródło
To zadziała i jest łatwe do zrozumienia, ale istnieją szybsze metody.
Matt Howells,
2
Jeśli nie zrobisz tego dużo , wpływ na wydajność byłby znikomy. Tak więc wszystkie rzeczy są równe, zgadzam się z Danielem, że „najlepsze” oznacza „nie czytać jak bełkot”.
2
Celowo nie zdefiniowałem „najlepszego”, aby uzyskać różne metody. Spójrzmy prawdzie w oczy, jeśli osiągnęliśmy poziom tego rodzaju kręcenia bitów, prawdopodobnie szukamy czegoś niesamowicie szybkiego, który wyglądałby jak napisany przez szympansa.
Matt Howells,
6
Zły kod. Kompilator może zrobić z niego dobry, ale w moich testach GCC nie. Zamień (n% 2) na (n & 1); I jest znacznie szybszy niż MODULO. Zamień (n / = 2) na (n >> = 1); przesunięcie bitów znacznie szybciej niż podział.
Mecki,
6
@ Mecki: W moich testach gcc (4.0, -O3) dokonał oczywistych optymalizacji.
26

Kręcenie bitów Hacker's Delight staje się o wiele wyraźniejsze, gdy zapisujesz wzory bitów.

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

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.

John Dimm
źródło
3
Wydaje się, że to rozwiązanie ma niewielki problem związany z pierwszeństwem operatora. Dla każdego terminu należy powiedzieć: x = (((x >> 1) i 0b01010101010101010101010101010101) + (x & 0b01010101010101010101010101010101)); (tzn. dodano dodatkowe pareny).
Nopik
21

Aby uzyskać szczęśliwe medium między tabelą wyszukiwania 2 32 i iteracją każdego bitu z osobna:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

Od http://ctips.pbwiki.com/CountBits

PhirePhly
źródło
Nieprzenośny. Co jeśli procesor ma 9 bitów? Tak, są tam naprawdę takie procesory ...
Robert S. Barnes
15
@Robert S. Barnes, ta funkcja nadal będzie działać. Nie przyjmuje żadnych założeń dotyczących rozmiaru natywnego słowa i nie ma w ogóle odniesienia do „bajtów”.
finnw
19

Można to zrobić w O(k), gdzie kjest ustawiona liczba bitów.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}
herohuyongtao
źródło
Jest to zasadniczo algorytm Briana Kernighana (pamiętasz go?), Z niewielką zmianą, że użył bardziej zwięzłej n &= (n-1)formy.
Adrian Mole
17

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:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}
Peter
źródło
4
och, podoba mi się to. jak o wersji python: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))()
underrun
10

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.

Michael Dorfman
źródło
10
  private int get_bits_set(int v)
    {
      int c; // c accumulates the total bits set in v
        for (c = 0; v>0; c++)
        {
            v &= v - 1; // clear the least significant bit set
        }
        return c;
    }
stacktay
źródło
9

Kilka otwartych pytań: -

  1. Jeśli liczba jest ujemna, to?
  2. Jeśli liczba wynosi 1024, wówczas metoda „iteracyjnego dzielenia przez 2” będzie iterować 10 razy.

możemy zmodyfikować algo, aby obsługiwał liczbę ujemną w następujący sposób:

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

teraz, aby rozwiązać drugi problem, możemy napisać algo w stylu: -

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

dla pełnego odniesienia patrz:

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

Baban
źródło
9

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

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

Opublikowano w 1988 r., C Programming Language 2nd Ed. (autor: Brian W. Kernighan i Dennis M. Ritchie) wspomina o tym w ćwiczeniu 2-9. 19 kwietnia 2006 r. Don Knuth wskazał mi, że ta metoda „została po raz pierwszy opublikowana przez Petera Wegnera w CACM 3 (1960), 322. (Odkryta również niezależnie przez Derrick Lehmera i opublikowana w 1964 r. W książce pod redakcją Beckenbacha)”.

Błąd
źródło
8

Korzystam z poniższego kodu, który jest bardziej intuicyjny.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Logika: n & (n-1) resetuje ostatni ustawiony bit n.

PS: Wiem, że to nie jest rozwiązanie O (1), ale ciekawe rozwiązanie.

Manish Mulani
źródło
jest to dobre w przypadku „rzadkich” liczb z małą liczbą bitów O(ONE-BITS). Rzeczywiście jest to O (1), ponieważ jest co najwyżej 32 jednobitowe.
ealfonso
7

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:

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
        static int bitCountOfByte( int value ){
            return BIT_COUNT[ value & 0xFF ];
        }

        static int bitCountOfInt( int value ){
            return bitCountOfByte( value ) 
                 + bitCountOfByte( value >> 8 ) 
                 + bitCountOfByte( value >> 16 ) 
                 + bitCountOfByte( value >> 24 );
        }

Myślę, że nie będzie to szybsze dla wartości 64-bitowej, ale wartość 32-bitowa może być szybsza.

Horkruks 7
źródło
Mój kod ma 10 operacji. Twój kod ma 12 operacji. Twój link działa z mniejszymi tablicami (5). Używam 256 elementów. Z buforowaniem może być problem. Ale jeśli używasz go bardzo często, nie stanowi to problemu.
Horcrux7
Jak się okazuje, takie podejście jest mierzalnie nieco szybsze niż podejście polegające na kręceniu bitów. Jeśli chodzi o użycie większej ilości pamięci, kompiluje się do mniejszej ilości kodu i to wzmocnienie jest powtarzane za każdym razem, gdy wstawiasz funkcję. Może więc łatwo okazać się wygraną netto.
7

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.

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

Oto sekret pierwszego i najbardziej złożonego kroku:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

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.

  • Don Gillies
SystemBuilder
źródło
7

jeśli używasz C ++, inną opcją jest użycie metaprogramowania szablonu:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

użycie byłoby:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

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)

2 obroty
źródło
Niestety liczenie bitów nie odbywa się równolegle, więc prawdopodobnie jest wolniejsze. Może to miłe constexpr.
imallett
Zgadzam się - było to zabawne ćwiczenie w rekursji szablonów C ++, ale zdecydowanie dość naiwne rozwiązanie.
pentafobe,
6

Szczególnie podoba mi się ten przykład z pliku fortuny:

# zdefiniować BITCOUNT (x) (((BX_ (x) + (BX_ (x) >> 4)) i 0x0F0F0F0F)% 255)
# zdefiniować BX_ (x) ((x) - (((x) >> 1) i 0x77777777)
                             - (((x) >> 2) i 0x33333333)
                             - (((x) >> 3) i 0x11111111))

Najbardziej mi się podoba, ponieważ jest taki ładny!

Ross
źródło
1
Jak to działa w porównaniu z innymi sugestiami?
asdf
6

Java JDK1.5

Integer.bitCount (n);

gdzie n jest liczbą, której 1 należy liczyć.

sprawdź także

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }
Rahul
źródło
To nie jest algorytm, to tylko wywołanie biblioteki. Przydatne w Javie, nie tyle dla wszystkich innych.
benzado
2
@benzado ma rację, ale i tak daje +1, ponieważ niektórzy programiści Java mogą nie wiedzieć o metodzie
finnw
@finnw, jestem jednym z tych programistów. :)
neevek
6

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:

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

Wersja AVX2:

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}
ErmIg
źródło
6

Zawsze używam tego w programowaniu konkurencyjnym i jest łatwy do napisania i wydajny:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}
diugalde
źródło
5

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

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

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.

Mostafa
źródło
5

Szybkie rozwiązanie C # przy użyciu wstępnie obliczonej tabeli liczby bitów z rozgałęzieniem na wielkości wejściowej.

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS = 
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}
dadhi
źródło
Jak na ironię, ta tabela mogła zostać utworzona przez dowolny algorytm opublikowany w tym wątku! Niemniej jednak korzystanie z takich tabel oznacza stałą wydajność. Posunięcie się o krok dalej i utworzenie tabeli translacji o wielkości 64 KB spowodowałoby zatem zmniejszenie o połowę koniecznych operacji AND, SHIFT i ADD. Ciekawy temat dla manipulatorów bitowych!
user924272
Większe tabele mogą być wolniejsze (a nie stałe) z powodu problemów z pamięcią podręczną. Możesz „wyszukać” 3 bity jednocześnie (0xe994 >>(k*2))&3, bez dostępu do pamięci ...
greggo
5

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ć.

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );

/* List of available bitcount algorithms.  
 * onTheFly:    Calculate the bitcount on demand.
 *
 * lookupTalbe: Uses a small lookup table to determine the bitcount.  This
 * method is on average 3 times as fast as onTheFly, but incurs a small
 * upfront cost to initialize the lookup table on the first call.
 *
 * strategyCount is just a placeholder. 
 */
enum strategy { onTheFly, lookupTable, strategyCount };

/* String represenations of the algorithm names */
extern const char *strategyNames[];

/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );

#endif

.

#include <limits.h>

#include "bitcount.h"

/* The number of entries needed in the table is equal to the number of unique
 * values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;

static int _defaultBitCount( unsigned int val ) {
    int count;

    /* Starting with:
     * 1100 - 1 == 1011,  1100 & 1011 == 1000
     * 1000 - 1 == 0111,  1000 & 0111 == 0000
     */
    for ( count = 0; val; ++count )
        val &= val - 1;

    return count;
}

/* Looks up each byte of the integer in a lookup table.
 *
 * The first time the function is called it initializes the lookup table.
 */
static int _tableBitCount( unsigned int val ) {
    int bCount = 0;

    if ( !_lookupTableInitialized ) {
        unsigned int i;
        for ( i = 0; i != UCHAR_MAX + 1; ++i )
            _bitCountTable[i] =
                ( unsigned char )_defaultBitCount( i );

        _lookupTableInitialized = 1;
    }

    for ( ; val; val >>= CHAR_BIT )
        bCount += _bitCountTable[val & UCHAR_MAX];

    return bCount;
}

static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;

const char *strategyNames[] = { "onTheFly", "lookupTable" };

void setStrategy( enum strategy s ) {
    switch ( s ) {
    case onTheFly:
        _bitcount = _defaultBitCount;
        break;
    case lookupTable:
        _bitcount = _tableBitCount;
        break;
    case strategyCount:
        break;
    }
}

/* Just a forwarding function which will call whichever version of the
 * algorithm has been selected by the client 
 */
int bitcount( unsigned int val ) {
    return _bitcount( val );
}

#ifdef _BITCOUNT_EXE_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Use the same sequence of pseudo random numbers to benmark each Hamming
 * Weight algorithm.
 */
void benchmark( int reps ) {
    clock_t start, stop;
    int i, j;
    static const int iterations = 1000000;

    for ( j = 0; j != strategyCount; ++j ) {
        setStrategy( j );

        srand( 257 );

        start = clock(  );

        for ( i = 0; i != reps * iterations; ++i )
            bitcount( rand(  ) );

        stop = clock(  );

        printf
            ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
              reps * iterations, strategyNames[j],
              ( double )( stop - start ) / CLOCKS_PER_SEC );
    }
}

int main( void ) {
    int option;

    while ( 1 ) {
        printf( "Menu Options\n"
            "\t1.\tPrint the Hamming Weight of an Integer\n"
            "\t2.\tBenchmark Hamming Weight implementations\n"
            "\t3.\tExit ( or cntl-d )\n\n\t" );

        if ( scanf( "%d", &option ) == EOF )
            break;

        switch ( option ) {
        case 1:
            printf( "Please enter the integer: " );
            if ( scanf( "%d", &option ) != EOF )
                printf
                    ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
                      option, option, bitcount( option ) );
            break;
        case 2:
            printf
                ( "Please select number of reps ( in millions ): " );
            if ( scanf( "%d", &option ) != EOF )
                benchmark( option );
            break;
        case 3:
            goto EXIT;
            break;
        default:
            printf( "Invalid option\n" );
        }

    }

 EXIT:
    printf( "\n" );

    return 0;
}

#endif
Robert S. Barnes
źródło
1
Bardzo podoba mi się twoje wtyczkowe, polimorficzne podejście, a także przełącznik budowania jako biblioteki wielokrotnego użytku lub samodzielnego, testowego pliku wykonywalnego. Bardzo dobrze przemyślane =)
5

co możesz zrobić to

while(n){
    n=n&(n-1);
    count++;
}

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.

Varun Gusain
źródło