count of bits set in a long
Roger House
roger at everexn.com
Thu Sep 27 04:02:40 AEST 1990
In <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)?
The following approach should run faster since it operates on 4 bytes
rather than on 32 bits. However, a table of 256 bytes is required.
static char num1bits[256] =
{
/* 0 */ 0, /* num1bits[i] = no. of 1 bits */
/* 1 */ 1, /* in the binary representa- */
/* 2 */ 1, /* tion of the number i */
/* 3 */ 2,
/* 4 */ 1,
/* 5 */ 2,
...
/* 254 */ 7,
/* 255 */ 8,
};
int count1bits(unsigned long x)
{
return (
num1bits[ x & 0xff] + num1bits[(x>8) & 0xff] +
num1bits[(x>16) & 0xff] + num1bits[(x>24) & 0xff]
);
}
Roger House
More information about the Comp.lang.c
mailing list