Counting the number of "on" bits in an int

Question

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 & 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 <stdio.h>
#include <limits.h>

int on_bits(int num);

int main(void)
{
    int input;

    printf("Enter an int value ('q' to quit): ");
    while (scanf("%d", &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 < (sizeof(num) * CHAR_BIT); i++)
        b_mask <<= 1;

    /* Check bits */
    while (b_mask > 0) {
        if (b_mask & num)
            ++res;
        b_mask >>= 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

Answer 1

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 << (sizeof(b_mask)*CHAR_BIT - 1);

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

1. Start b_mask at 1 and left shift it instead of right shift it.
2. 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 & 0x1);
        num >>= 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 &= 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 & 0xff];
        num >>= 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 >> 1) & 0x55555555);
    num  = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    return (((num + (num >> 4)) & 0xF0F0F0F) * 0x1010101) >> 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 << (sizeof(int)*CHAR_BIT - 1);
    int res     = (num & signBit) != 0;

    num &= ~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...
}

Answer 2

You can improve the performance of the routine by using more memory. The way to do it is that instead of considering 1 single bit at a time and checking if it's on or not, consider multiple bits at a time, say 4. We then can build a table of every possible arrangements of 4 bits (2^4 = 16 entries) and store the number of enabled bits in it.

Then for any number, we can mask off 4 bits at a time, look it up in the table, and add that to the running total before shifting over by 4 bits. This approach can be extended to any number of bits, but for each additional bit, you would use twice as much memory to hold the table.

Answer 3

I received some excellent answers and comments on this question. If I didn't make it clear when I asked, the problem states that the function should take an int argument, and I took this literally to mean that the value may be negative, and that the function should count the sign bit as well as the value bits.

Many potential solutions require bit-shifting the input number to the right, and this of course causes problems for negative values. It was suggested that casting the input int to unsigned int would solve this issue. It is true that the bit pattern is preserved under such a cast if the underlying representation is two's complement, but the standard explicitly allows for one's complement and sign-magnitude representations as well. The bit pattern is not preserved under this casting in these alternative representations.

@Lưu Vĩnh Phúc provided a very informative link that had one solution that intrigued me, so I will write about it here.

The method comes from Kernighan, but apparently was first published by Peter Wegner. The idea is to remove the least significant bit by doing a bitwise & with the result of subtracting 1 from the number. The nice thing about this method is that it iterates not once for each bit in the input number, but only once for each significant bit.

The code at the link takes an unsigned int for input, but I have adapted the code to work for int inputs. My version uses a bit mask to control the loop, checking to see if the input number can be further reduced. Since the sign bit cannot be removed by subtraction, it is counted at loop initialization:

int on_bits(int num)
{
    int c;                   // c accumulates the total bits set in num
    int sb;                  // used to mask sign bit

    sb = ~(0x1 << (CHAR_BIT * sizeof(int) - 1));
    for (c = (num < 0 ? 1 : 0); num & sb; c++) {
        num &= num - 1;      // clear the least significant bit set
    }

    return c;
}

I believe that this code works for both one's and two's complement representations, but it fails for sign-magnitude representations.

By way of explanation, for positive values, subtracting 1 flips the least significant bit:

...1100 - 1 --> ...1011

The least significant bit can be removed from a number by doing a bitwise & on the result of this subtraction:

...1100 & (...1100 - 1) --> ...1100 & ...1011 --> ...1000

For negative values, in two's complement, subtracting 1 gives:

...1100 - 1 --> -(2^N - ...1100) - 1 --> -(2^N - ...1100 + 1)
            --> -(2^N - (...1100 - 1)) --> -(2^N - ...1011)
            --> ...1011

That is, subtraction of 1 from the two's complement representation of a negative number yields a negative number with value bits that are the result of subtracting one from the original value bits. So, again, we can remove the least significant bit with:

...1100 & (...1100 - 1) --> ...1100 & ...1011 --> ...1000

For negative values in one's complement, subtracting 1 gives:

...1100 - 1 --> -(-...1100 + 1) --> ~(~...1100 + 1)
            --> ~(...0011 + 1) --> ~...0100 --> ...1011

That is, subtracting 1 from the one's complement representation of a negative number flips the least significant bit. This again allows the same removal strategy.

But, this method does not work for negative values in sign-magnitude representation. Here, subtracting 1 gives:

1...1100 - 1 --> -(0...1100 + 1) --> -0...1101 --> 1...1101