Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Keywords: bits set, count of, long
Message-ID: <3820@goanna.cs.rmit.oz.au>
Date: 25 Sep 90 04:16:28 GMT
References: <37545@ut-emx.uucp>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 19

In article <37545@ut-emx.uucp>, nwagner@ut-emx.uucp (Neal R. Wagner) writes:
>   I need a fast method to count the number of bits that are set in a 32-bit

A simple way is to set up a table:
	static char n_bits_set[256] = {0, 1, 1, 2, ... };

	int bit_count(n)
	    unsigned long int n;
	    {
		return n_bits_set[(n >> 24)      ]
		     + n_bits_set[(n >> 16) & 255]
		     + n_bits_set[(n >>  8) & 255]
		     + n_bits_set[(n      ) & 255];
	    }

There's a rather nice loop that does one iteration per bit, and works
for any size, but I'll leave that for others.
-- 
Heuer's Law:  Any feature is a bug unless it can be turned off.