Path: utzoo!attcan!uunet!mailrus!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!mips!pacbell.com!pacbell!barn!everexn!roger
From: roger@everexn.com (Roger House)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Keywords: bits set, count of, long
Message-ID: <1990Sep26.180240.11516@everexn.com>
Date: 26 Sep 90 18:02:40 GMT
References: <37545@ut-emx.uucp>
Organization: Everex Systems, Inc.
Lines: 39

In <37545@ut-emx.uucp> nwagner@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