Example: Integer Popcount

Example: Integer Popcount

The “popcount” is short for “population count” of a binary number, and is the number of binary 1s in an integer number. This has applications such as quickly counting the number of elements in a bit set or bit vector.

Bitwise arithmetic can be used to check for a '1' value in each bit of an integer. Usually an unsigned type is used (as below), but bit twiddling of signed integers is also possible. This is the slow version in C++ that simply loops through each bit, checking if it is set:

   int aussie_popcount_basic(unsigned int x) 
   {
        // Count number of 1s
        const int bitcount = 8 * sizeof(x);
        int ct = 0;
        for (int i = 0; i < bitcount; i++) {
            if (AUSSIE_ONE_BIT_SET(x, 1u << i)) ct++;
        }
        return ct;
   }

Kernighan Popcount Algorithm: A faster version is to use a bit trick found by Brian Kernighan, author of The C Programming Language. For all values of n, the previous number n-1 has one less bit set. So, if you do bitwise-AND of n and n-1, it removes the rightmost bit that is 1 (i.e., least significant bit). Hence, you can use this to optimize popcount by only looping as many times as there are 1s in the number (rather than always doing 32 iterations). Here's the new C++ code:

   int aussie_popcount_kernighan_algorithm(unsigned int x) 
   {
        // Count number of 1s with Kernighan bit trick
        int ct = 0;
        while (x != 0) {
            x = x & (x - 1);  // Remove rightmost 1 bit
            ct++;
        }
        return ct;
   }

Intrinsic Popcount Functions: The Kernighan method is faster, but far from optimal. To do it super-fast, we have to look at existing builtin function primitives. For example, Microsoft intrinsics include “__popcnt” or “_mm_popcnt_u32” (in header file <intrin.h>) and the GCC library has a “__builtin_popcount” function, which count the number of 1s in an unsigned integer. On x86 CPUs, the underlying intrinsics should be using the x86 assembler instruction named POPCNT. Here is some example C++ code that works for Microsoft Visual Studio:

    int aussie_popcount_intrinsics2(unsigned int x)
    {
        return __popcnt(x);  // Microsoft intrinsics
    }

Obviously, a faster version is to declare this one-line function as “inline” in a header file, or to convert to a C++ preprocessor macro, such as:

    #define AUSSIE_POPCOUNT(x) (__popcnt((unsigned)(x)))

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++