Come si conta il numero di bit zero in un numero intero?

Question

Come faccio a trovare il numero di bit "zero" in C++. Supponiamo di avere un numero intero;

int value = 276; 

Per il quale ho i bit 100010100, ma come faccio a contare gli zeri?

Answer 1

Il modo più ingenuo semplice è quello di iterare poco più i bit e contare:

size_t num_zeroes = 0; 

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i) 
{ 
    if ((value & (1 << i)) == 0) 
    ++num_zeroes; 
} 

Ci sono tutti i numeri di meglio (per diversi valori di "migliori") modi, ma questo è abbastanza chiaro, molto terse (in termini di codice) e non richiede una serie di impostazioni.

Un micro-ottimizzazione che potrebbe essere considerato un miglioramento è quello di non calcolare la maschera per testare ogni bit, invece spostare il valore e testare sempre il bit più a destra:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1) 
{ 
    if ((value & 1) == 0) 
    ++num_zeroes; 
} 

Answer 2

gran lunga la soluzione più ovvia è una tabella di consultazione.

/* Assuming CHAR_BITS == 8 */ 
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ }; 
int bitsInByte(unsigned char c) { return bits[c]; } 

Answer 3

V'è un grande libro per questo genere di cose: Hacker's Delight (sì, il nome fa schifo: non ha nulla a che fare con la sicurezza, ma esclusivamente bit-giocherellando). Fornisce diversi algoritmi per contare i bit '1', il migliore può anche essere trovato here (anche se il libro ha spiegazioni che questo sito non lo fa).

Una volta noto il numero di bit "1", basta sottrarlo al numero di bit nella rappresentazione del tipo.

Answer 4

È possibile effettuare il 32 meno the number of bits set.

Answer 5

Se si utilizza GCC, è possibile provare le funzioni built-in:

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x) 
int __builtin_clz (unsigned int x) 

Vedi GCC Documentation per i dettagli.

Answer 6

Fai un complimento quindi conta gli 1.

count_zero_bits (x) = count_one_bits (~ x);

Implementare il codice per contare quelli.

template< typename I > 
int count_one_bits(I i) 
{ 
    size_t numbits = 0; 
    for(; i != 0; i >>= 1) 
    { 
     numbits += i&1; 
    } 
} 

anche se c'è un problema con la mia funzione se i è un numero negativo perché >> metterà 1 bit sul lato destro in modo da otterrete un ciclo mai terminazione. Se esiste un modo basato su modelli per applicare un tipo non firmato che sarebbe l'ideale.

Una volta che avete allora:

template< typename I > int count_zero_bits(I i) 
{ 
    return count_one_bits(~i); 
} 

funzionerà.

Answer 7

Kernighan way del conteggio dei bit impostati

unsigned int v; // count the number of bits set in v 
unsigned int c; // c accumulates the total bits set in v 
for (c = 0; v; c++) 
{ 
    v &= v - 1; // clear the least significant bit set 
} 

può essere facilmente adattato per il compito dato. Un numero di iterazioni qui è uguale a un numero di bit impostati.

Consiglio anche il link qui sopra per vari altri modi di risolvere questo e altri tipi di compiti bit-related. C'è anche un solo esempio la linea di ottenere numero di bit implementato nelle macro.

Answer 8

Se si vuole l'efficienza poi c'è una buona implementazione nel libro "Gli hacker Delizia"

22 istruzioni di salto libero.

unsigned int count_1bits(unsigned int x) 
{ 
    x = x - ((x >> 1) & 0x55555555); 
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
    x = x + (x >> 8); 
    x = x + (x >> 16); 
    return x & 0x0000003F; 
} 

unsigned int count_0bits(unsigned int x) 
{ 
    return 32 - count_1bits(x); 
} 

Proverò a spiegare come funziona. È un algoritmo divide et impera.

(x >> 1) & 0x55555555 

Sposta tutti i bit 1 passo a destra e prende il bit meno significativo di ogni coppia di bit.

0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs) 

Quindi in pratica si avrà la seguente tabella di tutte le permutazioni a 2 bit.

1. (00 >> 1) & 01 = 00 
2. (01 >> 1) & 01 = 00 
3. (10 >> 1) & 01 = 01 
4. (11 >> 1) & 01 = 01 

x - ((x >> 1) & 0x55555555); 

Quindi si sottraggono queste coppie non spostate.

1. 00 - 00 = 00 => 0 x 1 bits 
2. 01 - 00 = 01 => 1 x 1 bits 
3. 10 - 01 = 01 => 1 x 1 bits 
4. 11 - 01 = 10 => 2 x 1 bits 

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

Così ora abbiamo cambiato ogni coppia 2 bit in modo che il loro valore è ora il numero di bit del loro corrispondenti coppie originali 2 bit ... e poi continuare in modo simile con i gruppi 4 bit, 8 bit gruppi, gruppi a 16 bit e finali a 32 bit.

Se si desidera una spiegazione migliore comprare il libro, ci sono un sacco di buona spiegazione e le discussioni di algoritmi alternativi ecc ...

Answer 9

Secondo me, il modo più semplice per ottenere il numero di bit zero in modo positivo intero è il seguente pezzo di codice.

int get_zero_bit_count(int num) 
{ 
    int cnt = 0; 

    while(num > 0) 
     { 
      int and_num = num & 1; 

      if (and_num != num) cnt++; 

      num >>= 1; 
     } 

     return cnt; 
    } 

Questo codice è di facile comprensione ed è esplicativo. Funziona bene per numeri interi positivi.

Answer 10

Mi sorprende che nessuno ha menzionato questo:

int num_zero_bits = __builtin_popcount(~num); 

questo darà il numero di zero bit in num quando viene utilizzato con GCC.

Answer 11

Ampliando la risposta di ronag, che altri utenti hanno già menzionato porta a risultati errati (il suo algoritmo funziona solo fino ad un valore di x = 15), qui è una versione aggiornata dell'algoritmo:

uint8_t count_1bits(uint32_t x) { 
    x = x - ((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 & 0x3F; 
} 

uint8_t count_0bits(uint32_t x) { 
    return 32 - count_1bits(x); 
} 

Il spiegazione della prima linea da ronag è corretta, tuttavia, le linee rimanenti si utilizza un approccio differente. Nella prima riga, attraverso lo spostamento e sottrazione, ogni coppia 2 bit conterrà il numero di bit impostati in quella coppia del numero originale. Il resto delle linee ricorsivo piegare quei numeri insieme aggiungendo LSB di ciascun gruppo 2n bit MSB di quella coppia traslata di n, in modo che il gruppo 2n bit contiene il numero di bit che è stata impostata in quel gruppo nel numero originale:

01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number) 
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111 
= 0110 + 0111 
= 1101 

che questo algoritmo funziona per 32 bit interi, ma può essere facilmente adattato cambiando le costanti per il corretto bit-lunghezza in modo che il modello rimane lo stesso (ad esempio 0x5555 ... = 0101. .., 0x0f0f ...= 00001111 ... ecc.) E aggiunta/rimozione dei turni appropriati