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

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?

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:

• https://graphics.stanford.edu/~seander/bithacks.html
• https://en.wikipedia.org/wiki/Hamming_weight
• http://gurmeet.net/puzzles/fast-bit-counting-routines/
• http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)

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 .

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.

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.

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.

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 .

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

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

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.

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

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.

Aby uzyskać szczęśliwe medium między tabelą wyszukiwania 2 ³² 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

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

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

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.

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

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

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

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.

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.

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

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)

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!

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

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

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

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.

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

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

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.