Numero di 1s in un numero binario

Question

ho bisogno di fare un programma che conta il numero di 1s nella rappresentazione binaria di un numero senza segno, utilizzando una funzione ricorsiva, quindi questo è il mio codice:

#include <stdio.h> 
#include <stdlib.h> 

int one(unsigned n); 

int main() 
{ 
    unsigned n; 
    printf("n= "); scanf("%u", &n); 
    printf("%d", one(n)); 

    printf("\n"); 
    return 0; 
} 

int one(unsigned n) 
{ 
    if(n==1 || n==0) 
     return n; 
    else 
     return (n&1+one(n>>1)); 
} 

Thing è, il mio codice funziona per il numero 7 per esempio, ma se inserisco il numero 2 verrà stampato che contiene 2. E per 4 restituisce 0, e penso che per tutti gli esponenti di 2 restituisca 0 alla fine. Non riesco a capire perché.

Answer 1

Il problema principale è qui:

return (n&1+one(n>>1)); 

L'operatore di addizione + operatore ha una precedenza che il bit-E operatore &. Quindi l'espressione è efficace:

return (n & (1 + one(n >> 1))); 

è necessario aggiungere le parentesi intorno n&1:

return ((n & 1) + one(n >> 1)); 

EDIT:

Come un esercizio di programmazione, questo funziona bene. Nel codice della vita reale, una tabella di ricerca precalcolata è molto più efficiente.

// Assumes CHAR_BITS == 8 

int numbits[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
        ... 
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; 

int count_bits(unsigned n) 
{ 
    int i, count = 0; 
    for (i=0; i<sizeof(n); i++) { 
     count += numbits[(uint8_t)(n & 0xFF)]; 
     n >>= 8; 
    } 
} 

Answer 2

L'operatore & ha una precedenza inferiore alla + operatore, che provoca il calcolo nel else ramo o one per produrre il (logicamente) risultato sbagliato. Basta circondano da parentesi per assicurarsi che sia eseguita per prima e si dovrebbe andare bene:

return (n & 1) + one(n>>1); 

Answer 3

In questa linea

return (n&1+one(n>>1)); 

L'operatore + ha una priorità più alta rispetto &. Ma prima devi mascherare l'ultimo bit, quindi aggiungerlo:

return ((n&1) + one(n>>1));