Population Count

Count the total number of set bits (1-bits) across an entire array of 32-bit unsigned integers, using the AVX2 shuffle-based nibble lookup technique.

This is the Muła popcount algorithm — a classic example of using _mm256_shuffle_epi8 as a parallel 16-entry lookup table.

Function Signature

#include <immintrin.h>
#include <cstdint>

int64_t population_count(const uint32_t* arr, int n);

Parameters:

• arr — pointer to an array of n unsigned 32-bit integers, guaranteed 32-byte aligned
• n — number of elements, guaranteed to be a multiple of 8 and at least 8

Returns: the total number of set bits across all elements (as int64_t)

Example

Input:  [7, 0, 15, 1, 3, 255, 0, 8]
Output: 19

Explanation: popcount of each: 3+0+4+1+2+8+0+1 = 19

Constraints

• 8 ≤ n ≤ 4,000,000
• n is always a multiple of 8
• arr is 32-byte aligned
• The total popcount fits in int64_t

Notes

The key insight: a nibble (4 bits) has only 16 possible values, so its popcount fits in a 16-entry table. _mm256_shuffle_epi8 acts as a parallel lookup — it uses each byte of the index vector to select from a 16-byte table (within each 128-bit lane).

Split each byte into its low and high nibbles, look up both, and add. Accumulate in 8-bit counters (which overflow after ~31 iterations), then periodically widen to 64-bit using _mm256_sad_epu8.

Useful Intrinsics