count of bits set in a long

[Roger House]

In <37545 at ut-emx.uucp> nwagner at ut-emx.uucp (Neal R. Wagner) writes:

>  I need a fast method to count the number of bits that are set in a 32-bit
>integer on a Sun 3/80 running 4.0.3 SunOS.  The brute-force method follows.
>Is there a faster way in C?  How close in speed to a hand-coded assembly
>routine would a fast method in C be (after the latter is run through the
>optimizer)?


The following approach should run faster since it operates on 4 bytes
rather than on 32 bits.  However, a table of 256 bytes is required.


static char num1bits[256] =
{
	/*   0 */	0,		/* num1bits[i] = no. of 1 bits	*/
	/*   1 */	1,		/*   in the binary representa-	*/
	/*   2 */	1,		/*   tion of the number i	*/
	/*   3 */	2,
	/*   4 */	1,
	/*   5 */	2,
		...
	/* 254 */	7,
	/* 255 */	8,
};



int count1bits(unsigned long x)

{
	return (
		num1bits[ x     & 0xff] + num1bits[(x>8)  & 0xff] + 
		num1bits[(x>16) & 0xff] + num1bits[(x>24) & 0xff]
	       );
}


						Roger House