Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!hplabs!hpda!hpwala!hp-and!gallag
From: gallag@hp-and.HP.COM (Mike Gallagher)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Message-ID: <13530002@hp-and.HP.COM>
Date: 25 Sep 90 19:09:24 GMT
References: <37545@ut-emx.uucp>
Organization: HP Andover Division (Massachusetts)
Lines: 59

>   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)?

Try this:

/**************************************************************************/

typedef	unsigned long bit_set;
static int bit_count();

static char bit_array[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

main()
{
        bit_set i;
        for (i=0; i<=256; i++)
                printf("%d has %d bits on\n", i, bit_count(i));
}

static int bit_count(i)
bit_set i;
{

        int count;

        count = bit_array[i&0xff];
        i >>= 8;
        count += bit_array[i&0xff];
        i >>= 8;
        count += bit_array[i&0xff];
        i >>= 8;
        count += bit_array[i&0xff];
        return count;

}

/**************************************************************************/

Mike Gallagher