next up previous
Next: Floating Point Arithmetic Up: Arithmetic and Logical Operations Previous: Multiplication

Division

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
Mon Sep 13 11:15:41 ADT 1999