Number of 1s in a binary number

Question

I need to make a program that counts the number of 1s in the binary representation of an unsigned number, using a recursive function, so this is my code:

#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 is, my code works for number 7 for example, but if I enter the number 2 it will print that it has 2 ones in it. And for 4 it returns 0, and I think for all exponents of 2 it returns 0 in the end. I can't figure out why.

Answer 1

The main problem is here:

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

The addition operator + operator has higher precedence that the bitwise-AND operator &. So the expression is effectively:

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

You need to add parenthesis around n&1:

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

EDIT:

As a programming exercise, this works fine. In real life code, a precomputed lookup table is much more efficient.

// 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

The & operator has a lesser precedence than the + operator, which causes the calculation in the else branch or one to produce the wrong (logically) result. Just surround it by parenthesis to make sure it's executed first and you should be fine:

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

Answer 3

In this line

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

The operator + has a higher precedence than &. But, you have to mask the last bit first, then add it:

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