Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!nstn.ns.ca!news.cs.indiana.edu!att!linac!pacific.mps.ohio-state.edu!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!netcomsv!craig
From: craig@netcom.COM (Craig Hansen)
Newsgroups: comp.arch
Subject: Re: new instructions
Summary: branch free leading zero count
Message-ID: <1991May24.175323.9730@netcom.COM>
Date: 24 May 91 17:53:23 GMT
References: <24216@lanl.gov> <1991May23.192557.7558@kithrup.COM> <BRUCE.91May23181937@contingency.think.com>
Organization: Netcom - Online Communication Services  UNIX System {408 241-9760 guest}
Lines: 62



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