Efficient Bitboard Population Count in C

This article explores the concept of population count (popcount) and the most efficient techniques for computing it on 64-bit bitboards using the C programming language. You will learn what population count represents in systems programming and game development, followed by practical implementations ranging from hardware-accelerated CPU instructions and compiler built-ins to algorithmic bit-manipulation strategies like parallel bit counting and Brian Kernighan's method.

What is Population Count?

Population count, also known as Hamming weight or popcount, is the total number of set bits (bits with a value of 1) within a binary word.

In computer science, bitboards are 64-bit integers (uint64_t) commonly used to model states across an 8x8 grid, such as in chess or checkers engines. Each bit corresponds to a specific square, where a 1 denotes the presence of a piece or a specific state and a 0 denotes its absence. Calculating the population count on a bitboard reveals vital game-state metrics, such as piece counts or evaluation weights, in a single operation. Because chess engines evaluate millions of positions per second, this operation must execute with maximum efficiency.

Method 1: Hardware-Accelerated Compiler Built-ins

Modern x86 and ARM processors provide dedicated hardware instructions to calculate population count in a single CPU cycle (such as POPCNT on x86 architectures). The standard and most performant approach in C is to use compiler-provided intrinsics or built-in functions.

For GCC and Clang:

#include <stdint.h>

int count_pieces(uint64_t bitboard) {
    return __builtin_popcountll(bitboard);
}

For Microsoft Visual C++ (MSVC):

#include <stdint.h>
#include <nmmintrin.h>

int count_pieces(uint64_t bitboard) {
    return (int)_mm_popcnt_u64(bitboard);
}

When compiled with target-specific optimizations (such as -mpopcnt or -march=native), these functions emit native assembly instructions that bypass software iteration entirely, making them the fastest possible solution.

Method 2: Parallel Bit Counting (SWAR)

If the target architecture lacks dedicated hardware support for popcount, the optimal software fallback is the SWAR (SIMD Within A Register) algorithm. This technique uses bitmasks and shifts to sum adjacent bit fields in parallel, operating in \(\mathcal{O}(1)\) time with no conditional branching.

#include <stdint.h>

int swar_popcount64(uint64_t x) {
    // Sum adjacent pairs: 2-bit fields
    x = x - ((x >> 1) & 0x5555555555555555ULL);
    
    // Sum adjacent pairs of 2-bit fields: 4-bit fields
    x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
    
    // Sum adjacent 4-bit fields into 8-bit fields
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
    
    // Multiply by 0x01... to sum all 8 bytes into the top byte, then shift down
    return (int)((x * 0x0101010101010101ULL) >> 56);
}

This method requires roughly 12 instructions, avoiding cache misses and pipeline-stalling branches.

Method 3: Brian Kernighan’s Algorithm

Brian Kernighan’s algorithm calculates population count by clearing the least significant set bit in each iteration using the expression x &= (x - 1). The loop runs only as many times as there are set bits (\(\mathcal{O}(k)\), where \(k\) is the number of ones).

#include <stdint.h>

int kernighan_popcount64(uint64_t x) {
    int count = 0;
    while (x != 0) {
        x &= (x - 1);
        count++;
    }
    return count;
}

While slower on average than hardware intrinsics and SWAR for arbitrary inputs, Kernighan's algorithm is efficient for sparse bitboards—situations where only a few bits are set, such as tracking pawn chains or king positions in the endgame.

Summary

When working with bitboards in C, always prefer compiler intrinsics (__builtin_popcountll or _mm_popcnt_u64) to leverage native CPU instructions. When building cross-platform software targeting older processors without hardware popcount support, the SWAR algorithm provides consistent, branch-free performance, while Kernighan’s approach remains useful for sparse bitboard configurations.