Efficient count the number of bits in a 32bit bitmask

count_bits.c

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

#define DO_PRINT 0

#define TEST_BITS(_n_, _do_print_) do { \
	unsigned calculated = number_of_set_bits(_n_); \
	unsigned actual = number_of_set_bits_naive(_n_); \
	if (_do_print_) \
		printf("Number of set bits in %.8x: %d\n", _n_, calculated); \
	if (calculated != actual) { \
		printf("for 0x%.8x (dec %d) number of bits calculated is: %d " \
			"but is actually %d\n", _n_, _n_, calculated, actual); \
		fflush(stdout); \
		exit(-1); \
	} \
} while (0)

static int number_of_set_bits(uint32_t i)
{
	/* Java: use >>> instead of >>
	   C or C++: use uint32_t */
	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (int)((((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
}

static int number_of_set_bits_naive(uint32_t i)
{
	uint32_t num = 0;

	while (i) {
		num += (i & 0x1);
		i >>= 1;
	}

	return (int)num;
}

int main(int argc, char **argv)
{
	uint32_t i;

	for (i = 0; i <= 0x11111111; i++)
		TEST_BITS(i, DO_PRINT);
	printf("number_of_set_bits() works correctly!\n");
	return 0;
}