NOTE: Credit to the content of the article, other than my comments about the content, goes to whatever A.I. engine Microsoft uses for CoPilot…

While trying out a feature of Microsoft’s CoPilot A.I., I decided to ask it a simple question:

What is a good way to count the set bits in a 32-bit integer in the C programming language?

At my day job, we collect a byte from boards that multiplex eight sub-boards. There can be up to four of these multiplexer boards for a total of 32 sub-boards being multiplexed. Bits in those bytes will be set to indicate if a sub-board was found. The original designer has code that retrieves a byte from each multiplexer board then combines them into a 32-bit integer. There is code that counts the set bits to make sure we found as many boards as the system is configured to expect.

To my surprise, CoPilot gave me five different routines. The first was easy to understand, and a bit more clever than what I would have created. It called this the Iterative Bitwise Method with a description of “simple and portable, but not the fastest.”

int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Next was something called the Brian Kernighan’s Algorithm, which was “efficient for sparse bit patterns.”

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

Third was a Lookup Table Method for “fast for repeated calls but requires extra memory.”

unsigned char lookupTable[256];

void initializeLookupTable() {
    for (int i = 0; i < 256; i++) {
        lookupTable[i] = countSetBits(i); // Use any method to count bits
    }
}

int countSetBitsUsingLookup(int n) {
    return lookupTable[n & 0xFF] +
           lookupTable[(n >> 8) & 0xFF] +
           lookupTable[(n >> 16) & 0xFF] +
           lookupTable[(n >> 24) & 0xFF];
}

Fourth was something I had never heard of: Compiler Intrinsics. It said “may modern compilers provide built-in functions to count set bits efficiently” and described it as “extremely fast but platform-dependent.”

#include <intrin.h>

int countSetBits(int n) {
    return __popcnt(n);
}

In my world of “barely C” embedded compiles that don’t even support the modern printf formats for printing pointers, I do not expect to have access to this.

And fifth was Parallel Bitwise Operations, described as “fast and portable, but harder to understands.”

And that is the version that made me post this:

int countSetBits(int n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n + (n >> 4)) & 0x0F0F0F0F;
    n = n + (n >> 8);
    n = n + (n >> 16);
    return n & 0x3F;
}

Harder to understand is an understatement. My brane hurts just looking at that trying to figure out how it works.

And I thought I’d share that hurt with you.

Have a good C day…