Xref: utzoo comp.lang.c:15398 comp.std.c:662
Path: utzoo!utgpu!watmath!clyde!att!osu-cis!killer!ames!mailrus!csd4.milw.wisc.edu!leah!itsgw!steinmetz!uunet!mstan!chuck
From: chuck@Morgan.COM (chuck)
Newsgroups: comp.lang.c,comp.std.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <201@terminus.Morgan.COM>
Date: 10 Jan 89 21:07:33 GMT
References: <225@tityus.UUCP>
Reply-To: chuck@Morgan.COM ()
Organization: Morgan Stanley and Co., NY, NY
Lines: 32

In article <225@tityus.UUCP> jim@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@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         +------------------+