Skip to content

Instantly share code, notes, and snippets.

@Y0un3ss3
Forked from qi7chen/divide.c
Created November 21, 2017 23:04
Show Gist options
  • Save Y0un3ss3/5442fe9595d4e7f9c6c34e5a0315eff2 to your computer and use it in GitHub Desktop.
Save Y0un3ss3/5442fe9595d4e7f9c6c34e5a0315eff2 to your computer and use it in GitHub Desktop.
divide algorithm use shift and substract
/*
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 &quotient,
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 &quotient,
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 */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment