/*
These functions are examples of unsigned and signed integer division.
The algorithms assume 32-bit integers. The algorithms used are
from
Digital Computer Arithmetic, by Joseph J.F. Cavanaugh
McGraw Hill, 1984.
For an integer of size N, this algorithm will take N steps. This
makes it slower the "high-radix" division algorithms. The algorithm
has been written with pipelined hardware in mind and where ever
possible, conditions are avoided in loops. Assuming a decent
compiler, this code should also perform well on hardware with
branch delay slots.
If you compile this with Visual C++ and you keep the .c suffix
use -Tp to default to C++.
Ian Kaplan, October 1996
Copyright stuff
Use of this program, for any purpose, is granted the author,
Ian Kaplan, as long as this copyright notice is included in
the source code or any source code derived from this program.
The user assumes all responsibility for using this code.
*/
void unsigned_divide(unsigned int dividend,
unsigned int divisor,
unsigned int "ient,
unsigned int &remainder )
{
unsigned int t, num_bits;
unsigned int q, bit, d;
int i;
remainder = 0;
quotient = 0;
if (divisor == 0)
return;
if (divisor > dividend) {
remainder = dividend;
return;
}
if (divisor == dividend) {
quotient = 1;
return;
}
num_bits = 32;
while (remainder < divisor) {
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
d = dividend;
dividend = dividend << 1;
num_bits--;
}
/* The loop, above, always goes one iteration too far.
To avoid inserting an "if" statement inside the loop
the last iteration is simply reversed. */
dividend = d;
remainder = remainder >> 1;
num_bits++;
for (i = 0; i < num_bits; i++) {
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
t = remainder - divisor;
q = !((t & 0x80000000) >> 31);
dividend = dividend << 1;
quotient = (quotient << 1) | q;
if (q) {
remainder = t;
}
}
} /* unsigned_divide */
#define ABS(x) ((x) < 0 ? -(x) : (x))
void signed_divide(int dividend,
int divisor,
int "ient,
int &remainder )
{
unsigned int dend, dor;
unsigned int q, r;
dend = ABS(dividend);
dor = ABS(divisor);
unsigned_divide( dend, dor, q, r );
/* the sign of the remainder is the same as the sign of the dividend
and the quotient is negated if the signs of the operands are
opposite */
quotient = q;
if (dividend < 0) {
remainder = -r;
if (divisor > 0)
quotient = -q;
}
else { /* positive dividend */
remainder = r;
if (divisor < 0)
quotient = -q;
}
} /* signed_divide */