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

Rozważ również wbudowane funkcje kompilatorów.

Na przykład na kompilatorze GNU możesz 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ę cpu, aby wykonać tę samą pracę szybciej.

Na x86 możesz powiedzieć kompilatorowi, że może przyjąć wsparcie dla popcnt instrukcji z -mpopcnt lub -msse4.2, aby również włączyć instrukcje wektorowe, które zostały dodane w tej samej generacji. Zobacz Opcje GCC x86 . -march=nehalem (lub -march= jakikolwiek procesor chcesz, aby Twój kod założył i dostroić) może być dobrym wyborem. Uruchomienie wynikowego pliku binarnego na starszym procesorze spowoduje błąd nielegalnej instrukcji.

Aby zoptymalizować pliki binarne dla maszyny, na której je zbudujesz, użyj -march=native (z gcc, clang lub ICC).

MSVC zapewnia wewnętrzną instrukcję x86 popcnt , 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 wydajnie popcountować dla procesora docelowego, powinien ujawnić tę funkcjonalność poprzez ISO C++ std::bitset<>. W praktyka, może być lepiej z bit-hack I / shift / ADD w niektórych przypadkach dla niektórych procesorów docelowych.

Dla architektur docelowych, w których hardware popcount jest opcjonalnym rozszerzeniem (jak x86), nie wszystkie Kompilatory mają std::bitset, który korzysta z niego, gdy jest dostępny. Na przykład, MSVC nie ma możliwości włączenia obsługi popcnt w czasie kompilacji i zawsze używa przeszukiwania tabeli , nawet z /Ox /arch:AVX (co implikuje SSE4. 2, chociaż technicznie istnieje oddzielny bit funkcji dla popcnt.)

Ale przynajmniej dostajesz coś przenośnego, co działa wszędzie, a z gcc/clang z odpowiednimi opcjami docelowymi, dostajesz hardware popcount 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();
}

X86-64 gcc -O3 -std=gnu++11 -mpopcnt emituje 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

PowerPC64 gcc -O3 -std=gnu++11 emituje (dla wersji int arg):

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

To źródło wcale nie jest specyficzne dla x86 ani GNU, ale tylko dobrze kompiluje dla x86 z gcc/clang / icc.

Zauważ również, że GCC dla architektur bez pojedynczej instrukcji popcount jest przeszukiwaniem tabeli bajt-w-czasie. To nie jest wspaniałe dla ARM, na przykład.

Moim zdaniem "najlepszym" rozwiązaniem jest to, które może odczytać inny programista (lub oryginalny programista dwa lata później) bez obfitych komentarzy. Możesz chcieć najszybszego lub najmądrzejszego rozwiązania, które niektórzy już dostarczyli, ale wolę czytelność niż sprytność w każdej chwili.

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ć prędkość (i zakładając, że dobrze ją udokumentujesz, aby pomóc swoim następcom), możesz użyć wyszukiwania 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ślonym typie danych rozmiary, więc nie są tak przenośne. Ale ponieważ wiele optymalizacji wydajności i tak nie jest przenośnych, może to nie być problem. Jeśli chcesz przenośności, chciałbym trzymać się czytelnego rozwiązania.

Z 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 w ~20-owskich instrukcjach (zależnych od łuku), bez rozgałęzień.

Hacker ' s Delight jest zachwycająca! Gorąco polecam.

Myślę, że najszybszy sposób-bez użycia tabel lookup i popcount -jest następujący. Zlicza ustawione bity z zaledwie 12 operacjami.

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ę bitów zestawu, dzieląc na dwie połówki, licząc liczbę bitów zestawu w obu połówkach, a następnie dodając je. Znany również jako Divide and Conquer paradygmat. Przejdźmy do szczegółów..

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

Liczba bitów w dwóch bitach może być 0b00, 0b01 lub 0b10. Spróbujmy to wypracować na 2 bity..

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

To jest to, co było wymagane: ostatnia kolumna pokazuje liczbę ustawionych bitów w każdej parze bitów. Jeśli liczba dwóch bitów wynosi >= 2 (0b10), to and produkuje 0b01, w przeciwnym razie produkuje 0b00.

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

To stwierdzenie powinno być łatwe do zrozumienia. Po pierwszej operacji mamy liczbę ustawionych bitów w co dwa bity, teraz sumujemy tę liczbę w co 4 bity.

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

Następnie sumujemy powyższy wynik, dając nam całkowitą liczbę ustawionych bitów w 4 bitach. Na ostatnia wypowiedź jest najtrudniejsza.

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

Wyjaśnijmy to jeszcze raz...

v + (v >> 4)

Jest to podobne do drugiej instrukcji; zamiast tego liczymy bity zbioru w grupach po 4. Wiemy-ze względu na nasze poprzednie operacje-że każde skubanie ma w sobie liczbę bitów setowych. Spójrzmy na przykład. Załóżmy, że mamy bajt 0b01000010. Oznacza to, że pierwszy skubaniec ma swój zestaw 4-bitowy, a drugi ma swój zestaw 2-bitowy. Teraz dodamy te przekąski razem.

0b01000010 + 0b01000000

Daje nam liczba ustawionych bitów w bajcie, w pierwszym 0b01100010 i dlatego maskujemy ostatnie cztery bajty ze wszystkich bajtów w liczbie (odrzucając je).

0b01100010 & 0xF0 = 0b01100000

Teraz każdy bajt ma w sobie liczbę ustawionych bitów. Musimy je połączyć. Sztuczka polega na pomnożeniu wyniku przez 0b10101010, który ma interesującą właściwość. Jeśli nasza liczba ma cztery bajty, A B C D, spowoduje to powstanie nowej liczby z tymi bajtami A+B+C+D B+C+D C+D D. Liczba 4 bajtów może mieć maksymalnie 32 bity ustawione, co może być reprezentowane jako 0b00100000.

Teraz potrzebujemy tylko pierwszego bajtu, który ma sumę wszystkich ustawionych bitów we wszystkich bajtach i otrzymujemy go przez >> 24. Algorytm ten został zaprojektowany dla słów 32 bit, ale można go łatwo zmodyfikować dla słów 64 bit.

Znudziło mi się i zmierzyłem miliard iteracji trzech podejść. Kompilatorem jest gcc-O3. Procesor jest tym, co umieścili w MacBooku Pro 1. generacji.

Najszybsza jest następująca, w 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 idzie do tego samego kodu, ale szuka 4 bajtów zamiast 2 halfwords. Trwało to około 5,5 sekundy.

Trzecie miejsce zajmuje nieco skrętne podejście "sideways addition", które zajęło 8,6 sekundy.

Czwarte miejsce zajmuje GCC ' s _ _ builtin _ popcount (), na wstydliwe 11 sekund.

Liczenie bit-w-czasie było waaaay wolniejsze, i znudziło mi się czekanie na zakończenie.

Więc jeśli zależy Ci przede wszystkim na wydajności, skorzystaj z pierwszego podejścia. Jeśli Ci zależy, ale nie na tyle, aby wydać na to 64Kb PAMIĘCI RAM, użyj drugiego podejścia. W przeciwnym razie użyj czytelnego (ale powolnego) podejścia "jeden bit na raz".

Edit: Podobne wyniki tutaj .

Jeśli przypadkiem używasz Javy, zrobi to wbudowana metoda Integer.bitCount.

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;
}

Algorytm ten opiera się na algorytmie "Divide and Conquer". Załóżmy, że istnieje 8-bitowa liczba całkowita 213(11010101 w systemie binarnym), algorytm działa tak(za każdym razem łączyć dwa bloki sąsiadujące):

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

To jedno z tych pytań, gdzie pomaga poznać Twoją mikroarchitekturę. Właśnie zmierzyłem dwa warianty pod gcc 4.3.3 skompilowane z-O3 za pomocą linii C++, aby wyeliminować napowietrzne wywołania funkcji, miliard iteracji, zachowując bieżącą sumę wszystkich liczeń, aby upewnić się, że kompilator nie usunie niczego ważnego, używając rdtsc do pomiaru czasu (dokładny cykl zegara).

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

Ma to związek z łańcuchami zależności instrukcji, które są bardzo złe dla tego algorytmu. Mogłem prawie podwoić prędkość ponownie, używając pary 64-bitowych rejestrów. W rzeczywistości, gdybym był sprytny i dodał x + y trochę wcześniej mógłbym ogolić kilka zmian. Wersja 64-bitowa z niewielkimi poprawkami wyszłoby na parzyste, ale policz dwa razy więcej bitów.

Z 128-bitowymi rejestrami SIMD, to kolejny czynnik dwóch, a zestawy instrukcji SSE często mają sprytne skróty.

Ok, zdecydowałem się na zmianę wersji 64-bitowej. For this one sizeof (unsigned long) = = 8

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

To wygląda w porządku (nie testuję uważnie, choć). Teraz terminy wychodzą na 10.70 gigacykli / 14.1 gigacykli. Ta późniejsza liczba zsumowała 128 miliardów bitów i odpowiada 5,9 s upłynął na tej maszynie. Wersja non-parallel przyspiesza trochę, ponieważ pracuję w trybie 64-bitowym i lubi nieco 64-bitowe rejestry lepsze niż rejestry 32-bitowe.

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

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

Byłem podekscytowany przez chwilę, ale okazało się, że gcc bawi się sztuczkami inline z -O3, mimo że nie używam słowa kluczowego inline w niektórych testach. Kiedy pozwalam gcc grać figle, miliard wywołań do pop4 () zajmuje 12,56 GIGA, ale stwierdziłem, że to składanie argumenty jako wyrażenia stałe. Bardziej realistyczna liczba wydaje się być 19.6 gc dla kolejnego 30% przyspieszenie. Moja pętla testowa wygląda teraz tak, upewniając się, że każdy argument jest na tyle inny, aby powstrzymać gcc przed płataniem figli.

   hitime b4 = rdtsc(); 
   for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) 
      sum += pop4 (i,  i^1, ~i, i|1); 
   hitime e4 = rdtsc(); 

256 miliardów bitów zsumowanych w czasie 8,17 s. Działa do 1.02 s dla 32 milionów bitów jako benchmarked w 16-bitowej tabeli wyszukiwania. Nie mogę porównywać bezpośrednio, bo druga ławka nie daje taktowania, ale wygląda na to, że spoliczkowałem snota z 64KB table edition, czyli tragiczne użycie pamięci podręcznej L1.

Update: postanowiłem zrobić oczywiste i utworzyć pop6 (), dodając cztery kolejne zduplikowane linie. Wyszło 22,8 gc, 384 miliardy bitów podsumowane w 9,5 s upłynęło. Więc jest kolejne 20% teraz na 800ms za 32 miliardy bitów.

Dlaczego nie podzielić iteracyjnie przez 2?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

Zgadzam się, że nie jest to najszybszy, ale "najlepszy" jest nieco niejednoznaczny. Argumentowałbym jednak, że "najlepsze" powinno mieć element klarowności

Dla szczęśliwego medium pomiędzy 2³² przeszukiwanie tabeli i iteracja 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;
}

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

[1]}Rozkosz hakera bit-twidling staje się o wiele wyraźniejsza, gdy wypisujesz 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 bity parzyste do nieparzystych, tworząc sumę bitów w każdym z dwóch. Pozostałe kroki dodają kawałki wysokiego rzędu do kawałków niskiego rzędu, podwajając rozmiar kawałka aż do góry, aż do ostatecznego liczenia zajmującego całą int.

Nie jest to najszybsze i najlepsze rozwiązanie, ale znalazłem to samo pytanie na swojej drodze 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 masz problem od strony matematycznej i narysować wykres, a następnie okaże się, że jest to funkcja, która ma pewną część okresową, a następnie zdajesz sobie sprawę z różnicy 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);
    }
}

Można to zrobić w O(k), Gdzie k jest liczbą ustawionych bitów.

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

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

    return count;
}

Funkcja, której szukasz, jest często nazywana "sumą boczną" lub "liczbą ludności" liczby binarnej. Knuth omawia to w pre-Fascicle 1A, pp11-12 (chociaż było krótkie odniesienie w tomie 2, 4.6.3-(7).)

locus classicus to artykuł Petera Wegnera "Technika liczenia jedynek w komputerze binarnym", z komunikaty ACM , Volume 3 (1960) Number 5, page 322. Podaje tam dwa różne algorytmy, jeden zoptymalizowany dla liczb, które mają być " rzadkie "(tzn. mają małą liczbę jedynek) i jeden dla przeciwnego przypadku.

Kilka pytań otwartych: -

1. jeśli liczba jest ujemna to?
2. jeśli liczba jest 1024, to metoda "iteracyjnie dziel 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 przezwyciężyć 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;
}

Pełne odniesienie patrz:

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

  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;
    }

Myślę, że metoda Briana Kernighana też się przyda... Przechodzi przez tyle iteracji, ile jest ustawionych bitów. Więc jeśli mamy słowo 32-bitowe z ustawionym tylko wysokim bitem, to 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; 
}

Opublikowany w 1988 roku, język programowania C 2nd Ed. (Brian W. Kernighan i Dennis M. Ritchie) wspomina o tym w ćwiczeniach 2-9. 19 kwietnia 2006 roku Don Knuth zwrócił mi uwagę, że metoda ta " została po raz pierwszy opublikowana przez Petera Wegnera w CACM 3 (1960), 322. (Również odkryty niezależnie przez Derricka Lehmera i opublikowany w 1964 w książce pod redakcją Beckenbacha.)"

Używam 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 bit zestawu n.

P. s: wiem, że to nie jest rozwiązanie O(1), aczkolwiek ciekawe rozwiązanie.

Co masz na myśli mówiąc "najlepszy algorytm"? Kod skrócony 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, to myślę, że następujące mogą 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.

Napisałem szybkie makro bitcount dla maszyn RISC około 1990 roku. Nie używa zaawansowanej arytmetyki( mnożenie, dzielenie,%), pobierania pamięci (zbyt wolne), gałęzi (zbyt wolne), ale zakłada, że procesor ma 32-bitowy barrel shifter (innymi słowy, > > 1 i >> 32 biorą taką samą ilość cykli.) Zakłada, że małe stałe (takie jak 6, 12, 24) nic nie kosztują, aby załadować je do rejestrów, lub są przechowywane tymczasowo i ponownie używane w kółko.

Z tymi założenia, liczy 32 bity w około 16 cyklach / instrukcjach na większości maszyn RISC. Zauważ, że 15 instrukcji / cykli jest zbliżone do dolnej granicy liczby cykli lub instrukcji, ponieważ wydaje się, że potrzeba co najmniej 3 Instrukcji (Maska, shift, operator), aby przeciąć liczbę dodanych na pół, więc log_2(32) = 5, 5 x 3 = 15 instrukcji jest quasi-dolną wartością.

#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ę 1 kolumnę (a) powyżej, przesuń to prawo 1 bit, i odjąć go od AB, i uzyskać wyjście (CD). Rozszerzenie do 3 bitów jest podobne; możesz to sprawdzić za pomocą 8-rzędowej tabeli logicznej, takiej jak moja powyżej, jeśli chcesz.

• Don Gillies

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:

// 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żna oczywiście dalej rozbudowywać ten szablon, aby używać różnych typów (nawet auto-detecting bit size), ale zachowałem to dla jasności.

Edit: zapomniałem wspomnieć, że jest to dobre, ponieważ powinno działać w dowolnym kompilatorze C++ i w zasadzie po prostu rozwija pętlę dla Ciebie, jeśli stała wartość jest używana dla liczby bitów (innymi słowy, jestem jestem pewien, że to najszybsza Metoda ogólna, jaką znajdziesz)

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

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

Java JDK1.5

Liczba całkowita.bitCount(N);

Gdzie n jest liczbą, której 1 mają być policzone.

Zobacz też:

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);
         }

Znalazłem implementację liczenia bitów w tablicy z wykorzystaniem instrukcji SIMD (SSSE3 i AVX2). Ma 2-2, 5 razy lepszą wydajność niż jeśli użyje 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];
}

Zawsze używam tego w programowaniu konkurencyjnym i jest to łatwe do napisania i wydajne:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

Istnieje wiele algorytmów do liczenia ustawionych bitów; ale myślę, że najlepszy jest szybszy! Możesz zobaczyć szczegóły na tej stronie:

Bit Twidling Hacki

Proponuję ten:

Zliczanie bitów ustawionych w słowach 14, 24 lub 32-bitowych 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 64-bitowego procesora z szybkim podziałem modułów, aby była wydajna. Pierwsza opcja zajmuje tylko 3 operacje; druga opcja zajmuje 10; a trzecia opcja zajmuje 15.

Oto przenośny moduł (ANSI-C), który może porównywać każdy z Twoich algorytmów na dowolnej architekturze.

Twój procesor ma 9 bitów bajtów? Nie ma problemu : -) w tej chwili implementuje algorytmy 2, algorytm K&R i tabelę mądrego wyszukiwania bajtów. Tabela wyszukiwania jest średnio 3 razy szybsza niż algorytm K&R. Jeśli ktoś może wymyślić sposób, aby algorytm" Hacker 's Delight" był przenośny, nie krępuj się 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

32-bitowe czy nie ? Właśnie przyszedłem z tą metodą w Javie po przeczytaniu" cracking the coding interview " 4th edition exercice 5.5 (chap 5: Bit Manipulation). Jeśli najmniej znaczącym bitem jest przyrost o 1 count, to przesuń w prawo liczbę całkowitą.

public static int bitCount( int n){
    int count = 0;
    for (int i=n; i!=0; i = i >> 1){
        count += i & 1;
    }
    return count;
}

Myślę, że ten jest bardziej intuicyjny niż rozwiązania ze stałą 0x3333333 bez względu na to, jak szybkie są. To zależy od twojej definicji "najlepszego algorytmu".

Szybkie rozwiązanie w języku C # wykorzystujące wstępnie obliczoną tabelę z liczeniem bitów bajtów z rozgałęzieniami na wielkość wejściową.

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
    };
}