🚀 go-pugleaf

The C code below uses the well-known doubling technique
to count ones in a bit string of arbitrary length.

#define UNSINT_BIT 32
#define LOG_UNSINT_Bit 5

typedef unsigned int UnsInt;
typedef UnsInt *PToUnsInt;
typedef PToUnsInt Bits;

UnsInt bcount(Bits b, UnsInt size) {
    UnsInt count = 0;
    UnsInt words = (size+UNSINT_BIT-1)>>LOG_UNSINT_BIT;
    UnsInt m = ~((-2)<<(UNSINT_BIT-1 - ((words<<LOG_UNSINT_BIT)-size)));
    UnsInt i;
    
    for (i=0; i!=words; i++) {
	UnsInt v = b[i];
	if (i==words-1) v &= m;
#if UNSINT_BIT == 32
	v = ((v>> 1)&0x55555555) + (v&0x55555555);
	v = ((v>> 2)&0x33333333) + (v&0x33333333);
	v = ((v>> 4)&0x0f0f0f0f) + (v&0x0f0f0f0f);
	v = ((v>> 8)&0x00ff00ff) + (v&0x00ff00ff);
	v = ((v>>16)&0x0000ffff) + (v&0x0000ffff);
	count += v;
#else
	while (v != 0) {
	    count++;
	    v = v & (v-1);
	}
#endif
    }
    return count;
}


With a little effort, this code can be further improved by doubling up
words before reducing the word down to a single sum. This improvement
takes advantage of the fact that an n-bit field holds sums of up to
2**n-1.  After the "v = ((v>> 2)&0x33333333) + (v&0x33333333);"
statement, you have sums in 4 bit fields that can hold sums from two
words, and after the "v = ((v>> 4)..."  statement you have sums in 8
bit fields that can hold sums from 32 words.

I would also note that a branch-free "count leading zeros" sequence
can be constructed from the sequence:

	v = v | (v>>16);
	v = v | (v>> 8);
	v = v | (v>> 4);
	v = v | (v>> 2);
	v = v | (v>> 1);

...followed by the population count sequence, and a subtraction of the
result from the word size.

Regards,
Craig Hansen
craig@microunity.com