Count set bits in O(1)

bits.c

#include <inttypes.h>

uint16_t bits(int64_t a) {
	uint64_t x;
	a -= (a >> 1) & 0x5555555555555555;
	x = ((a >> 2) & 0x3333333333333333) + (a & 0x3333333333333333);
	return (((int64_t) ((x + (x >> 4)) & 0xf0f0f0f0f0f0f0f)) * ((int64_t) 0x101010101010101)) >> 56;
}