Counting the number of "on" bits in an int Here is some code I wrote as a solution to Programming Exercise 15.3 in Stephen Prata's C Primer Plus, 6th Edition. It is probably worth pointing out that the title of the chapter is Bit Fiddling. The question asks:


  Write a function that takes an int argument and returns the number
  of "on" bits in the argument. Test the function in a program.


My code seems to work for a variety of test-cases. But bit-fiddling seems finicky, and I was wondering if anyone could see any mistakes here. I would also be very interested to hear about ways to improve this code, or better approaches (e. g., more concise, or more efficient) to the problem.

The code that I have forms a bitmask from an unsigned int with only the bit corresponding to the sign bit of the input int set to "on", and then proceeds to check the bits of the input int against the bitmask, moving the test bit towards the lower order bits at each iteration until the last bit has been tested.

Since first posting this question, I have begun to feel uneasy about the expression:

(b_mask &amp; num)


as b_mask is an unsigned int and num is an int. It usually seems like a bad idea to mix signed and unsigned types in the same expression. Is the result of this operation reliable? Any thoughts on this particular issue would be welcome.

#include &lt;stdio.h&gt;
#include &lt;limits.h&gt;

int on_bits(int num);

int main(void)
{
    int input;

    printf("Enter an int value ('q' to quit): ");
    while (scanf("%d", &amp;input) == 1) {
        printf("%d\n", on_bits(input));
        printf("Enter an int value ('q' to quit): ");
    }

    return 0;
}

int on_bits(int num)
{
    int res = 0;
    unsigned b_mask = 0x1;

    /* Move to sign bit */
    for (int i = 1; i &lt; (sizeof(num) * CHAR_BIT); i++)
        b_mask &lt;&lt;= 1;

    /* Check bits */
    while (b_mask &gt; 0) {
        if (b_mask &amp; num)
            ++res;
        b_mask &gt;&gt;= 1;
    }

    return res;
}


Here is a sample interaction:




Enter an int value ('q' to quit): 255
8
Enter an int value ('q' to quit): -255
25
Enter an int value ('q' to quit): 2048
1
Enter an int value ('q' to quit): 2047    
11
Enter an int value ('q' to quit): -2047
22
Enter an int value ('q' to quit): 4095
12
Enter an int value ('q' to quit): -4095
21
Enter an int value ('q' to quit): -1234567
22
Enter an int value ('q' to quit): -987654321
16
Enter an int value ('q' to quit): q
The current implementation

Your implementation is correct, and takes \$O(n)\$ time, where \$n\$ is the number of bits in an int.  One thing you can improve is the initial setting of b_mask.  Currently, you use a loop, but it can be done like this:

unsigned int b_mask = 1u &lt;&lt; (sizeof(b_mask)*CHAR_BIT - 1);


Actually, there are two other strategies you can use as well:


Start b_mask at 1 and left shift it instead of right shift it.
Get rid of b_mask and shift the number instead.


For an example of #2:

int on_bits(unsigned int num)
{
    int res = 0;

    while (num != 0) {
        res += (num &amp; 0x1);
        num &gt;&gt;= 1;
    }

    return res;
}


Other implementations

There are a wide variety of ways to count bits.  You should read the wikipedia page on Hamming weight for starters.  I'll briefly mention some here:

Removing one bit per loop

There is a bit trick that removes the lowest set bit.  So instead of looping \$n\$ times (e.g. 32), you can only loop \$m\$ times, where \$m\$ is the number of bits actually set. So if there is only 1 bit set, you only have to loop once.  The code looks like this:

int on_bits(unsigned int num)
{
    int res = 0;

    while (num != 0) {
        num &amp;= num - 1;
        res++;
    }

    return res;
}


Using hardware instruction

Many CPUs have a dedicated instruction for counting bits (e.g. popcnt for X86).  Your compiler probably has a way of accessing this instruction (e.g. __builtin_popcount() for GNU.  This will be the fastest of all implementations but will be hardware and compiler dependent.

int on_bits(unsigned int num)
{
    return __builtin_popcount(num);
}


Using a lookup table

Suppose you created a lookup table with 256 entries that contained the number of bits set in each byte value 0..255.  Then your code would need to loop only 4 times instead of 32:

static const uint8_t bitsInByte[256] = { /* Prefilled in */ };
int on_bits(unsigned int num)
{
    int res = 0;

    while (num != 0) {
        res += bitsInByte[num &amp; 0xff];
        num &gt;&gt;= 8;
    }

    return res;
}


Using parallelism and bit tricks

This is described in the wikipedia article in depth.  Here I give the 32-bit version instead of the 64-bit one:

// Assumes int is 32 bits
int on_bits(unsigned int num)
{
    num -= ((num &gt;&gt; 1) &amp; 0x55555555);
    num  = (num &amp; 0x33333333) + ((num &gt;&gt; 2) &amp; 0x33333333);
    return (((num + (num &gt;&gt; 4)) &amp; 0xF0F0F0F) * 0x1010101) &gt;&gt; 24;
}


One's complement

According to later comments by the OP, being able to handle one's complement is important, and the input argument should be int instead of unsigned int.  You can still use all of the functions above, if you first prepare the input argument by stripping its sign bit, like this:

int on_bits(int num)
{
    int signBit = 1 &lt;&lt; (sizeof(int)*CHAR_BIT - 1);
    int res     = (num &amp; signBit) != 0;

    num &amp;= ~signBit;

    // Now, num has its sign bit stripped so it can be right shifted.
    // Res is 1 if the sign bit was set, or 0 if it was not.

    // Do the rest here...
}