count of bits set in a long
Paul Sander
paul at athertn.Atherton.COM
Wed Sep 26 09:59:12 AEST 1990
In article <37545 at ut-emx.uucp> nwagner at 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 at Atherton.COM | "Both should be changed often."
{decwrl,pyramid,sun}!athertn!paul | -- Bennett Falk in "Mom Meets Unix"
More information about the Comp.lang.c
mailing list