1

I have the following function for counting the number of one bits:

/** Count the number of 1 bits in num */
int bitcount(int num)
{
    unsigned i = 0;
    int count = 0;
    for(; num != 0; num = num >> 1)
    {
        if(num & 1)
        {
            count++;
        }
    }
    return count;
}

It works fine, however the book I am reading (K&R) says that there is a faster version of bitcount that relies on the fact that in a two's complement number system, x &= (x - 1) deletes the rightmost bit in x. I need help leveraging this information to create a faster bitcount algorithm.

Gilbert
  • 2,699
  • 28
  • 29
  • 2
    I think it's worth mentioning that unless you are doing some extremely performance-critical code, there's not much point in getting faster than what you currently have – RShields Mar 06 '22 at 21:31
  • 1
    `x &= (x - 1)` You can just do that in a loop until `x` is 0. The number of iterations for that will be the number of 1 bits whereas your solution will need to iterate until the highest 1 bit is found. Simple example: For `1000` in binary your solution will iterate 4 times whereas the other solution will need only 1 iteration. – kaylum Mar 06 '22 at 21:35
  • https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer – Chayim Friedman Mar 06 '22 at 22:05
  • 1
    ""It works fine," --> No. Tests are inadequate. Try `bitcount(-1)`. Function fails for all negative values. Why worry about speed when functionality is broken? This is a good example of misplaced priorities. – chux - Reinstate Monica Mar 07 '22 at 01:33
  • 1
    If `x` is not negative, `x & (x - 1)` clears the lowest set bit, regardless of how negative numbers are stored. Two's complement is irrelevant; the only requirement is a binary encoding. Two's complement is only relevant if `x` is negative; as chux points out above, the function fails on negative íntegers. – rici Mar 07 '22 at 06:14
  • @rici Thanks. I think I am starting to get it a little bit. Basically, rather than starting from left going to right cancelling out the ones, this time you start from right going to left. The & thing helps you jump straight to the next one. Interesting, it seems that this C thing has alot going on. I'll try out the advice. – Gilbert Mar 07 '22 at 07:46
  • @rici I figured it out. thx – Gilbert Mar 07 '22 at 19:21

0 Answers0