10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive \$\endgroup\$ – phuclv Nov 6 '16 at 13:14
  • \$\begingroup\$ Thanks for the very interesting link. The naive approach that you linked to will not work for negative values, which I took to be important in the solution of this problem. But, there was another method attributed to Kernighan there that was very interesting. I have added my own answer below to discuss this possibility. Thanks again! \$\endgroup\$ – David Bowling Nov 6 '16 at 18:51
  • \$\begingroup\$ Try not to adapt your question post to answers being posted. \$\endgroup\$ – Jamal Nov 6 '16 at 20:13
  • \$\begingroup\$ @Jamal-- I did not adapt my question to any such answers. I did add to it an update to the effect that I had placed my own answer below, and I asked about an expression in the original code that had begun to make me uneasy, but which no one had commented on. I would like to hear comments on this aspect of the code, i.e., whether the expression in question is valid or not. Please return my question to its original state. \$\endgroup\$ – David Bowling Nov 6 '16 at 20:50
  • \$\begingroup\$ I added back that particular part, with the reference to your answer removed \$\endgroup\$ – Jamal Nov 7 '16 at 1:23
12
\$\begingroup\$

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...
}
\$\endgroup\$
  • \$\begingroup\$ @JS1-- This is exactly what I was looking for. I can't believe that I missed the obvious and set b_mask in a loop instead of using a single bit-shifting operation! Thank you for all of the information. \$\endgroup\$ – David Bowling Nov 4 '16 at 22:37
  • \$\begingroup\$ Gotta love bit fiddling on a Friday night. A most interesting read. \$\endgroup\$ – isanae Nov 5 '16 at 2:21
  • \$\begingroup\$ @JS1-- I was just looking over your answer again, and it occurs to me that many of the possibilities that you mention may not work for this particular problem, as the input is an int, not an unsigned int. This could lead to problems, at least for the solutions involving right-shifts of the bits of the input number. Still, your answer was very informative and has given me plenty to think about. \$\endgroup\$ – David Bowling Nov 5 '16 at 2:53
  • \$\begingroup\$ @DavidBowling If the input must be signed, then Just cast the input argument to an unsigned int. Like this: int on_bits(int n) { unsigned int num = (unsigned int) n; ... \$\endgroup\$ – JS1 Nov 5 '16 at 4:28
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like this idea. This had occurred to me in a half-formed fashion, but seeing your explanation makes me want to try to implement it. \$\endgroup\$ – David Bowling Nov 4 '16 at 22:41
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ By definition, any function that counts set bits will be implementation specific because the implementation details of the int type are implementation specific. \$\endgroup\$ – Edward Nov 6 '16 at 21:47
  • \$\begingroup\$ @Edward-- I am not sure that I get your meaning. If you are saying that an implementation that uses two's complement will produce different results than one that uses one's complement, then yes, of course. But it would be nice if the same code worked on both implementations. The solution in my original question works for all three of the representations allowed by the standard. The solution in this answer works for two of the three representations. The bit-counts will differ, but the code will still work. \$\endgroup\$ – David Bowling Nov 6 '16 at 21:54
  • \$\begingroup\$ @Edward-- that said, I have reservations about my use of both unsigned and int in the same expression in my original code, and the effects of padding bits in this situation are unclear to me, as I don't have a good handle on exactly how padding bits work in integer representations. \$\endgroup\$ – David Bowling Nov 6 '16 at 21:56
  • \$\begingroup\$ To the latter point, this proposed code has a similar issue because both CHAR_BIT and the result of the sizeof operator could either be signed or unsigned. This is a good illustration of the previous point which is that the same code might "work" on different implementations or it might not. It also might produce the same number given the same input, or it might not. This is the very definition of non-portable code, but the fault is not in your implementation -- it's inherent to the problem. \$\endgroup\$ – Edward Nov 6 '16 at 22:05
  • \$\begingroup\$ @Edward-- Thank you for your observations. This is exactly why I put this here. I was under the impression that the additive-expression of a bitwise shift operator was only required to be non-negative, which the above expression satisfies. I don't see how this is a problem here. What am I missing? \$\endgroup\$ – David Bowling Nov 6 '16 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.