BIT Counting: C programming problem

[chuck]

In article <225 at tityus.UUCP> jim at athsys.uucp (Jim Becker) writes:
>
>	I was recently asked a problem to which there are a number of
>solutions, I'm looking for opinions as to the best of those different
>solutions.
>
>	The problem is the most efficient method to simply count the
>number of on bits in a sixteen bit short. This is a really easy
>exercise, but one that has a variety of different approaches. I would
>be interested in the opinions of programmers out there, an efficient
>algorithm that is understandable.
>

A pretty simple bit counting algorithm can be done with a table lookup
if the calculation of the count is critical enough to warrant the space for
the table.  There need only be 1 256 byte table containing the number of
bits in a byte.  Just look up the number of bits in the lower and upper bytes
of the word.

static char bitcounts[] = { 0, 1, 1, 2, 1, ..., 7, 8 };

#define BITCOUNT(s) ((int)bitcounts[s & 0xff] + bitcounts[(s & 0xff00) >> 8])

If its REALLY critical make a 64k table which is accessed using the whole
short as an index.  This is not much memory if you're talking about a really
heavily used loop.

-- 
+------------------+   Chuck Ocheret, Sr. Staff Engineer   +------------------+
| chuck at morgan.com |       Morgan Stanley & Co., Inc.      |  (212)703-4474   |
|   Duty now ...   |19th Floor, 1251 Avenue of the Americas| for the future.  |
+------------------+         New York, N.Y.  10020         +------------------+