why the input argument on population count must be unsigned

Question

int pcount_r (unsigned x) {
    if(x==0)
        return 0;
    else
        return ((x & 1) + pcount_r(x >> 1));
}

just wondering why the input argument is unsigned.

best regards!

Answer 1

If the number is signed, then right-shifting will copy the sign-bit (the last bit), effectively giving negative numbers an infinite number of bits.

int pcount_r(int x) {
    if (x == 0)
        return 0;
    else if (x < 0)
        return sizeof(int)*8 - pcount_r(~x);
    else
        return (x & 1) + pcount_r(x >> 1);
}

Answer 2

It is implementation-defined what E1 >> E2 produces when E1 has a signed type and negative value (C99 6.5.7:5). On the other-hand, E1 >> E2 is unambiguously defined by the standard. Accepting and operating on an unsigned integer is a way to make the function most portable.

Incidentally, it is usual to use unsigned types for bit-twiddling.

Answer 3

The problem is that C (unlike Java) does not support signed (arithmetic) shifts. CPUs have two different types of shift operators, signed and unsigned. For example, on an x86, the SAR instruction does an arithmetic shift right, and SHR does an unsigned shift right. Since, C only has one shift right operator (>>), it cannot support both of them. If the compiler implements the code above using an unsigned shift (SHR) and you supply a negative number to that procedure you will get a wrong answer.