Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!nsc!pyramid!athertn!paul
From: paul@athertn.Atherton.COM (Paul Sander)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Keywords: bits set, count of, long
Message-ID: <30899@athertn.Atherton.COM>
Date: 25 Sep 90 23:59:12 GMT
References: <37545@ut-emx.uucp>
Reply-To: paul@Atherton.COM (Paul Sander)
Organization: Atherton Technology, Sunnyvale, CA
Lines: 61

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
>integer on a Sun 3/80 running 4.0.3 SunOS.  The brute-force method follows.
>Is there a faster way in C?  How close in speed to a hand-coded assembly
>routine would a fast method in C be (after the latter is run through the
>optimizer)?
>  Thanks in advance for your help.  Send e-mail and I will summarize for the
>net.
>
>===============================================================================
>#define	BIT_SETSIZE	32
>typedef	unsigned long	bit_set;
>#define BIT_ISSET(bit,bitset)	(((bitset) & (1<<(bit))) >> (bit))
>int bit_count();
>
>main()
>{
>	bit_set i;
>	for (i=0; i<=16; i++)
>		printf("%d has %d bits on\n", i, bit_count(i));
>}
>
>intint bit_count(i)
>bit_set i;
>{
>	int j, k;
>	k = 0;
>	for (j=0; j<BIT_SETSIZE; j++) k = k + BIT_ISSET(j, i);
>	return k;
>}
>===============================================================================

I can't think of a faster way to do it, but can think of a more portable
way (portable to two's complement machines, anyway):

int bit_count(i)
bit_set i;
{
	int k;
	for (k = 0 ; i != 0; i = i >> 1) k += (i & 1);
	return k;
}

Or:

int bit_count(i)
bit_set i;
{
	int k;
	for (k = 0 ; i != 0; i = i >> 1)
		if (i & 1) k++;
	return k;
}

Note that this requires the bit_set typedef to be unsigned, otherwise the
right-shifts are sign-extended and the loop becomes infinite.
-- 
Paul Sander        (408) 734-9822  | "Passwords are like underwear," she said,
paul@Atherton.COM                  | "Both should be changed often."
{decwrl,pyramid,sun}!athertn!paul  | -- Bennett Falk in "Mom Meets Unix"