Path: utzoo!attcan!uunet!tektronix!tekecs!nobody
From: nobody@tekecs.TEK.COM (-for inetd server command)
Newsgroups: comp.lang.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <10844@tekecs.TEK.COM>
Date: 11 Jan 89 21:50:03 GMT
References: <225@tityus.UUCP> <34389@bbn.COM>
Reply-To: paulsc@radio_flyer.UUCP (Paul Scherf)
Organization: Tektronix, Inc., Wilsonville, OR
Lines: 29

In article <225@tityus.UUCP> jim@athsys.uucp (Jim Becker) writes:
}
}	The problem is the most efficient method to simply count the
}number of on bits in a sixteen bit short. 

Try this:

char bitCount[0x10000] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    /* rest of table left as an exercise to the reader */
};

#define BITCOUNT(num)	(bitCount[(unsigned short)(num)])

Or try this (a little slower, uses less space,
watch out for parameters with side effects):

char bitCount[0x100] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    /* rest of table left as an exercise to the reader */
};

#define BITCOUNT(num)	(bitCount[(unsigned char)(num)]\
			    + bitCount[(unsigned char)((num) >> 8)])

Paul Scherf, Tektronix, Box 1000, MS 61-028, Wilsonville, OR, USA
paulsc@orca.GWD.Tek.COM     503-685-2734     tektronix!orca!paulsc