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


8 bit mewakili tampilan nomor 7 seperti ini:

00000111

Tiga bit ditetapkan.

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


751


asal


Jawaban:


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

Algoritme 'terbaik' sangat tergantung pada CPU yang Anda gunakan dan apa pola penggunaan Anda.

Beberapa CPU memiliki satu instruksi built-in untuk melakukannya dan yang lainnya memiliki instruksi paralel yang bekerja pada vektor bit. Instruksi paralel (seperti x86's popcnt, pada CPU yang didukung) hampir pasti akan menjadi 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 lingkaran yang ketat. Namun itu bisa menderita karena biaya 'cache miss', di mana CPU harus mengambil beberapa tabel dari memori utama.

Jika Anda tahu bahwa byte Anda akan kebanyakan 0 atau kebanyakan 1 maka ada algoritma yang sangat efisien untuk skenario ini.

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

int numberOfSetBits(int i)
{
     // Java: 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;
}

Ini memiliki perilaku terburuk dari salah satu algoritma yang dibahas, jadi akan secara efisien menangani semua pola penggunaan atau nilai yang Anda lempar.


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

Namun, cara terbaik untuk menggunakan instruksi vektor untuk popcount biasanya dengan menggunakan variabel-shuffle untuk melakukan pencarian tabel untuk 4 bit pada saat setiap byte secara paralel. (Indeks 4 bit, 16 tabel entri yang disimpan dalam register vektor).

Pada CPU Intel, perangkat keras 64bit instruksi popcnt dapat mengungguli SSSE3 PSHUFB implementasi bit-paralel oleh sekitar faktor 2, tetapi hanya jika kompiler Anda mendapatkannya dengan benar. Jika tidak, SSE dapat keluar secara signifikan ke depan. Versi kompiler baru menyadari adanya popcnt ketergantungan palsu  masalah 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)


764



Juga pertimbangkan fungsi built-in dari kompiler Anda.

Pada kompiler GNU misalnya Anda hanya dapat 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 compiler akan memancarkan instruksi cpu untuk melakukan pekerjaan yang sama lebih cepat.

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


Pada x86, Anda dapat memberi tahu compiler yang dapat diasumsikan mendukung popcnt instruksi dengan -mpopcnt atau -msse4.2 untuk juga mengaktifkan instruksi vektor yang ditambahkan pada generasi yang sama. Lihat Opsi x86 GCC. -march=nehalem (atau -march= CPU apa pun yang Anda inginkan untuk diasumsikan dan diperbaiki oleh kode Anda) dapat menjadi pilihan yang baik. Menjalankan biner yang dihasilkan pada CPU yang lebih lama akan menghasilkan kesalahan instruksi ilegal.

Untuk membuat binari yang dioptimalkan untuk mesin yang Anda buat, gunakan -march=native  (dengan gcc, clang, atau ICC).

MSVC menyediakan intrinsik untuk x86 popcnt petunjuk, tetapi tidak seperti gcc, ini benar-benar intrinsik untuk instruksi perangkat keras dan memerlukan dukungan perangkat keras.


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

Secara teori, setiap compiler yang mengetahui bagaimana popcount secara efisien untuk CPU target harus mengekspos fungsionalitas itu melalui ISO C ++ std::bitset<>. Dalam prakteknya, 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 compiler memiliki std::bitset yang memanfaatkannya saat tersedia. Misalnya, MSVC tidak memiliki cara untuk mengaktifkan popcnt dukungan pada waktu kompilasi, dan selalu digunakan pencarian tabel, bahkan dengan /Ox /arch:AVX (yang berarti SSE4.2, meskipun secara teknis ada bit fitur terpisah untuk popcnt.)

Tapi setidaknya Anda mendapatkan sesuatu yang portabel yang berfungsi di mana saja, dan dengan gcc / clang 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 penjelajah kompiler Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt memancarkan 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++11 memancarkan (untuk int versi arg):

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

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

Juga catat bahwa gcc's fallback untuk arsitektur tanpa single-instruction popcount adalah pencarian tabel byte-on-a-time. Ini tidak bagus untuk ARM, misalnya.


185



Menurut 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 terpintar yang telah disediakan beberapa orang tetapi saya lebih suka keterbacaan atas 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 menginginkan lebih banyak kecepatan (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 itu. Namun, karena banyak pengoptimalan kinerja tidak portabel, itu mungkin bukan masalah. Jika Anda ingin mudah dibawa, saya akan tetap menggunakan solusi yang mudah dibaca.


168



Dari Delight Hacker, hal. 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;
}

Eksekusi dalam instruksi ~ 20-ish (arch dependent), tidak ada percabangan.

Kegembiraan Hacker  aku s menyenangkan! Sangat dianjurkan.


94



Saya pikir cara tercepat - tanpa menggunakan tabel pencarian dan popcount—adalah yang berikut. Ini menghitung set bit 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 bit yang ditetapkan dengan membagi dalam dua bagian, menghitung jumlah bit yang ditetapkan di kedua bagian dan kemudian menambahkannya. Juga dikenal sebagai Divide and Conquer paradigma. Mari detailnya ..

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

Jumlah bit dalam dua bit bisa 0b00, 0b01 atau 0b10. Mari kita coba untuk melakukan ini pada 2 bit ..

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

Ini adalah apa yang diperlukan: kolom terakhir menunjukkan hitungan bit yang diatur dalam setiap pasangan dua bit. Jika dua nomor bit itu >= 2 (0b10) kemudian and menghasilkan 0b01, kalau tidak menghasilkan 0b00.

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

Pernyataan ini harus mudah dimengerti. Setelah operasi pertama kita memiliki hitungan bit-bit yang diatur dalam setiap dua bit, sekarang kita simpulkan hitungan itu dalam setiap 4 bit.

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

Kami kemudian menjumlahkan hasil di atas, memberi kami jumlah total set bit dalam 4 bit. Pernyataan terakhir adalah yang paling rumit.

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

Mari kita jabarkan lebih lanjut ...

v + (v >> 4)

Ini mirip dengan pernyataan kedua; kami menghitung set bit dalam kelompok 4 sebagai gantinya. Kami tahu — karena operasi kami sebelumnya — bahwa setiap nibble memiliki hitungan bit set di dalamnya. Mari kita lihat contohnya. Misalkan kita memiliki byte 0b01000010. Ini berarti nibble pertama memiliki set 4bits dan yang kedua memiliki set 2bits. Sekarang kita tambahkan camilan itu bersama.

0b01000010 + 0b01000000

Ini memberi kita hitungan bit set dalam satu byte, pada nibble pertama 0b01100010 dan karena itu kami menutupi empat byte terakhir dari semua byte dalam nomor (membuangnya).

0b01100010 & 0xF0 = 0b01100000

Sekarang setiap byte memiliki hitungan bit set di dalamnya. Kita perlu menambahkan semuanya bersama. Caranya adalah dengan mengalikan hasilnya dengan 0b10101010 yang memiliki properti yang menarik. Jika nomor kami memiliki empat byte, A B C D, itu akan menghasilkan nomor baru dengan byte ini A+B+C+D B+C+D C+D D. Bilangan 4 byte dapat memiliki maksimum 32 bit set, yang dapat direpresentasikan sebagai 0b00100000.

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


69



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

Tercepat adalah sebagai 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 menggunakan kode yang sama tetapi mencari 4 byte bukannya 2 halfwords. Itu membutuhkan waktu sekitar 5,5 detik.

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

Tempat keempat pergi ke GCC's __builtin_popcount (), pada 11 detik yang memalukan.

Penghitungan pendekatan satu-bit-pada-waktu adalah lebih lambat, dan saya bosan menunggu untuk menyelesaikannya.

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

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

Edit: Hasil serupa sini.


53



Jika Anda menggunakan Java, metode built-in Integer.bitCount akan melakukan itu.


52



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

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);
    kembali (x + y) & 0x000000FF;
}

The Hacker Delight yang tidak dimodifikasi menghabiskan 12,2 gigacycles. Versi paralel saya (menghitung dua kali lebih banyak bit) berjalan dalam 13,0 gigacycles. 10.5 total waktu berlalu untuk keduanya bersama-sama pada 2.4GHz Core Duo. 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 + y sedikit lebih cepat saya dapat mencukur beberapa perubahan. Versi 64-bit dengan beberapa tweak kecil akan keluar sekitar genap, tetapi menghitung dua kali lebih banyak bit lagi.

Dengan 128 bit SIMD register, tetapi faktor lain dari dua, dan set instruksi SSE sering memiliki jalan pintas pintar juga.

Tidak ada alasan untuk kode menjadi sangat transparan. Antarmukanya sederhana, algoritmanya dapat dirujuk secara on-line di banyak tempat, dan itu cocok untuk uji unit komprehensif. Programmer yang tersandung padanya bahkan mungkin belajar sesuatu. Operasi bit ini sangat alami di tingkat mesin.

OK, saya memutuskan untuk me-bench versi 64-bit yang di-tweak. Untuk ukuran yang satu ini (tidak bertanda panjang) == 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);
    kembalikan x & 0xFF;
}

Itu terlihat benar (saya tidak menguji dengan hati-hati, meskipun). Sekarang timing keluar pada 10.70 gigacycles / 14.1 gigacycles. Angka yang kemudian dijumlahkan 128 miliar bit dan sesuai dengan 5,9 detik yang terlewati pada mesin ini. Versi non-paralel mempercepat sedikit karena saya sedang menjalankan dalam mode 64-bit dan itu suka register 64-bit sedikit lebih baik dari register 32-bit.

Mari kita lihat apakah ada sedikit lebih banyak pipelining OOO yang bisa didapat di sini. Ini sedikit lebih terlibat, jadi saya benar-benar diuji sedikit. Setiap istilah saja berjumlah 64, semua jumlah gabungan hingga 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);
    kembalikan x & 0x000001FF;
}

Saya senang sesaat, tetapi ternyata gcc sedang bermain trik inline dengan -O3 meskipun saya tidak menggunakan kata kunci inline dalam beberapa tes. Ketika saya membiarkan gcc bermain trik, satu miliar panggilan ke pop4 () membutuhkan 12,56 gigacycles, tetapi saya memutuskan itu melipat argumen sebagai ekspresi konstan. Jumlah yang lebih realistis tampaknya 19.6gc untuk 30% lebih cepat. Lingkaran percobaan saya sekarang terlihat seperti ini, memastikan setiap argumen cukup berbeda untuk menghentikan gcc dari bermain 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 pada 8.17 berlalu. Berfungsi hingga 1.02s untuk 32 juta bit sebagai patokan dalam pencarian tabel 16-bit. Tidak dapat dibandingkan secara langsung, karena bangku yang lain tidak memberikan kecepatan clock, tetapi sepertinya saya telah menampar ingus keluar dari edisi meja 64KB, yang merupakan penggunaan L1 cache yang tragis di tempat pertama.

Pembaruan: memutuskan untuk melakukan yang jelas dan membuat pop6 () dengan menambahkan empat baris duplikat. Sampai dengan 22.8gc, 384 miliar bit dijumlahkan dalam 9.5s berlalu. Jadi ada 20% lagi Sekarang di 800ms untuk 32 miliar bit.


28



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

Biar saya jelaskan algoritma ini.

Algoritma ini didasarkan pada Divide and Conquer Algorithm. Misalkan ada 8bit integer 213 (11010101 dalam biner), algoritma 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)
+-------------------------------+

28