** Next:** About this document
**Up:** Arithmetic and Logical Operations
** Previous:** Multiplication

##

The unsigned binary division algorithm is based on the longhand
algorithm employed for decimal integers. The *dividend* is divided
by the *divisor* to obtain the *quotient* and a *remainder*.

5 <--quotient
____
divisor--> 2 ) 11 <--dividend
- 10
----
1 <--remainder

If the divisor is larger than the dividend, the quotient is 0 and
the remainder equals the dividend.

Otherwise, the divisor is shifted left until the most significant bits of
the divisor and dividend are aligned.
If the shifted divisor is greater than the dividend, then the
resulting quotient bit is 0. Otherwise, the quotient
bit is a 1 and the divisor is subtracted from the dividend to produce a
remainder. This process is repeated until the remainder from the
subtraction is smaller than the divisor.

In binary, decimal 11 divided by 2 gives a quotient of 5 and a remainder
of 1 as shown below:

101 (5)
______
(2) 10) 1011 (11)
-10
-----
011
-00
----
11
-10
---
1 (1)

A SAL implementation of the unsigned integer division algorithm is
shown below:

#
# SAL code to implement unsigned division
# Dividend is divided by Divisor,
# yielding Quotient and Remainder
#
.data
# Input Parameters
Dividend: .word 57
Divisor: .word 10
# Outputs
Quotient: .word 0
Remainder: .word 0
# Temporary Variables
divisor: .word
steps: .word 0
.text
__start: move steps, 0
move Quotient, 0 # initialize Quotient
move Remainder, Dividend # and Remainder
move divisor, Divisor
ShiftLoop: sll divisor, divisor, 1 # shift divisor left to
add steps, steps, 1 # align with dividend
ble divisor, Remainder, ShiftLoop
Subtract: sra divisor, divisor, 1 # repeat: shift divisor right,
blez steps, Done # if divisor < Remainder,
sll Quotient, Quotient, 1 # subtract divisor,
sub steps, steps, 1 # decrement shift count,
bgt divisor, Remainder, Subtract
sub Remainder, Remainder, divisor
add Quotient, Quotient, 1 # add quotient bit
bgtz steps, Subtract # until steps = 0.
Done: done

To handle signed integers, unsigned division is performed on the
absolute values of the numbers and the result is negated when the
numbers are of opposite sign.

Overflow is not possible in integer division because the quotient
and the remainder must be less than or equal to the dividend.

Division by zero is undefined and will produce an execution error
resulting in termination of the program.

*CS 301 Class Account *

Thu Nov 5 12:25:05 AST 1998