Newsgroups: comp.lang.c
Subject: Re: Fast way of counting number of bits =1 in an int.
From: alanb@sdl.mdcbbs.com (Alan Braggins)
Date: 15 Oct 92 09:31:55 GMT
Organization: Shape Data (Division of EDS), Cambridge UK
In-reply-to: mlg@siemens.com.'s message of 12 Oct 92 15:22:27 GMT

>>>>> On 12 Oct 92 15:22:27 GMT, mlg@siemens.com. (Michael Greenberg) said:

> puri@enel.ucalgary.ca (Ruchir Puri) writes:

>>Hi there!
>>	I was wondering if software pundits out there know of 
>>a better way of counting the number of bits=1 in an integer variable.
>>The regular way is mask, shift, mask, shift,......

> Here another approach...

> Extract 8 bits at a time from your 32 bit word with shift and mask
> operations.  Use the extracted byte as an index into a 256 element
> table.  table[i] = number of bits set in 'i'. Sum the results.

Here is something I saved last time I saw this question.
I haven't used it since, so no promises.

/* magic below taken from Usenet posting <1992Apr30.160952.1@zodiac.rutgers.edu>
   by leichter@zodiac.rutgers.edu. Names changed for consistency with above.
   (Original code left as comments)
*/
/*
 * Macros to compute a bit value from a bit number, bit number from bit value,
 * and the bit count (number of bits on) for 32-bit quantities.  The results
 * are compile-time constants if the arguments are.
 *
 * The definition of BITCOUNT is based on an algorithm condensed from one
 * extracted from a graph coloring register allocator which manipulates
 * bitvectors.  It was inspired by an analogous algorithm for counting bits in
 * 36 bit words in MIT's HAKMEM.  The first VAX version was designed by Chris
 * Smith and written by Jane Hoffman.  The original conversion to a form
 * suitable for C on a VAX was by Brad Merrill; that code was fixed and
 * re-written by Jerry Leichter.  It assumes a 32-bit word.  Note that the
 * argument is evaluated multiple times, so should not have side-effects.  A
 * full explanation of the algorithm is too long to include here; in summary,
 * BX_(x) replaces each 4-bit sequence in x by the number of bits in that
 * sequence (which will, of course, fit in 4 bits).  BITCOUNT folds the 4-bit
 * sequences into 8-bit sequences.  The 8-bit sequences are then added up by
 * recognizing that they can be viewed as a base 256 number, and the sum of
 * the digits of a base b number is the same mod b-1 as the number mod b-1.
 *
 * The original implementation produce results in groups of 3, then 6 bits.
 * While natural on a PDP-10's 36-bit word, this requires special case
 * handling of the sign bit on a VAX, since the top 3-bit sequence is really
 * only 2 bits long. 
 */
/* done above as mask #define BITVAL(n)	(1 << (n)) */
/* inverse of mask */
/* #define BITNUM(b)	BITCOUNT((b)-1) */
#define BIT_invmaskn_m(n) BIT_popcount_m((n)-1)

/* #define BITCOUNT(x)	(((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255) */
#define BIT_popcount_m(n) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)

#define  BX_(x)		((x) - (((x)>>1)&0x77777777)			\
			     - (((x)>>2)&0x33333333)			\
                         - (((x)>>3)&0x11111111))

/* alternative implementation */
#if 0
int makmem(a)
register unsigned a;		/* must be unsigned to make right */
				/* shifts logical and to make divide */
				/* unsigned!!! */
{

				/* each octal digit is replaced by */
				/* number of 1's in it */
    a = a - ((a>>1) & 033333333333) - ((a>>2) & 011111111111);
				/* casting out 63's */
    a = ((a + (a>>3)) & 030707070707) % 63;
    return a;
}
#endif
--
     Alan Braggins, alanb@sdl.mdcbbs.com, abraggins@cix.compulink.co.uk
Shape Data - A division of EDS-Scicon Limited.   Cambridge, UK +44-223-316673
   "Any technology distinguishable from magic is insufficiently advanced."
 "My employer does not necessarily share my views - but I'm working on it."