|integer mod with constant modulus. firstname.lastname@example.org (R. Bernstein) (1995-06-24)|
|Re: integer mod with constant modulus. email@example.com (1995-06-29)|
|Re: integer mod with constant modulus. firstname.lastname@example.org (1995-07-04)|
|HAKMEM #169 email@example.com (1995-07-06)|
|From:||firstname.lastname@example.org (Michael Ernst)|
|Organization:||MIT Lab for Computer Science|
|Date:||Thu, 29 Jun 1995 20:58:34 GMT|
"R. Bernstein" <email@example.com> writes:
> [Do fast integer mod (2^x +/- 1) computations by casting out nines (or
> other appropriate factor and then summing blocks of bits in a word in
> parallel, making sure there is no carry between blocks.]
This is a really neat technique which was described in HAKMEM and is used
in the X11 sources to count the number of bits in a word (which is actually
a modulus operation). It doesn't require any branches. On some
architectures the final modulus may be expensive; it can be replaced by a
few more shifts, masks, and adds in the obvious way.
* This function counts the number of bits in a long.
* It is limited to 63 bit longs, but a minor mod can cope with 511 bits.
* It is so magic, an explanation is required:
* Consider a 3 bit number as being
* if we shift it right 1 bit, we have
* subtracting this from the original gives
* if we shift the original 2 bits right we get
* and so with another subtraction we have
* which is the number of bits in the original number.
* Suitable masking allows the sums of the octal digits in a
* 32 bit number to appear in each octal digit. This isn't much help
* unless we can get all of them summed together.
* This can be done by modulo arithmetic (sum the digits in a number by molulo
* the base of the number minus one) the old "casting out nines" trick they
* taught in school before calculators were invented.
* Now, using mod 7 wont help us, because our number will very likely have
* more than 7 bits set. So add the octal digits together to get base64
* digits, and use modulo 63.
* (Those of you with 64 bit machines need to add 3 octal digits together to
* get base512 digits, and use mod 511.)
* This is HAKMEM 169, as used in X11 sources.
t0_hackmemmod(register unsigned long n)
register unsigned long tmp;
tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
Return to the
Search the comp.compilers archives again.