Bagaimana cara menghitung jumlah bit yang ditetapkan dalam integer 32-bit?

8 bit mewakili angka 7 terlihat seperti ini:

00000111

Tiga bit diatur.

Apa algoritma untuk menentukan jumlah bit yang ditetapkan dalam integer 32-bit?

Ini dikenal sebagai ' Berat Hamming ', 'popcount' atau 'penambahan samping'.

Algoritma 'terbaik' sangat tergantung pada CPU Anda dan apa pola penggunaan Anda.

Beberapa CPU memiliki instruksi built-in tunggal untuk melakukannya dan yang lain memiliki instruksi paralel yang bekerja pada vektor bit. Instruksi paralel (seperti x86 popcnt, pada CPU yang didukungnya) hampir pasti akan tercepat. Beberapa arsitektur lain mungkin memiliki instruksi yang lambat diimplementasikan dengan loop microcoded yang menguji sedikit per siklus ( kutipan diperlukan ).

Metode pencarian tabel pra-populasi bisa sangat cepat jika CPU Anda memiliki cache yang besar dan / atau Anda melakukan banyak instruksi ini dalam satu lingkaran yang ketat. Namun itu dapat menderita karena biaya 'cache miss', di mana CPU harus mengambil beberapa tabel dari memori utama. (Cari setiap byte secara terpisah untuk menjaga tabel tetap kecil.)

Jika Anda tahu bahwa byte Anda sebagian besar adalah 0 atau sebagian besar 1 maka ada algoritma yang sangat efisien untuk skenario ini.

Saya percaya algoritma tujuan umum yang sangat baik adalah sebagai berikut, dikenal sebagai 'paralel' atau 'algoritma SWAR presisi-variabel'. Saya telah menyatakan ini dalam bahasa pseudo seperti-C, Anda mungkin perlu menyesuaikannya agar berfungsi untuk bahasa tertentu (mis. Menggunakan uint32_t untuk C ++ dan >>> di Jawa):

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

Untuk JavaScript: memaksa untuk integer dengan |0untuk kinerja: ubah baris pertama menjadii = (i|0) - ((i >> 1) & 0x55555555);

Ini memiliki perilaku kasus terburuk terbaik dari semua algoritma yang dibahas, jadi akan secara efisien menangani pola penggunaan atau nilai yang Anda berikan.

Bagaimana bithack SWAR ini bekerja:

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

Langkah pertama adalah versi masking yang dioptimalkan untuk mengisolasi bit aneh / genap, bergeser untuk berbaris, dan menambahkan. Ini secara efektif melakukan 16 penambahan terpisah dalam akumulator 2-bit ( SWAR = SIMD Dalam Daftar ). Seperti (i & 0x55555555) + ((i>>1) & 0x55555555).

Langkah selanjutnya mengambil delapan ganjil / genap dari akumulator 16x 2-bit dan menambahkan lagi, menghasilkan jumlah 8x 4-bit. The i - ...optimasi tidak mungkin saat ini sehingga tidak hanya topeng sebelum / sesudah pergeseran. Menggunakan 0x33...konstanta yang sama dua kali daripada 0xccc...sebelum bergeser adalah hal yang baik ketika mengkompilasi untuk SPA yang perlu membangun konstanta 32-bit dalam register secara terpisah.

Langkah terakhir shift-and-add (i + (i >> 4)) & 0x0F0F0F0Fmelebar ke akumulator 4x 8-bit. Itu topeng setelah menambahkan bukan sebelumnya, karena nilai maksimum dalam akumulator 4-bit adalah 4, jika semua 4 bit dari bit input yang sesuai ditetapkan. 4 + 4 = 8 yang masih muat dalam 4 bit, jadi membawa antar elemen nibble tidak mungkin dilakukan i + (i >> 4).

Sejauh ini ini hanya SIMD yang cukup normal menggunakan teknik SWAR dengan beberapa optimasi pintar. Melanjutkan dengan pola yang sama untuk 2 langkah lagi dapat melebar menjadi 2x 16-bit kemudian 1x 32-bit. Tetapi ada cara yang lebih efisien pada mesin dengan perangkat keras yang berlipat ganda:

Setelah kita memiliki beberapa "elemen" yang cukup, perkalian dengan konstanta sihir dapat menjumlahkan semua elemen menjadi elemen teratas . Dalam hal ini elemen byte. Multiply dilakukan dengan meninggalkan-pergeseran dan menambahkan, jadi kalikan dari x * 0x01010101hasil di x + (x<<8) + (x<<16) + (x<<24). Elemen 8-bit kami cukup lebar (dan memegang jumlah yang cukup kecil) bahwa ini tidak menghasilkan carry ke atas yang 8 bit.

Versi 64-bit ini dapat melakukan elemen 8x 8-bit dalam integer 64-bit dengan pengganda 0x010101010101010101, dan mengekstrak byte tinggi dengan >>56. Jadi itu tidak mengambil langkah ekstra, hanya konstanta yang lebih luas. Inilah yang digunakan GCC untuk __builtin_popcountllsistem x86 ketika popcntinstruksi perangkat keras tidak diaktifkan. Jika Anda dapat menggunakan builtin atau intrinsik untuk ini, lakukan itu untuk memberi kompiler kesempatan untuk melakukan optimasi target-spesifik.

Dengan SIMD penuh untuk vektor yang lebih luas (mis. Menghitung seluruh array)

Algoritma bitwise-SWAR ini dapat diparalelkan untuk dilakukan dalam beberapa elemen vektor sekaligus, bukan dalam register integer tunggal, untuk mempercepat pada CPU dengan SIMD tetapi tidak ada instruksi popcount yang dapat digunakan. (mis. kode x86-64 yang harus dijalankan pada CPU apa pun, bukan hanya Nehalem atau yang lebih baru.)

Namun, cara terbaik untuk menggunakan instruksi vektor untuk popcount biasanya dengan menggunakan variabel-shuffle untuk melakukan pencarian tabel untuk 4 bit pada setiap byte secara paralel. (4 bit indeks tabel entri 16 diadakan di register vektor).

Pada Intel CPU, perangkat keras 64bit popcnt dapat mengungguli implementasi paralel-bit SSSE3PSHUFB sekitar faktor 2, tetapi hanya jika kompiler Anda melakukannya dengan benar . Kalau tidak, SSE dapat keluar secara signifikan di depan. Versi kompiler yang lebih baru menyadari masalah ketergantungan popcnt salah pada Intel .

Referensi:

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

Juga pertimbangkan fungsi bawaan kompiler Anda.

Sebagai contoh, pada kompilator GNU Anda bisa menggunakan:

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

Dalam kasus terburuk kompiler akan menghasilkan panggilan ke suatu fungsi. Dalam kasus terbaik kompiler akan memancarkan instruksi cpu untuk melakukan pekerjaan yang sama lebih cepat.

GCC intrinsik bahkan bekerja di berbagai platform. Popcount akan menjadi arus utama dalam arsitektur x86, jadi masuk akal untuk mulai menggunakan intrinsik sekarang. Arsitektur lain memiliki popcount selama bertahun-tahun.

Pada x86, Anda bisa memberi tahu kompiler bahwa ia dapat menerima dukungan untuk popcntinstruksi dengan -mpopcntatau -msse4.2juga mengaktifkan instruksi vektor yang ditambahkan pada generasi yang sama. Lihat opsi GCC x86 . -march=nehalem(atau -march=CPU apa pun yang Anda inginkan untuk diasumsikan dan disetel oleh kode Anda) bisa menjadi pilihan yang baik. Menjalankan biner yang dihasilkan pada CPU yang lebih lama akan menghasilkan kesalahan instruksi-ilegal.

Untuk membuat binari dioptimalkan untuk mesin tempat Anda membuatnya, gunakan -march=native (dengan gcc, dentang, atau ICC).

MSVC menyediakan intrinsik untuk popcntinstruksi x86 , tetapi tidak seperti gcc, ini benar-benar intrinsik untuk instruksi perangkat keras dan membutuhkan dukungan perangkat keras.

Menggunakan std::bitset<>::count()bukannya built-in

Secara teori, setiap kompiler yang tahu bagaimana cara menghitung uang secara efisien untuk CPU target harus mengekspos fungsi itu melalui ISO C ++ std::bitset<>. Dalam praktiknya, Anda mungkin lebih baik dengan bit-hack DAN / shift / ADD dalam beberapa kasus untuk beberapa CPU target.

Untuk arsitektur target di mana perangkat keras popcount adalah ekstensi opsional (seperti x86), tidak semua kompiler memiliki std::bitsetyang memanfaatkannya saat tersedia. Misalnya, MSVC tidak memiliki cara untuk mengaktifkan popcntdukungan pada waktu kompilasi, dan selalu menggunakan pencarian tabel , bahkan dengan /Ox /arch:AVX(yang menyiratkan SSE4.2, meskipun secara teknis ada sedikit fitur terpisah untuk popcnt.)

Tapi setidaknya Anda mendapatkan sesuatu yang portabel yang bekerja di mana-mana, dan dengan gcc / dentang dengan opsi target yang tepat, Anda mendapatkan perangkat keras popcount untuk arsitektur yang mendukungnya.

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

Lihat asm dari gcc, clang, icc, dan MSVC pada explorer compiler Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcntmemancarkan ini:

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++11memancarkan (untuk intversi arg):

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

Sumber ini sama sekali tidak spesifik x86 atau GNU, tetapi hanya mengkompilasi dengan baik untuk x86 dengan gcc / clang / icc.

Perhatikan juga bahwa fallback gcc untuk arsitektur tanpa popcount dengan instruksi tunggal adalah pencarian tabel byte per waktu. Ini tidak bagus untuk ARM, misalnya .

Menurut pendapat saya, solusi "terbaik" adalah solusi yang dapat dibaca oleh programmer lain (atau programmer asli dua tahun kemudian) tanpa komentar berlebihan. Anda mungkin menginginkan solusi tercepat atau paling pintar yang beberapa telah disediakan tetapi saya lebih suka keterbacaan daripada kepintaran setiap saat.

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

Jika Anda ingin lebih cepat (dan dengan asumsi Anda mendokumentasikannya dengan baik untuk membantu penerus Anda), Anda bisa menggunakan pencarian tabel:

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

Meskipun ini bergantung pada ukuran tipe data tertentu sehingga mereka tidak portabel. Namun, karena banyak pengoptimalan kinerja yang tidak portabel, itu mungkin bukan masalah. Jika Anda ingin mudah dibawa, saya akan tetap menggunakan solusi yang mudah dibaca.

Dari Hacker's Delight, hlm. 66, Gambar 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;
}

Menjalankan instruksi ~ 20-ish (tergantung lengkungan), tanpa percabangan.

Kegembiraan Hacker sangat menyenangkan! Sangat dianjurkan.

Saya pikir cara tercepat — tanpa menggunakan tabel pencarian dan popcount — adalah sebagai berikut. Itu menghitung bit yang ditetapkan hanya dengan 12 operasi.

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

Ini bekerja karena Anda dapat menghitung jumlah total set bit dengan membaginya menjadi dua, menghitung jumlah bit set pada kedua bagian dan kemudian menambahkannya. Juga dikenal sebagai Divide and Conquerparadigma. Mari kita masuk ke detail ..

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

Jumlah bit dalam dua bit dapat berupa 0b00, 0b01atau 0b10. Mari kita coba selesaikan ini pada 2 bit ..

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

Inilah yang diperlukan: kolom terakhir menunjukkan jumlah bit yang diset di setiap dua bit pasangan. Jika nomor bit kedua >= 2 (0b10)kemudian andmenghasilkan 0b01, yang lain menghasilkan 0b00.

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

Pernyataan ini harus mudah dimengerti. Setelah operasi pertama kita memiliki jumlah bit yang diset dalam setiap dua bit, sekarang kita meringkas jumlah itu dalam setiap 4 bit.

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

Kami kemudian meringkas hasil di atas, memberi kami jumlah total bit yang ditetapkan dalam 4 bit. Pernyataan terakhir adalah yang paling sulit.

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

Mari kita jabarkan lebih lanjut ...

v + (v >> 4)

Ini mirip dengan pernyataan kedua; kami menghitung bit yang ditetapkan dalam kelompok 4 sebagai gantinya. Kita tahu — karena operasi kita sebelumnya — bahwa setiap gigitan memiliki jumlah bit yang ditetapkan di dalamnya. Mari kita lihat sebuah contoh. Misalkan kita memiliki byte 0b01000010. Ini berarti gigitan pertama memiliki 4 bit yang ditetapkan dan yang kedua memiliki 2 bit yang ditetapkan. Sekarang kita tambahkan camilan itu bersama-sama.

0b01000010 + 0b01000000

Ini memberi kita hitungan bit yang ditetapkan dalam byte, pada gigitan pertama 0b01100010dan oleh karena itu kita menutupi empat byte terakhir dari semua byte dalam angka (membuangnya).

0b01100010 & 0xF0 = 0b01100000

Sekarang setiap byte memiliki hitungan set bit di dalamnya. Kita perlu menjumlahkan semuanya. Caranya adalah dengan melipatgandakan hasil 0b10101010yang memiliki properti menarik. Jika nomor kami memiliki empat byte A B C D, maka akan menghasilkan angka baru dengan byte ini A+B+C+D B+C+D C+D D. Angka 4 byte dapat memiliki set maksimum 32 bit, yang dapat direpresentasikan sebagai 0b00100000.

Yang kita butuhkan sekarang adalah byte pertama yang memiliki jumlah semua bit yang ditetapkan dalam semua byte, dan kita mendapatkannya >> 24. Algoritma ini dirancang untuk 32 bitkata - kata tetapi dapat dengan mudah dimodifikasi untuk 64 bitkata - kata.

Saya bosan, dan menghitung satu miliar iterasi dari tiga pendekatan. Kompiler adalah gcc -O3. CPU adalah apa pun yang mereka masukkan ke dalam gen 1 Macbook Pro.

Yang tercepat adalah yang berikut, pada 3,7 detik:

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

Tempat kedua pergi ke kode yang sama tetapi mencari 4 byte bukannya 2 kata setengah. Itu membutuhkan waktu sekitar 5,5 detik.

Tempat ketiga pergi ke pendekatan 'samping samping' sedikit-twiddling, yang membutuhkan 8,6 detik.

Tempat keempat adalah __builtin_popcount () GCC, pada 11 detik yang memalukan.

Pendekatan menghitung sedikit demi sedikit lebih lambat, dan saya bosan menunggu sampai selesai.

Jadi, jika Anda peduli dengan kinerja di atas segalanya, maka gunakan pendekatan pertama. Jika Anda peduli, tetapi tidak cukup untuk menghabiskan 64Kb RAM di atasnya, gunakan pendekatan kedua. Kalau tidak, gunakan pendekatan satu-bit-pada-waktu-baca yang dapat dibaca (tapi lambat)

Sulit untuk memikirkan situasi di mana Anda ingin menggunakan pendekatan bit-twiddling.

Sunting: Hasil serupa di sini .

Jika Anda menggunakan Java, metode bawaan Integer.bitCountakan melakukannya.

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

Biarkan saya jelaskan algoritma ini.

Algoritma ini didasarkan pada Divide and Conquer Algorithm. Misalkan ada bilangan bulat 8bit 213 (11010101 dalam biner), algoritmenya bekerja seperti ini (setiap kali menggabungkan dua blok tetangga):

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

Ini adalah salah satu pertanyaan di mana itu membantu untuk mengetahui arsitektur mikro Anda. Saya hanya menghitung waktu dua varian di bawah gcc 4.3.3 yang dikompilasi dengan -O3 menggunakan inline C ++ untuk menghilangkan overhead panggilan fungsi, satu miliar iterasi, menjaga jumlah berjalan dari semua jumlah untuk memastikan kompiler tidak menghapus sesuatu yang penting, menggunakan rdtsc untuk pengaturan waktu ( siklus clock tepat).

inline int pop2 (x tidak ditandatangani, tidak ditandatangani 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;
}

Hacker Delight yang tidak dimodifikasi membutuhkan waktu 12,2 gigacycles. Versi paralel saya (menghitung bit dua kali lebih banyak) berjalan dalam 13,0 gigacycles. Total 10,5 berlalu untuk keduanya secara bersamaan dengan Core Duo 2.4GHz. 25 gigacycles = lebih dari 10 detik pada frekuensi jam ini, jadi saya yakin timing saya tepat.

Ini ada hubungannya dengan rantai ketergantungan instruksi, yang sangat buruk untuk algoritma ini. Saya hampir bisa menggandakan kecepatan lagi dengan menggunakan sepasang register 64-bit. Bahkan, jika saya pintar dan menambahkan x + ya sedikit lebih cepat saya bisa mencukur beberapa shift. Versi 64-bit dengan beberapa tweak kecil akan keluar bahkan, tetapi menghitung bit dua kali lebih banyak lagi.

Dengan register 128 bit SIMD, satu lagi faktor dua, dan set instruksi SSE sering juga memiliki jalan pintas yang cerdas.

Tidak ada alasan untuk kode menjadi sangat transparan. Antarmuka sederhana, algoritme dapat direferensikan secara online di banyak tempat, dan dapat dilakukan uji unit yang komprehensif. Programmer yang menemukan itu bahkan mungkin belajar sesuatu. Operasi bit ini sangat alami pada level mesin.

OK, saya memutuskan untuk menggunakan versi 64-bit tweak. Untuk yang satu ini sizeof (unsigned long) == 8

inline int pop2 (panjang tak bertanda x, tak bertanda panjang y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x333333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x333333333333333333);
    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;
}

Kelihatannya benar (saya tidak menguji dengan hati-hati). Sekarang waktunya keluar pada 10,70 gigacycles / 14,1 gigacycles. Angka itu kemudian menjumlahkan 128 miliar bit dan sesuai dengan 5.9 yang berlalu pada mesin ini. Versi non-paralel mempercepat sedikit karena saya menjalankan dalam mode 64-bit dan suka register 64-bit sedikit lebih baik daripada register 32-bit.

Mari kita lihat apakah ada sedikit lebih banyak OOO pipelining yang bisa didapat di sini. Ini sedikit lebih terlibat, jadi saya benar-benar diuji sedikit. Setiap istilah saja berjumlah 64, semua jumlah gabungan menjadi 256.

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

Saya senang sesaat, tetapi ternyata gcc memainkan trik inline dengan -O3 meskipun saya tidak menggunakan kata kunci inline dalam beberapa tes. Ketika saya membiarkan trik bermain gcc, satu miliar panggilan ke pop4 () membutuhkan 12,56 gigacycles, tapi saya memutuskan itu melipat argumen sebagai ekspresi konstan. Angka yang lebih realistis tampaknya 19.6gc untuk 30% percepatan lainnya. Loop pengujian saya sekarang terlihat seperti ini, memastikan setiap argumen cukup berbeda untuk menghentikan gcc dari memainkan trik.

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

256 miliar bit dijumlahkan dalam 8.17s telah berlalu. Berfungsi untuk 1,02 detik untuk 32 juta bit sebagaimana dibandingkan dalam tabel 16-bit. Tidak dapat membandingkan secara langsung, karena bangku lainnya tidak memberikan kecepatan jam, tetapi sepertinya saya telah menampar ingot dari edisi tabel 64KB, yang merupakan penggunaan tragis dari cache L1 di tempat pertama.

Pembaruan: memutuskan untuk melakukan yang jelas dan membuat pop6 () dengan menambahkan empat baris duplikat. Datang ke 22,8gc, 384 miliar bit dijumlahkan dalam 9,5 yang telah berlalu. Jadi ada 20% lagi Sekarang pada 800ms untuk 32 miliar bit.

Mengapa tidak dibagi secara iteratif dengan 2?

hitung = 0
sementara n> 0
  if (n% 2) == 1
    hitung + = 1
  n / = 2  

Saya setuju bahwa ini bukan yang tercepat, tetapi "terbaik" agak ambigu. Saya berpendapat bahwa "terbaik" harus memiliki unsur kejelasan

Twiddling Hacker's Delight menjadi jauh lebih jelas ketika Anda menulis pola bit.

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

Langkah pertama menambahkan bit genap ke bit aneh, menghasilkan jumlah bit di masing-masing bit. Langkah-langkah lain menambahkan potongan-potongan tingkat tinggi ke potongan-potongan tingkat rendah, menggandakan ukuran potongan sepanjang jalan, sampai kita memiliki hitungan akhir mengambil seluruh int.

Untuk media senang antara tabel pencarian ³² dan iterasi melalui setiap bit secara individual:

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

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

Ini bisa dilakukan di O(k), di mana kjumlah bit diatur.

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

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

    return count;
}

Itu bukan solusi tercepat atau terbaik, tetapi saya menemukan pertanyaan yang sama di jalan saya, dan saya mulai berpikir dan berpikir. akhirnya saya menyadari bahwa itu dapat dilakukan seperti ini jika Anda mendapatkan masalah dari sisi matematika, dan menggambar grafik, maka Anda menemukan bahwa itu adalah fungsi yang memiliki beberapa bagian periodik, dan kemudian Anda menyadari perbedaan antara periode ... jadi ini dia:

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

Fungsi yang Anda cari sering disebut "jumlah sideways" atau "jumlah populasi" dari angka biner. Knuth membahasnya dalam pra-Fascicle 1A, hal11-12 (walaupun ada referensi singkat dalam Volume 2, 4.6.3- (7).)

The lokus classicus adalah artikel Peter Wegner "Sebuah Teknik untuk Ones Menghitung dalam Binary Computer", dari Komunikasi ACM , Volume 3 (1960) Nomor 5, halaman 322 . Dia memberikan dua algoritma berbeda di sana, satu dioptimalkan untuk angka yang diharapkan "jarang" (yaitu, memiliki sejumlah kecil) dan satu untuk kasus sebaliknya.

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

Beberapa pertanyaan terbuka: -

1. Jika angkanya negatif maka?
2. Jika jumlahnya 1024, maka metode "iteratif dibagi dengan 2" akan berulang sebanyak 10 kali.

kita dapat memodifikasi algo untuk mendukung angka negatif sebagai berikut: -

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

sekarang untuk mengatasi masalah kedua kita bisa menulis algo seperti: -

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

untuk referensi lengkap lihat:

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

Saya pikir metode Brian Kernighan akan berguna juga ... Itu melewati sebanyak iterasi karena ada bit yang ditetapkan. Jadi jika kita memiliki kata 32-bit dengan hanya set bit tinggi, maka itu hanya akan melewati loop.

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

Diterbitkan pada tahun 1988, Bahasa Pemrograman C 2nd Ed. (oleh Brian W. Kernighan dan Dennis M. Ritchie) menyebutkan ini dalam latihan 2-9. Pada 19 April 2006, Don Knuth menunjukkan kepada saya bahwa metode ini "pertama kali diterbitkan oleh Peter Wegner di CACM 3 (1960), 322. (Juga ditemukan secara independen oleh Derrick Lehmer dan diterbitkan pada 1964 dalam sebuah buku yang diedit oleh Beckenbach.)"

Saya menggunakan kode di bawah ini yang lebih intuitif.

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

Logika: n & (n-1) me-reset bit set terakhir dari n.

PS: Saya tahu ini bukan O (1) solusi, walaupun itu solusi yang menarik.

Apa maksud Anda dengan "Algoritma terbaik"? Kode singkat atau kode cepat? Kode Anda terlihat sangat elegan dan memiliki waktu eksekusi yang konstan. Kode ini juga sangat pendek.

Tetapi jika kecepatan adalah faktor utama dan bukan ukuran kode maka saya pikir tindak lanjutnya bisa lebih cepat:

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

Saya pikir ini tidak akan lebih cepat untuk nilai 64 bit tetapi nilai 32 bit bisa lebih cepat.

Saya menulis makro bitcount cepat untuk mesin RISC di sekitar tahun 1990. Tidak menggunakan aritmatika lanjutan (perkalian, pembagian,%), pengambilan memori (terlalu lambat), cabang (terlalu lambat), tetapi ia menganggap CPU memiliki 32-bit barrel shifter (dengan kata lain, >> 1 dan >> 32 mengambil jumlah siklus yang sama.) Asumsinya adalah bahwa konstanta kecil (seperti 6, 12, 24) tidak memerlukan biaya apa pun untuk dimuat ke register, atau disimpan di temporaries dan digunakan kembali berulang-ulang.

Dengan asumsi ini, ia menghitung 32 bit dalam sekitar 16 siklus / instruksi pada kebanyakan mesin RISC. Perhatikan bahwa 15 instruksi / siklus dekat dengan batas bawah pada jumlah siklus atau instruksi, karena tampaknya mengambil setidaknya 3 instruksi (mask, shift, operator) untuk memotong jumlah penambahan menjadi setengah, jadi log_2 (32) = 5, 5 x 3 = 15 instruksi adalah quasi-lowerbound.

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

Inilah rahasia untuk langkah pertama dan paling rumit:

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

jadi jika saya mengambil kolom 1 (A) di atas, geser ke kanan 1 bit, dan kurangi dari AB, saya mendapatkan output (CD). Ekstensi ke 3 bit serupa; Anda dapat memeriksanya dengan tabel boolean 8 baris seperti milik saya di atas jika diinginkan.

• Don Gillies

jika Anda menggunakan C ++ opsi lain adalah menggunakan metaprogramming template:

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

penggunaan akan:

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

Anda tentu saja dapat memperluas templat ini untuk menggunakan berbagai jenis (bahkan ukuran bit pendeteksi otomatis) tapi saya tetap membuatnya mudah untuk kejelasan.

sunting: lupa menyebutkan ini bagus karena harus bekerja di kompiler C ++ dan pada dasarnya hanya membuka gulungan Anda untuk Anda jika nilai konstan digunakan untuk jumlah bit (dengan kata lain, saya cukup yakin itu adalah metode umum tercepat Anda akan menemukan)

Saya sangat menyukai contoh ini dari file keberuntungan:

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

Saya suka yang terbaik karena sangat cantik!

Java JDK1.5

Integer.bitCount (n);

di mana n adalah angka yang 1-nya harus dihitung.

periksa juga,

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

Saya menemukan implementasi penghitungan bit dalam array dengan menggunakan instruksi SIMD (SSSE3 dan AVX2). Ini memiliki kinerja 2-2,5 kali lebih baik daripada jika akan menggunakan fungsi intrinsik __popcnt64.

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

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

Saya selalu menggunakan ini dalam Pemrograman Kompetitif dan mudah untuk menulis dan efisien:

#include <bits/stdc++.h>

using namespace std;

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

Ada banyak algoritma untuk menghitung bit yang ditetapkan; tapi saya pikir yang terbaik adalah yang lebih cepat! Anda dapat melihat detailnya di halaman ini:

Bit Twiddling Hacks

Saya menyarankan yang ini:

Menghitung bit yang diatur dalam kata-kata 14, 24, atau 32-bit menggunakan instruksi 64-bit

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;

Metode ini membutuhkan CPU 64-bit dengan divisi modulus cepat agar efisien. Opsi pertama hanya membutuhkan 3 operasi; opsi kedua membutuhkan 10; dan opsi ketiga memakan waktu 15.

Solusi C # cepat menggunakan tabel jumlah bit Byte yang dihitung sebelumnya dengan percabangan pada ukuran input.

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

Berikut ini adalah modul portabel (ANSI-C) yang dapat membandingkan setiap algoritma Anda pada arsitektur apa pun.

CPU Anda memiliki 9 bit byte? Tidak masalah :-) Saat ini mengimplementasikan 2 algoritma, algoritma K&R dan tabel pencarian byte yang bijaksana. Tabel pencarian rata-rata 3 kali lebih cepat dari algoritma K&R. Jika seseorang dapat menemukan cara untuk membuat algoritma "Hacker's Delight" portabel jangan ragu untuk menambahkannya.

#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

apa yang bisa kamu lakukan adalah

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

logika di balik ini adalah bit n-1 terbalik dari bit set paling kanan dari n. jika n = 6 yaitu 110 maka 5 adalah 101 bit dibalik dari bit set paling kanan dari n. jadi jika kita & dua ini kita akan membuat bit paling kanan 0 di setiap iterasi dan selalu pergi ke bit set paling kanan berikutnya. Oleh karena itu, menghitung bit yang ditetapkan. Kompleksitas waktu terburuk akan menjadi O (logn) ketika setiap bit diatur.