count of bits set in a long
Theodore A. Camus
tac at cs.brown.edu
Sat Sep 29 01:45:42 AEST 1990
> unsigned long mask,y;
>
> y = (mask >> 1) &033333333333;
> y = mask - y - ((y >>1) & 033333333333);
> return (((y + (y >> 3)) & 030707070707) % 077);
As chris at mimsy.umd.edu noted, '%' is usually a costly operation.
However, 077 in octal is 63 in decimal, and I believe the following
relationship is true : x % 63 = [(x % 64) + (x / 64)] % 63 and can
be efficiently calculated by :
while (x > 63) { /* 2 assembly instructions */
x = (x & 63)+(x >> 6); /* 3 assembly instructions */
}
if (x = 63) /* 1 assembly instruction */
return 0 /* 1 assembly instruction */
else /* fall through, take value of x */
return x; /* = 0 instructions */
The loop is not expected to execute approx. log x times, i.e. not many.
63
Furthermore, although the lookup table method is conceptually elegant,
it has essentially NO locality of reference, and could easily cause several
cache misses, forcing a line fill just to access one byte, whereas this
code-only method will benefit from code pre-fetching etc.
my $2.0e-2 - Ted
CSnet: tac at cs.brown.edu Ted Camus
ARPAnet: tac%cs.brown.edu at relay.cs.net Box 1910 CS Dept
BITnet: tac at browncs.BITNET Brown University
"An ounce of example is worth a pound of theory." Providence, RI 02912
More information about the Comp.lang.c
mailing list