Population Count, in depth: hardware instructions, compiler flags, bulk SIMD counting, Hamming distance for binary embeddings, GPU warp compaction and rank

Three portable methods

Three portable methods are worth knowing, mainly so you can recognise them and replace them with an intrinsic. The naive loop tests each bit and costs one iteration per bit position. Kernighan's loop clears the lowest set bit with x &= x - 1 and costs one iteration per set bit, which is fast for sparse words. A byte lookup table sums four or eight table entries and is branch-free but touches memory.

int popcount_naive(uint64_t x) {        /* 64 iterations */
    int n = 0;
    for (int i = 0; i < 64; i++) n += (x >> i) & 1;
    return n;
}

int popcount_kernighan(uint64_t x) {    /* one iteration per set bit */
    int n = 0;
    while (x) { x &= x - 1; n++; }
    return n;
}

static uint8_t T[256];                  /* T[i] = popcount(i), filled once */
int popcount_table(uint64_t x) {
    int n = 0;
    for (int i = 0; i < 8; i++) n += T[(x >> (8 * i)) & 0xff];
    return n;
}

The SWAR method, which adds bits in parallel inside the register, is what compilers fall back to when no instruction is available. On any processor from roughly the last fifteen years, none of these beat the hardware instruction, so in production code their main use is as a reference implementation for tests.

What the compiler emits

The trap is that writing __builtin_popcountll(x) does not guarantee the instruction. On x86-64, POPCNT is not part of the original baseline, so a compiler targeting plain x86-64 emits either a library call or an inline bit-twiddling sequence, depending on the compiler and version. Building with -mpopcnt, -march=x86-64-v2 or a newer level, or -march=native lets it emit the single instruction. MSVC's __popcnt64 intrinsic always emits the instruction, and Microsoft's documentation tells you to check CPUID first, because on a processor without it the program faults.

On AArch64 the base instruction set counts bits per byte in a SIMD register with CNT and then adds the bytes, which compilers use for scalar popcount; newer Arm architecture versions add a scalar count instruction on general registers. Compiler developers have also documented that some Intel cores treated POPCNT as having a false dependency on its destination register, and current compilers insert a zeroing instruction to break it. You only need to care about that if you write assembly.

When one binary must run on old and new machines, dispatch at runtime:

__attribute__((target("popcnt")))
static uint64_t count_hw(const uint64_t *p, size_t n) {
    uint64_t s = 0;
    for (size_t i = 0; i < n; i++) s += __builtin_popcountll(p[i]);
    return s;
}

static uint64_t count_sw(const uint64_t *p, size_t n);   /* portable fallback */

uint64_t count_bits(const uint64_t *p, size_t n) {
    static int has = -1;
    if (has < 0) has = __builtin_cpu_supports("popcnt");
    return has ? count_hw(p, n) : count_sw(p, n);
}

Language APIs

Most languages now expose popcount directly, and the runtime or compiler maps it to the instruction when it can.

Python's bit_count on a negative number counts the bits of its absolute value, not of a two's-complement word, so mask first with x & ((1 << 64) - 1) when you are porting code that assumes fixed width.

Counting whole arrays

Counting an array is a different problem from counting a word. A scalar loop issues one POPCNT per eight bytes, which on a modern core is fast enough that the loop is often limited by loads, not counting. Three techniques go further. With AVX-512 VPOPCNTDQ, available on recent Intel and AMD server cores, one instruction counts all eight 64-bit lanes of a 512-bit register. Without it, the nibble-lookup method uses a byte shuffle as a 16-entry table to count four bits at a time across a vector register. And the Harley-Seal method, analysed for AVX2 by Mula, Kurz and Lemire, uses carry-save adders to combine many vectors before counting, so only a fraction of them need a full popcount.

#include <immintrin.h>
/* Requires AVX512F + AVX512VPOPCNTDQ; n is a multiple of 8 words. */
uint64_t count_avx512(const uint64_t *p, size_t n) {
    __m512i acc = _mm512_setzero_si512();
    for (size_t i = 0; i < n; i += 8)
        acc = _mm512_add_epi64(acc, _mm512_popcnt_epi64(_mm512_loadu_si512(p + i)));
    return (uint64_t)_mm512_reduce_add_epi64(acc);
}

In practice large counts become memory-bound: once the data is not in cache, every method above outruns DRAM. Measure with data sizes that match production before adopting intrinsics, and keep the scalar path as the reference in tests.

Hamming distance for binary embeddings

The most important use in machine learning is Hamming distance. Binary quantisation keeps one bit per embedding dimension, typically the sign, so a 1,024-dimension float32 vector of 4 KB becomes 128 bytes. The distance between two such codes is the popcount of their XOR, which needs no multiplications at all. Search systems use this as a fast first pass over many candidates and then rerank the best few hundred with the full precision vectors. Related ideas appear in locality-sensitive hashing, where random hyperplane signs produce exactly such codes.

import numpy as np

def binarize(emb: np.ndarray) -> np.ndarray:
    """float32 [n, d] -> uint8 [n, d // 8], one bit per dimension (sign)."""
    return np.packbits(emb > 0, axis=1)

def hamming_topk(q_bits: np.ndarray, db_bits: np.ndarray, k: int) -> np.ndarray:
    x = np.bitwise_xor(db_bits, q_bits)                 # broadcast the query
    dist = np.bitwise_count(x).sum(axis=1, dtype=np.int32)   # NumPy 2.0+
    idx = np.argpartition(dist, k)[:k]
    return idx[np.argsort(dist[idx])]

def search(q: np.ndarray, emb: np.ndarray, db_bits: np.ndarray, k=10, shortlist=400):
    cand = hamming_topk(binarize(q[None, :]), db_bits, shortlist)
    scores = emb[cand] @ q                              # full-precision rerank
    return cand[np.argsort(-scores)[:k]]

Viewing the packed array as uint64 instead of uint8 cuts the number of popcount calls by eight, provided the row length is a multiple of eight bytes and the array is contiguous.

Popcount on GPUs: warp compaction

On NVIDIA GPUs __popc and __popcll count a 32-bit or 64-bit value. Combined with __ballot_sync, which gathers one predicate bit from each of the 32 lanes of a warp into a word, popcount gives each lane its position among the lanes that passed a filter. That is the core of stream compaction, used for pruning tokens, filtering candidates or building sparse lists without a global prefix sum.

// Append values whose predicate is true, preserving lane order within the warp.
// Works with partial warps: the lowest active lane acts as leader.
__device__ void append_if(bool keep, int value, int *out, int *out_len) {
    unsigned mask   = __activemask();
    unsigned lane   = threadIdx.x & 31;
    int leader      = __ffs(mask) - 1;
    unsigned ballot = __ballot_sync(mask, keep);
    int offset = __popc(ballot & ((1u << lane) - 1u));   // keepers before me
    int total  = __popc(ballot);
    int base = 0;
    if (lane == leader && total) base = atomicAdd(out_len, total);
    base = __shfl_sync(mask, base, leader);
    if (keep) out[base + offset] = value;
}

One atomic per warp instead of one per element is the win. The leader is the lowest active lane rather than lane 0, so the code stays correct when some lanes have exited.

Rank queries in succinct bitvectors

Succinct structures store a bitvector and answer rank(i), the number of ones before position i, in constant time. The usual design stores a cumulative count every 512 bits, one cache line, and finishes with at most eight popcounts. Space overhead is about 12.5 percent with 64-bit counts and less with packed two-level counters. These rank queries underpin wavelet trees, FM-indexes and compressed tries; see succinct data structures for the theory.

/* block_rank[k] = ones in words [0, 8k). rank1 counts ones in bit positions [0, i). */
uint64_t rank1(const uint64_t *w, const uint64_t *block_rank, uint64_t i) {
    uint64_t word = i >> 6, bit = i & 63;
    uint64_t r = block_rank[word >> 3];
    for (uint64_t j = word & ~7ULL; j < word; j++) r += __builtin_popcountll(w[j]);
    if (bit) r += __builtin_popcountll(w[word] & ((1ULL << bit) - 1));
    return r;
}

Worked example: binary search over 10 million vectors

Suppose you want a first-pass search over 10 million documents with 1,024-dimension embeddings. Stored as float32 they need 41 GB; as binary codes, 1.28 GB, which fits in memory on a modest server. A full scan computes 16 popcounts of 64-bit XORs per document, 160 million in total. At about one popcount per cycle on one 3 GHz core that is roughly 50 ms of counting, and spread over eight cores roughly 7 ms; streaming 1.28 GB from DRAM at an achievable 50 to 100 GB per second takes 13 to 26 ms. The scan is therefore memory-bound, so AVX-512 counting will not halve it, but smaller codes, sharding across sockets or batching several queries per pass will. Rerank the top 400 with full vectors, which costs 400 dot products, and check recall at 10 against exact search on a held-out query set. Treat these figures as estimates to verify on your hardware.

Failure modes

• Shipping without the target flag. The intrinsic compiles to a slow fallback and nobody notices until a profile shows it.
• Shipping with it everywhere. A binary built for a newer level crashes with an illegal instruction on old hosts; dispatch or document the minimum CPU.
• Signed inputs. __builtin_popcount takes unsigned int; passing a negative long truncates or sign-extends depending on the call.
• Width mismatch. Using the 32-bit builtin on 64-bit data silently drops the high half.
• Reading past the end. rank1 at a word boundary, including i equal to the bitvector length, must not touch the next word; the if (bit) guard in rank1 prevents that. Shifting a 64-bit value by 64 is undefined in C.
• Partial warps. A full mask in __ballot_sync with inactive lanes is undefined behaviour, and a hard-coded lane 0 leader may not be running.

Trade-offs

Prefer the language API first, add target flags or runtime dispatch second, and reach for SIMD intrinsics only when a measured hot loop is compute-bound. For search, binary codes trade some recall for 32 times less memory; the rerank pass buys most of it back. Bitmap indexes face the same tension between raw bitsets and compressed containers, discussed in Roaring bitmaps.

There is also a choice between counting and tracking. If a structure is queried for its cardinality far more often than it changes, keep a running count updated on each insert and delete instead of recounting; if it changes constantly and is counted rarely, recount on demand. Rank directories are the middle ground: precomputed counts at a coarse grain plus popcount for the remainder. The same pattern applies to Bloom filter fill estimates, allocator bitmaps and feature masks.

What to do next

1. Grep your code for hand-written popcount loops and replace them with the language API.
2. Check the build flags of hot binaries and confirm the instruction appears in the disassembly.
3. Decide your minimum CPU level, or add runtime dispatch for mixed fleets.
4. Keep a scalar reference and an exhaustive or randomised test against it.
5. For embedding search, prototype binary codes with a rerank and measure recall at k.
6. On GPUs, look for per-element atomics that a ballot and popcount could batch per warp.