Path: utzoo!attcan!uunet!know!zaphod.mps.ohio-state.edu!swrinde!ucsd!rutgers!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!andrew.cmu.edu!sa1z+
From: sa1z+@andrew.cmu.edu (Sudheer Apte)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Message-ID: <Mazyneu00WB6EAjWo8@andrew.cmu.edu>
Date: 25 Sep 90 23:48:58 GMT
References: <37545@ut-emx.uucp>,
	<661@atcmpe.atcmp.nl>
Organization: Civil Engineering, Carnegie Mellon, Pittsburgh, PA
Lines: 31
In-Reply-To: <661@atcmpe.atcmp.nl>

> From article <37545@ut-emx.uucp>, by nwagner@ut-emx.uucp (Neal R. Wagner):
> > 
> >   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. ...

jc@atcmp.nl (Jan Christiaan van Winkel) writes:

> [... a really neat iteration, one per bit at most, deleted ]

That was probably what Karl Heuer was talking about leaving for others.
I was thinking along these lines:

static int num_bits[256] = {0, 1, 1, 2, 1, ... /* etc. */ };

struct four_pack { char a; char b; char c; char d;};

int bit_count(i)
unsigned long i;
{
	struct four_pack f;
	f = (struct four_pack) i;
	return num_bits[f.a] + num_bits[f.b] + num_bits[f.c] +
		num_bits[f.d];
}

Would this be faster, in reality, than shifts and iteration? 

	Sudheer.
------------------
...{harvard, uunet}!andrew.cmu.edu!sa1z
sa1z%andrew@CMCCVB.BITNET