Quickest/Shortest in C/C++ method to calculate sum of digits in binary/aka number of 1s in binary

I have a liking to finding shortest methods for coding. I have found a need for a method for calculating the sum of the digits(or the number of 1s in a number) of a number represented in binary. I have used bit operators and found this:

r=1;while(a&=a-1)r++;

where a is the number, and r is the count. a is a given integer. Is there any way to shorten this/improve the algorithm?

Shortest as in shortest length of source code.

Your solution assumes a to have an unsigned type.

Yet the code does not work for a = 0. You can fix it this way:

r=!!a;while(a&=a-1)r++;

You can shave one character off this way:

for(r=!!a;a&=a-1;r++);

But here is an alternative solution with the same source length:

for(r=0;a;a/=2)r+=a&1;

As Lundin mentioned, code golfing is off topic on Stack Overflow. It is a fun game, and one can definitely hone his C skills at trying to make the smallest code that is still fully defined for a given problem, but the resulting code is of poor value to casual readers trying to program at a more basic level.

Regarding the on topic part of your question, The quickest method to compute the number of bits in an integer: this problem has been studied intensively and several methods are available. Which one is fastest depends on many factors:

• how portable the code need to be. Some processors have built-in instructions for this and the compiler may provide a way to generate them via intrinsics or inline assembly.
• the expected range of values for the argument. If the range is small, a simple lookup table may yield the best performance.
• the distribution of values of the argument: if a specific value is almost always given, just testing for it might be the fastest solution.
• the cpu specific performance: different algorithms use different instructions, the relative performance of different cpus may differ.

Only careful benchmarking will tell you if a given approach is preferable to another, or if you are trying to optimise code whose performance is irrelevant. Provable correctness is much more important than micro-optimisation. Many experts consider optimisation to always be premature.

An interesting solution for 32-bit integers is this:

uint32_t bitcount_parallel(uint32_t v) {
    uint32_t c = v - ((v >> 1) & 0x55555555);
    c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
    c = ((c >> 4) + c) & 0x0F0F0F0F;
    c = ((c >> 8) + c) & 0x00FF00FF;
    return ((c >> 16) + c) & 0x0000FFFF;
}

If multiplication is fast, here is a potentially faster solution:

uint32_t bitcount_hybrid(uint32_t v) {
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Different solutions are detailed here: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive