Contare il numero di 1 in formato binario di un numero decimale

Sto cercando di trovare il numero di 1 in forma binaria di un grande numero decimale (numero decimale può essere grande come 1000000).

Ho provato questo pezzo di codice:

while(sum>0)  
{  
    if(sum%2 != 0)  
    {  
        c++;   //counting number of ones  
    }  
    sum=sum/2;  
}  

Voglio un algoritmo più veloce in quanto richiede un lungo periodo di tempo per i grandi input decimali. Per favore mi suggeriscono un algoritmo efficiente.

1000000 non è molto grande. Perché non si converte in una stringa e contare quelli?
Davvero? 20 iterazioni richiede molto tempo?
Spero che intendi per non reinventare la ruota e usando std::count 🙂
questo è un problema di peso di hamming: en.wikipedia.org/wiki/Hamming_weight . hanno letto in esso, si potrebbe ottenere enlightend come l’abuso di operatori binari 🙂
gurmeet.net/puzzles/fast-bit-counting-routines diversi cool semplici algoritmi. alcuni sono meglio di altri a seconda dello scenario.

InformationsquelleAutor zalenix | 2013-02-04

5 risposte

  1. 19

    In C++ si può fare proprio questo.

    #include <bitset>
    #include <iostream>
    #include <climits>
    
    size_t popcount(size_t n) {
        std::bitset<sizeof(size_t) * CHAR_BIT> b(n);
        return b.count();
    }
    
    int main() {
        std::cout << popcount(1000000);
    }
    Perché assumersi 32 bit? size_t non è necessariamente 32 bit. E 1 byte non significa necessariamente 8 bit. Dunque, ho modificato la risposta.
    Risposta ha detto “grande come 1 milione di” così ho pensato a 32-bit sarebbe sufficiente. Apprezzo la modifica però.
    Ah, io in realtà sono imbattuto su questa risposta, dopo un C++ di ricerca di google. Ciao Danny!
    ha un’idea di come farlo, come altro?

    InformationsquelleAutor Rapptz

  2. 19

    Quello che stai cercando è “popcount”, che è implementato come una singola CPU istruzioni successive x64 CPU, che non sarà battuto per la velocità:

    #ifdef __APPLE__
    #define NAME(name) _##name
    #else
    #define NAME(name) name
    #endif
    
    /*
     * Count the number of bits set in the bitboard.
     *
     * %rdi: bb
     */
    .globl NAME(cpuPopcount);
    NAME(cpuPopcount):
        popcnt %rdi, %rax
        ret

    Ma, naturalmente, avrete bisogno di testare la CPU supporta primo:

    /*
     * Test if the CPU has the popcnt instruction.
     */
    .globl NAME(cpuHasPopcount);
    NAME(cpuHasPopcount):
        pushq %rbx
    
        movl $1, %eax
        cpuid                   //ecx=feature info 1, edx=feature info 2
    
        xorl %eax, %eax
    
        testl $1 << 23, %ecx
        jz 1f
        movl $1, %eax
    
    1:
        popq %rbx
        ret

    Ecco un’implementazione in C:

    unsigned cppPopcount(unsigned bb)
    {
    #define C55 0x5555555555555555ULL
    #define C33 0x3333333333333333ULL
    #define C0F 0x0f0f0f0f0f0f0f0fULL
    #define C01 0x0101010101010101ULL
    
        bb -= (bb >> 1) & C55;              //put count of each 2 bits into those 2 bits
        bb = (bb & C33) + ((bb >> 2) & C33);//put count of each 4 bits into those 4 bits
        bb = (bb + (bb >> 4)) & C0F;        //put count of each 8 bits into those 8 bits
        return (bb * C01) >> 56;            //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
    }

    Il Compilatore GNU C runtime contiene un “built-in”, che potrebbe essere più veloce di attuazione di cui sopra (si potrebbe utilizzare la CPU popcnt istruzione, ma l’implementazione specifica):

    unsigned builtinPopcount(unsigned bb)
    {
        return __builtin_popcountll(bb);
    }

    Tutti i precedenti implementazioni sono utilizzati nel mio C++ scacchi, biblioteca popcount svolge un ruolo fondamentale nel gioco degli scacchi mossa generazione, quando bitboard sono utilizzati per rappresentare pezzo posizioni. Io uso un puntatore a funzione, set-up durante la biblioteca di inizializzazione, l’attuazione richiesto dall’utente e quindi utilizzare il popcount funzione tramite il puntatore.

    Google fornirà molte altre implementazioni, come è un problema interessante, per esempio: http://wiki.cs.pdx.edu/forge/popcount.html.

    InformationsquelleAutor trojanfoe

  3. 12

    Ci sono molti modi. Facile da capire e abbastanza veloce, è Brian Kernighan modo :

    unsigned int v = value(); //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
    }
    con voto positivo, perché è così bella e ordinata. Prende ancora più iterazioni di più popcount implementazioni 🙂
    Io non capisco. Spiegare questo a me : for (c = 0; v; c++). v non è inizializzata.
    A giudicare dal commento in prima linea, v deve contenere il valore il cui bit che si desidera contare.
    Oh. Grazie. Ho modificato la risposta a renderlo un po ‘ migliore.
    Grazie. Ho pensato che un commento sarebbe abbastanza 🙂

    InformationsquelleAutor BЈовић

  4. 2

    utilizzando bit shift operatore

        int number = 15; //this is input number
        int oneCount = number & 1 ? 1 : 0;
        while(number = number >> 1)
        {
            if(number & 1)
                ++oneCount;
        }
    
        cout << "# of ones :"<< oneCount << endl;
    Cosa succede se il numero è negativo?

    InformationsquelleAutor Santosh Chauhan

  5. 1
    int count_1s_in_Num(int num)
    {
        int count=0;
        while(num!=0)
        {
            num = num & (num-1);
            count++;
        }
        return count;
    }

    Se si applica l’operazione per il numero intero e il risultato della sottrazione, il risultato è un nuovo numero che è lo stesso come l’originale, intero, tranne che la destra 1 ora 0. Per esempio,01110000 E (01110000 – 1) = 01110000 E 01101111 = 01100000.

    Questa soluzione ha il tempo di esecuzione O(m), dove m è il numero di 1 nella soluzione.

    InformationsquelleAutor Praks

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *