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.