Come contare il numero di bit impostati in un numero intero a 32 bit?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
8 bit che rappresentano il numero 7 assomigliano a questo:
00000111
Sono impostati tre bit.
Quali sono gli algoritmi per determinare il numero di bit impostati in un numero intero a 32 bit?
Soluzione
Questo è noto come ' Peso di Hamming ', 'popcount' o 'aggiunta laterale' .
L'algoritmo "migliore" dipende in realtà dalla CPU in uso e dal modello di utilizzo.
Alcune CPU hanno una singola istruzione incorporata per farlo e altre hanno istruzioni parallele che agiscono su vettori di bit. Le istruzioni parallele (come x86 popcnt, sulle CPU in cui è supportato) saranno quasi sicuramente più veloci. Alcune altre architetture potrebbero avere un'istruzione lenta implementata con un ciclo microcodificato che verifica un po 'per ciclo ( citazione necessaria ).
Un metodo di ricerca di una tabella precompilata può essere molto veloce se la tua CPU ha una cache di grandi dimensioni e / o stai facendo molte di queste istruzioni in un ciclo stretto. Tuttavia può soffrire a causa del costo di un 'cache miss', in cui la CPU deve recuperare parte della tabella dalla memoria principale.
Se sai che i tuoi byte saranno per lo più 0 o principalmente 1, allora ci sono algoritmi molto efficienti per questi scenari.
Credo che un ottimo algoritmo di uso generale sia il seguente, noto come "algoritmo SWAR a precisione parallela". L'ho espresso in uno pseudo linguaggio simile a C, potrebbe essere necessario modificarlo per funzionare con un linguaggio specifico (ad esempio utilizzando uint32_t per C ++ e & Gt; & Gt; & Gt; in 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;
}
Questo ha il miglior comportamento nel caso peggiore di uno qualsiasi degli algoritmi discussi, quindi affronterà in modo efficiente qualsiasi modello di utilizzo o valore che gli viene lanciato.
Questo algoritmo bitwise-SWAR potrebbe essere parallelizzato per essere eseguito in più elementi vettoriali contemporaneamente, anziché in un unico registro intero, per un aumento di velocità su CPU con SIMD ma nessuna istruzione popcount utilizzabile. (ad es. codice x86-64 che deve essere eseguito su qualsiasi CPU, non solo Nehalem o successivo.)
Tuttavia, il modo migliore per utilizzare le istruzioni vettoriali per popcount è di solito usando una variabile shuffle per fare una ricerca di tabella per 4 bit alla volta di ogni byte in parallelo. (I 4 bit indicizzano una tabella di 16 voci contenuta in un registro vettoriale).
Sulle CPU Intel, l'istruzione popcnt hardware a 64 bit può superare un SSSE3 PSHUFB bit- implementazione parallela di circa un fattore 2, ma solo se il tuo compilatore ha capito bene . Altrimenti SSE può venire fuori in modo significativo. Le versioni più recenti del compilatore sono a conoscenza della popcnt falsa dipendenza problema su Intel .
References:
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)
Altri suggerimenti
Considera anche le funzioni integrate dei tuoi compilatori.
Ad esempio sul compilatore GNU puoi semplicemente usare:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
Nel peggiore dei casi il compilatore genererà una chiamata a una funzione. Nel migliore dei casi il compilatore emetterà un'istruzione cpu per fare lo stesso lavoro più velocemente.
Gli intrinseci di GCC funzionano anche su più piattaforme. Popcount diventerà mainstream nell'architettura x86, quindi ha senso iniziare a usare l'intrinseca ora. Altre architetture hanno il popcount per anni.
Su x86, puoi dire al compilatore che può assumere il supporto per popcnt istruzioni con -mpopcnt o -msse4.2 per abilitare anche le istruzioni vettoriali che sono state aggiunte nella stessa generazione. Vedi Opzioni GCC x86 . -march=nehalem (o -march= qualunque CPU si desideri assumere e ottimizzare il codice) potrebbe essere una buona scelta. L'esecuzione del binario risultante su una CPU precedente comporterà un errore di istruzione illegale.
Per rendere i binari ottimizzati per la macchina su cui li costruisci, usa -march=native (con gcc, clang o ICC).
MSVC fornisce un valore intrinseco per l'istruzione x86 std::bitset<>::count() , ma a differenza di gcc è davvero intrinseco per le istruzioni hardware e richiede supporto hardware.
Utilizzo di std::bitset<> invece di un incorporato
In teoria, qualsiasi compilatore che sappia contare in modo efficiente per la CPU di destinazione dovrebbe esporre tale funzionalità tramite ISO C ++ std::bitset . In pratica, potresti stare meglio con il bit-hack AND / shift / ADD in alcuni casi per alcune CPU di destinazione.
Per le architetture di destinazione in cui il popcount hardware è un'estensione opzionale (come x86), non tutti i compilatori hanno un /Ox /arch:AVX che ne approfitta quando disponibile. Ad esempio, MSVC non ha modo di abilitare gcc -O3 -std=gnu++11 -mpopcnt supporto in fase di compilazione e usa sempre una ricerca di tabella , anche con gcc -O3 -std=gnu++11 (che implica SSE4.2, sebbene tecnicamente sia presente un bit di funzionalità separato per int.)
Ma almeno ottieni qualcosa di portatile che funziona ovunque, e con gcc / clang con le giuste opzioni di destinazione, ottieni un popcount hardware per architetture che lo supportano.
#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();
}
Vedere asm da gcc, clang, ICC, e MSVC sul compilatore explorer Godbolt.
x86-64 <=> emette questo:
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
Emissione di PowerPC64 <=> (per la <=> versione arg):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
Questa fonte non è specifica per x86 o GNU, ma si compila bene solo per x86 con gcc / clang / icc.
Si noti inoltre che il fallback di gcc per architetture senza popcount a istruzione singola è una ricerca di tabella byte alla volta. Questo non è meraviglioso per ARM, ad esempio .
Secondo me, il " best " la soluzione è quella che può essere letta da un altro programmatore (o dal programmatore originale due anni dopo) senza commenti copiosi. Potresti desiderare la soluzione più veloce o più intelligente che alcuni hanno già fornito, ma preferisco la leggibilità all'intelligenza in qualsiasi momento.
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;
}
Se vuoi maggiore velocità (e supponendo che lo documenti bene per aiutare i tuoi successori), puoi usare una ricerca da tavolo:
// 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);
}
Anche se questi si basano su dimensioni di tipi di dati specifici, quindi non sono così portatili. Tuttavia, poiché molte ottimizzazioni delle prestazioni non sono comunque portatili, ciò potrebbe non essere un problema. Se vuoi la portabilità, mi atterrei alla soluzione leggibile.
From Hacker's Delight, p. 66, Figura 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;
}
Esegue in ~ 20-ish istruzioni (dipendenti dall'arco), senza diramazioni.
Hacker's Delight è delizioso! Altamente raccomandato.
Penso che il modo più veloce & # 8212; senza usare le tabelle di ricerca e popcount & # 8212; è il seguente. Conta i bit impostati con solo 12 operazioni.
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;
}
Funziona perché puoi contare il numero totale di bit impostati dividendoli in due metà, contando il numero di bit impostati in entrambe le metà e quindi sommandoli. Conosciuto anche come Divide and Conquer paradigma. Entriamo nel dettaglio ..
v = v - ((v >> 1) & 0x55555555);
Il numero di bit in due bit può essere 0b00, 0b01 o 0b10. Proviamo a risolverlo su 2 bit ..
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
Questo è ciò che era richiesto: l'ultima colonna mostra il conteggio dei bit impostati in ogni coppia di due bit. Se il numero di due bit è >= 2 (0b10), and produce 0b01000010, altrimenti produce 0b01100010.
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
Questa affermazione dovrebbe essere facile da capire. Dopo la prima operazione abbiamo il conteggio dei bit impostati in ogni due bit, ora riassumiamo quel conteggio ogni 4 bit.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
Riassumiamo quindi il risultato sopra riportato, dandoci il conteggio totale dei bit impostati in 4 bit. L'ultima affermazione è la più complicata.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Analizziamo ulteriormente ...
v + (v >> 4)
È simile alla seconda affermazione; contiamo invece i bit impostati in gruppi di 4. Sappiamo & # 8212; a causa delle nostre precedenti operazioni & # 8212; che ogni bocconcino ha il conteggio dei bit impostati in esso. Diamo un esempio. Supponiamo di avere il byte 0b10101010. Significa che il primo bocconcino ha i suoi 4 bit impostati e il secondo ha i suoi 2 bit impostati. Ora aggiungiamo insieme questi stuzzichini.
0b01000010 + 0b01000000
Ci fornisce il conteggio dei bit impostati in un byte, nel primo nibble A B C D e quindi mascheriamo gli ultimi quattro byte di tutti i byte nel numero (scartandoli).
0b01100010 & 0xF0 = 0b01100000
Ora ogni byte contiene il conteggio dei bit impostati. Dobbiamo sommarli tutti insieme. Il trucco è moltiplicare il risultato per A+B+C+D B+C+D C+D D che ha una proprietà interessante. Se il nostro numero ha quattro byte, 0b00100000, si otterrà un nuovo numero con questi byte >> 24. Un numero di 4 byte può avere un massimo di 32 bit impostati, che possono essere rappresentati come 32 bit.
Tutto ciò di cui abbiamo bisogno ora è il primo byte che ha la somma di tutti i bit impostati in tutti i byte e lo otteniamo per 64 bit. Questo algoritmo è stato progettato per <=> parole ma può essere facilmente modificato per <=> parole.
Se usi Java, il metodo integrato Integer.bitCount lo farà.
Mi sono annoiato e ho cronometrato un miliardo di iterazioni di tre approcci. Il compilatore è gcc -O3. La CPU è qualunque cosa abbiano inserito nel Macbook Pro di prima generazione.
Il più veloce è il seguente, a 3,7 secondi:
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] );
}
Il secondo posto va allo stesso codice ma cerca 4 byte anziché 2 mezze parole. Ci sono voluti circa 5,5 secondi.
Il terzo posto va all'approccio "aggiunta laterale" che ha richiesto 8,6 secondi.
Il quarto posto va a __builtin_popcount () di GCC, a 11 vergognosi secondi.
L'approccio del conteggio bit per volta era molto più lento e mi sono stufato di aspettare che si completasse.
Quindi, se ti preoccupi delle prestazioni sopra ogni altra cosa, usa il primo approccio. Se ti interessa, ma non abbastanza da spendere 64 KB di RAM, usa il secondo approccio. Altrimenti usa l'approccio leggibile (ma lento) un bit alla volta.
È difficile pensare a una situazione in cui vorresti usare l'approccio bit-twiddling.
Modifica: risultati simili qui .
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;
}
Lasciami spiegare questo algoritmo.
Questo algoritmo si basa su Divide and Conquer Algorithm. Supponiamo che esista un numero intero a 8 bit 213 (11010101 in binario), l'algoritmo funziona in questo modo (ogni volta unisci due blocchi vicini):
+-------------------------------+
| 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)
+-------------------------------+
Questa è una di quelle domande in cui aiuta a conoscere la tua microarchitettura. Ho appena cronometrato due varianti sotto gcc 4.3.3 compilate con -O3 usando C ++ inline per eliminare l'overhead della chiamata di funzione, un miliardo di iterazioni, mantenendo la somma corrente di tutti i conteggi per garantire che il compilatore non rimuova nulla di importante, usando rdtsc per il timing ( ciclo dell'orologio preciso).
inline int pop2(unsigned x, unsigned y)
{
x = x - ((x >> 1) & 0x55555555);
y = y - ((y >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
return (x+y) & 0x000000FF;
}
L'Hacker's Delight non modificato ha preso 12.2 gigacycles. La mia versione parallela (contando il doppio del numero di bit) gira in 13.0 gigacycles. 10.5s totali trascorsi per entrambi insieme su un Core Duo a 2,4 GHz. 25 gigacycles = poco più di 10 secondi a questa frequenza di clock, quindi sono sicuro che i miei tempi siano corretti.
Questo ha a che fare con le catene di dipendenza delle istruzioni, che sono molto dannose per questo algoritmo. Potrei quasi raddoppiare la velocità usando una coppia di registri a 64 bit. In effetti, se fossi intelligente e aggiungessi x + y un po 'prima potrei radere alcuni cambiamenti. La versione a 64 bit con alcune piccole modifiche sarebbe risultata uniforme, ma conterebbe di nuovo il doppio dei bit.
Con i registri SIMD a 128 bit, ancora un altro fattore due, e i set di istruzioni SSE spesso hanno anche scorciatoie intelligenti.
Non c'è motivo per cui il codice sia particolarmente trasparente. L'interfaccia è semplice, l'algoritmo può essere referenziato on-line in molti luoghi ed è suscettibile di test unitari completi. Il programmatore che inciampa su di esso potrebbe persino imparare qualcosa. Queste operazioni con i bit sono estremamente naturali a livello di macchina.
OK, ho deciso di mettere in panchina la versione ottimizzata a 64 bit. Per questa dimensione di (unsigned long) == 8
inline int pop2(unsigned long x, unsigned long y)
{
x = x - ((x >> 1) & 0x5555555555555555);
y = y - ((y >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0xFF;
}
Sembra giusto (non sto testando attentamente, però). Ora i tempi escono a 10.70 gigacicli / 14.1 gigacicli. Quel numero successivo ha sommato 128 miliardi di bit e corrisponde ai 5,9 trascorsi su questa macchina. La versione non parallela accelera un po 'perché sto funzionando in modalità 64 bit e preferisce i registri a 64 bit leggermente migliori dei registri a 32 bit.
Vediamo se c'è un po 'più di pipeline di OOO da avere qui. Questo è stato un po 'più coinvolto, quindi in realtà ho provato un po'. Ogni termine da solo ammonta a 64, tutti sommati a 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;
}
Sono stato eccitato per un momento, ma risulta che gcc sta giocando inline con -O3 anche se non sto usando la parola chiave inline in alcuni test. Quando lascio che gcc giochi, un miliardo di chiamate a pop4 () richiede 12,56 gigacicli, ma ho deciso che piegava gli argomenti come espressioni costanti. Un numero più realistico sembra essere 19,6 gc per un altro 30% di accelerazione. Il mio ciclo di prova ora assomiglia a questo, assicurandomi che ogni argomento sia abbastanza diverso da impedire a gcc di giocare brutti scherzi.
hitime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
hitime e4 = rdtsc();
Sono trascorsi 256 miliardi di bit sommati in 8,17 secondi. Risolve a 1,02 secondi per 32 milioni di bit come indicato nella ricerca della tabella a 16 bit. Non è possibile confrontare direttamente, perché l'altra panchina non fornisce una velocità di clock, ma sembra che io abbia schiaffeggiato la versione da tavolo da 64 KB, che è un tragico uso della cache L1 in primo luogo.
Aggiornamento: ha deciso di fare l'ovvio e creare pop6 () aggiungendo altre quattro linee duplicate. È arrivato a 22,8 gc, sono trascorsi 384 miliardi di bit sommati in 9,5 secondi. Quindi c'è un altro 20% ora a 800 ms per 32 miliardi di bit.
Perché non dividere iterativamente per 2?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
Sono d'accordo che questo non è il più veloce, ma " best " è alquanto ambiguo. Direi comunque che & Quot; best & Quot; dovrebbe avere un elemento di chiarezza
La delizia a bit di Hacker's Delight diventa molto più chiara quando si scrivono i pattern di 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;
}
Il primo passo aggiunge i bit pari ai bit dispari, producendo una somma di bit in ciascuno di essi. Gli altri passaggi aggiungono blocchi di ordine superiore a blocchi di ordine inferiore, raddoppiando la dimensione del blocco fino a quando non abbiamo il conteggio finale che occupa l'intero int.
Per un mezzo felice tra una tabella di ricerca 2 32 e iterando ogni singolo bit:
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;
}
Non è la soluzione più veloce o migliore, ma ho trovato la stessa domanda sulla mia strada e ho iniziato a pensare e pensare. alla fine mi sono reso conto che può essere fatto in questo modo se si ottiene il problema dal punto di vista matematico e si traccia un grafico, quindi si scopre che è una funzione che ha una parte periodica e quindi si comprende la differenza tra i periodi ... quindi ecco qui:
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);
}
}
Questo può essere fatto in O(k), dove k è il numero di bit impostati.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
La funzione che stai cercando è spesso chiamata " sideways sum " oppure " conteggio della popolazione " di un numero binario. Knuth ne discute in Pre-Fascicle 1A, pp11-12 (sebbene ci fosse un breve riferimento nel Volume 2, 4.6.3- (7).)
Il locus classicus è l'articolo di Peter Wegner " Una tecnica per contare quelli in un computer binario " ;, dal Comunicazioni dell'ACM , Volume 3 (1960) Numero 5, pagina 322 . Fornisce lì due diversi algoritmi, uno ottimizzato per i numeri che dovrebbero essere & Quot; sparse & Quot; (vale a dire, hanno un numero limitato di quelli) e uno per il caso opposto.
Poche domande aperte: -
- Se il numero è negativo, allora?
- Se il numero è 1024, allora il " dividere iterativamente per 2 " il metodo ripeterà 10 volte.
possiamo modificare l'algo per supportare il numero negativo come segue: -
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
ora per superare il secondo problema possiamo scrivere l'algo come: -
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
per riferimento completo vedi:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
private int get_bits_set(int v)
{
int c; // c accumulates the total bits set in v
for (c = 0; v>0; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c;
}
Penso che anche il metodo Brian Kernighan sarà utile ... Attraversa tante iterazioni quanti sono i bit impostati. Quindi, se abbiamo una parola a 32 bit con solo il bit alto impostato, passerà solo una volta nel ciclo.
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;
}
Pubblicato nel 1988, il C Programming Language 2nd Ed. (di Brian W. Kernighan e Dennis M. Ritchie) lo menziona nell'esercizio 2-9. Il 19 aprile 2006 Don Knuth mi ha fatto notare che questo metodo è stato pubblicato per la prima volta da Peter Wegner in CACM 3 (1960), 322. (Anche scoperto in modo indipendente da Derrick Lehmer e pubblicato nel 1964 in un libro edito da Beckenbach) quot. &;
Uso il codice seguente che è più intuitivo.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Logica: n & amp; (n-1) ripristina l'ultimo bit impostato di n.
P.S: So che questa non è una soluzione O (1), sebbene sia una soluzione interessante.
Cosa intendi con " Miglior algoritmo " ;? Il codice abbreviato o il codice digiuno? Il tuo codice sembra molto elegante e ha un tempo di esecuzione costante. Anche il codice è molto breve.
Ma se la velocità è il fattore principale e non la dimensione del codice, penso che quanto segue possa essere più veloce:
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 );
}
Penso che questo non sarà più veloce per un valore di 64 bit ma un valore di 32 bit può essere più veloce.
Ho scritto una macro bitcount veloce per le macchine RISC nel 1990 circa. Non usa l'aritmetica avanzata (moltiplicazione, divisione,%), recuperi di memoria (troppo lenti), rami (troppo lenti), ma presuppone che il La CPU ha un cambio a barilotto a 32 bit (in altre parole, & Gt; & Gt; 1 e & Gt; & Gt; 32 richiedono la stessa quantità di cicli.) Si assume che le piccole costanti ( come 6, 12, 24) non costano nulla da caricare nei registri o sono memorizzati in temporanei e riutilizzati più volte.
Con questi presupposti, conta 32 bit in circa 16 cicli / istruzioni sulla maggior parte delle macchine RISC. Si noti che 15 istruzioni / cicli si avvicinano a un limite inferiore del numero di cicli o istruzioni, poiché sembra che occorrano almeno 3 istruzioni (maschera, spostamento, operatore) per dimezzare il numero di addend, quindi log_2 (32) = 5, 5 x 3 = 15 istruzioni è un limite quasi inferiore.
#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;
Ecco un segreto per il primo e più complesso passaggio:
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
quindi se prendo la prima colonna (A) sopra, la sposto a destra di 1 bit e la sottraggo da AB, ottengo l'output (CD). L'estensione a 3 bit è simile; puoi controllarlo con un tavolo booleano a 8 file come il mio sopra, se lo desideri.
- Don Gillies
se stai usando C ++ un'altra opzione è usare la metaprogrammazione dei 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;
}
l'utilizzo sarebbe:
// 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 )
puoi ovviamente espandere ulteriormente questo modello per usare diversi tipi (anche con la dimensione del bit con rilevazione automatica) ma l'ho tenuto semplice per chiarezza.
modifica: ho dimenticato di menzionare che è buono perché dovrebbe funzionare in qualsiasi compilatore C ++ e sostanzialmente srotola il tuo ciclo per te se viene usato un valore costante per il conteggio dei bit (in altre parole, sono abbastanza sicuro che sia il metodo generale più veloce che troverai)
Sono particolarmente affezionato a questo esempio dal file di fortuna:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
Mi piace di più perché è così carino!
Java JDK1.5
Integer.bitCount (n);
dove n è il numero i cui 1 devono essere contati.
controlla anche
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);
}
Ho trovato un'implementazione del conteggio dei bit in un array con l'utilizzo delle istruzioni SIMD (SSSE3 e AVX2). Ha prestazioni 2-2,5 volte migliori rispetto a quando utilizzerà la funzione intrinseca __popcnt64.
Versione 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];
}
Versione 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];
}
Lo uso sempre nella programmazione competitiva ed è facile da scrivere ed efficiente:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
Esistono molti algoritmi per contare i bit impostati; ma penso che il migliore sia il più veloce! Puoi vedere i dettagli in questa pagina:
Suggerisco questo:
Bit di conteggio impostati in parole di 14, 24 o 32 bit usando le istruzioni a 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;
Questo metodo richiede una CPU a 64 bit con divisione veloce del modulo per essere efficiente. La prima opzione richiede solo 3 operazioni; la seconda opzione richiede 10; e la terza opzione richiede 15.
Soluzione C # rapida che utilizza una tabella precalcolata dei conteggi dei bit byte con ramificazione sulla dimensione di 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
};
}
Ecco un modulo portatile (ANSI-C) che può confrontare ciascuno dei tuoi algoritmi su qualsiasi architettura.
La tua CPU ha byte a 9 bit? Nessun problema :-) Al momento implementa 2 algoritmi, l'algoritmo K & Amp; R e una tabella di ricerca per byte. La tabella di ricerca è in media 3 volte più veloce dell'algoritmo K & Amp; R. Se qualcuno riesce a trovare un modo per fare il & Quot; Hacker's Delight & Quot; algoritmo portatile sentiti libero di aggiungerlo.
#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
32 bit o no? Sono appena arrivato con questo metodo in Java dopo aver letto & Quot; crackare l'intervista di codifica < ! / a> <> quot; Esercizio 5.5 della 4a edizione (cap. 5: manipolazione dei bit). Se il bit meno significativo è 1 incremento count, sposta a destra l'intero.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
Penso che questo sia più intuitivo delle soluzioni con 0x33333333 costante, non importa quanto siano veloci. Dipende dalla tua definizione di & Quot; miglior algoritmo & Quot; .
