/* 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 */