CODEWITHSUNDEEP
crecursionbit-manipulation
Nebeski
Nebeski

Reputation: 610

Number of 1s in a binary number

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.

Upvotes: 6

Views: 252

Answers (3)

dbush
dbush

Reputation: 223739

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;
    }
}

Upvotes: 2

Martin Zabel
Martin Zabel

Reputation: 3659

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));

Upvotes: 2

Mureinik
Mureinik

Reputation: 311163

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);

Upvotes: 2

Related Questions