Can I use a signed integer as an argument to __builtin_popcount()?

Question

This site: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html says that it is defined for unsigned integers. Will using it for signed int give wrong results in some cases or not?

Answer 1

__builtin_popcount is a gcc-specific extension. It acts like a function with the declaration:

int __builtin_popcount (unsigned int x);

If you had an actual function with that declaration, and its declaration were visible, then you could pass an argument of any numeric type to it. Since the declaration is a prototype, any argument you pass would be implicitly converted to the parameter type, unsigned int.

Conversion from (signed) int to unsigned int is well defined. If the value being converted is within the range 0 .. INT_MAX, the value is unchanged. Otherwise, it's wrapped module UINT_MAX+1. For example, converting -1 to unsigned int yields UINT_MAX, which is 2³²-1 if unsigned int is 32 bits wide.

So the question is, does gcc treat __builtin_popcount as a function with a visible prototype? Since it's a language extension, it doesn't have to, and the gcc manual isn't entirely clear. It shows a prototype for it, but that doesn't necessarily mean that prototype is visible to your code.

An experiment with gcc 4.8.2 indicates that it is treated as a function with a visible prototype. (You can't store its address in a pointer as you could for an ordinary function, but that shouldn't be a problem). This program:

#include <stdio.h>
#include <string.h>
int main(void) {
    unsigned int n = 21845; // 0x5555, popcount = 8
    float        x = 21845.0;
    unsigned int x_rep;
    memcpy(&x_rep, &x, sizeof x_rep);

    if (sizeof x != sizeof x_rep) {
        puts("WARNING: Sizes do not match");
    }
    printf("popcount(%u) = %d\n", n, __builtin_popcount(n));
    printf("popcount(%g) = %d\n", x, __builtin_popcount(x));
    printf("popcount(%u) = %d\n", x_rep, __builtin_popcount(x_rep));
    return 0;
}

produces this output on my system:

popcount(21845) = 8
popcount(21845) = 8
popcount(1185589760) = 11

Which means that the value of x is converted to unsigned int, not just reinterpreted. When we explicitly reinterpret its representation, we get different results.

So unless gcc changes its implementation of builtin functions for some reason (that seems unlikely), passing a signed int to __builtin_popcount should work as expected, converting the int value to unsigned int. And assuming a 2's-complement representation for signed integers (which is a reasonably safe assumption), converting from int to unsigned int does not change the representation, so __builtin_popcount will give you a correct count of the bits that are set in the representation of the int, including the sign bit.

Of course if you don't want to depend on this, you can always explicitly convert the value to unsigned int using a cast. Casts are often error-prone, and it's usually better to use implicit conversions, but in this case it might be a reasonable approach.

Having said all this, if you're computing the population count of a value, it almost certainly makes more sense to start with an unsigned value. It's likely that the signed int value you're passing to __builtin_popcount should have been defined as an unsigned int in the first place.

Finally, you wrote that __builtin_popcount is "defined for unsigned integers". Actually, it's defined only for type unsigned int, not for unsigned integers in general. There are three different builtin functions:

int __builtin_popcount (unsigned int x);
int __builtin_popcountl (unsigned long x);
int __builtin_popcountll (unsigned long long x);

You need to use the right one for the type of data you're working with. Using __builtin_popcount on an unsigned long long object will likely ignore the upper half of the value, probably without a warning from the compiler.

Answer 2

To complement the other answers, here is a do-it-yourself, what-is-gcc-doing example. Let us write a simple testcase:

int f(int i){
  return __builtin_popcount(i);
}

and compile it with gcc -c test.c -fdump-tree-all. This creates several files, starting with test.c.003t.original:

;; Function f (null)
;; enabled by -tree-original

{
  return __builtin_popcount ((unsigned int) i);
}

So you can see that when __builtin_popcount is called on a signed integer, gcc casts it to the documented argument type of unsigned int.

Answer 3

Yes. You can pass signed int as well — assuming negative number is represented as 2's complement (which is most on the modern systems).

If the number is positive, then it is as good as unsigned int. If you pass a negative number however, say -1, it will convert into a very large number of type unsigned int, but it will not change the bits-pattern — hence the number of bits. signed or unsigned has nothing to do with bit-patterns, it has to do the interpretation of bits-pattern when computing value.

signed int i = -1;    //i has N number of 1 bit
unsigned int j = -1;  //j has N number of 1 bit as well.
                      //j becomes a very large number!

Hope that helps.