Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!uflorida!gatech!rutgers!rochester!pt.cs.cmu.edu!andrew.cmu.edu!bader+
From: bader+@andrew.cmu.edu (Miles Bader)
Newsgroups: comp.lang.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <IXmNcvy00Uka47TGNP@andrew.cmu.edu>
Date: 10 Jan 89 05:52:59 GMT
References: <225@tityus.UUCP>
Organization: Carnegie Mellon
Lines: 26
In-Reply-To: <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. 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.

Chunk it:

#define CHUNKSIZE 8

/* table of #-bits for each index */
char numBits[1<<CHUNKSIZE]={....}; /* if big, you could init it at run-time */

int bitCount(num)
int num;
{
    int bc=0;

    while(num>0){
	bc+=numBits[num&((1<<CHUNKSIZE)-1)];
	num>>=CHUNKSIZE;
    }

    return bc;
}