May
2005, Issue 178
Test Your
EQ
|
Answer
7—The
given relationships show how you can do division by certain
other integer values by using a relatively small number
of shifts and adds/subtracts. For example, assume a long
int
is 32 bits:
long int divide_by_17 (long int x)
{
return (x>>4) - (x>>8) + (x>>12) - (x>>16)
+ (x>>20) - (x>>24) + (x>>28);
}
This
is equivalent to multiplying by the reciprocal of the
denominator, and follows directly from the binary representation
of the corresponding fractions:
1/3
= 0.01010101...
1/7
= 0.001001001001...
1/15
= 0.0001000100010001...
1/31
= 0.00001000010000100001...
and
1/5
= 0.001100110011...
1/9
= 0.000111000111000111...
1/17
= 0.000011110000111100001111...
1/33
= 0.000001111100000111110000011111...
Contributor:
David Tweed
