count of bits set in a long
Mike Gallagher
gallag at hp-and.HP.COM
Wed Sep 26 05:09:24 AEST 1990
> 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
More information about the Comp.lang.c
mailing list