MIPS division of signed integers

Question

I'm wondering if anyone might know how to perform a division between two signed integers in MIPS, WITHOUT using the built in division operations.

In the problem specs, I'm told the divisor register, ALU, and quotient register are all 32 bits wide, and the remainder register is 64 bits.

Answer 1

Think of how you'd perform a binary division by hand:

# a/b, where a=2011 and b=18

            1101111 ←quotient
      ┌────────────         ↓
10010 │ 11111011011  a
       -10010↓↓↓↓↓↓  -64b × 1
       ───────↓↓↓↓↓
         11010↓↓↓↓↓
        -10010↓↓↓↓↓  -32b × 1
        ───────↓↓↓↓
          10001↓↓↓↓
         -00000↓↓↓↓  -16b × 0
         ───────↓↓↓
          100011↓↓↓
          -10010↓↓↓   -8b × 1
          ───────↓↓
           100010↓↓
           -10010↓↓   -4b × 1
           ───────↓
            100001↓
            -10010↓   -2b × 1
            ───────
              11111
             -10010   -1b × 1
             ──────                
               1101  remainder

This “grade school” long division algorithm can be written (in Python — I'll let you convert it to MIPS) as:

def unsigned_divide(dividend, divisor):
    if divisor == 0:
        raise ZeroDivisionError()
    if dividend < divisor:
        return 0
    # Determine the position of the first digit of the quotient
    shift_amt = dividend.bit_length() - divisor.bit_length()
    # Loop to find each bit of the quotient
    quotient = 0
    while shift_amt >= 0:
        # Calculate one bit of the quotient
        if dividend >= (divisor << shift_amt):
             # new bit is 1
             dividend -= (divisor << shift_amt)
             quotient |= (1 << shift_amt)
        # Move to the next digit
        shift_amt -= 1
    return quotient

For signed division, you can just divide the absolute values while keeping track of the sign (assuming you want C-style truncating division):

def signed_divide(dividend, divisor):
    is_negative = (dividend < 0) ^ (divisor < 0)
    abs_quotient = unsigned_divide(abs(dividend), abs(divisor))
    return -abs_quotient if is_negative else abs_quotient

Answer 2

There are various methods - I would suggest Newton-Raphson, which is simple and fast, and uses only multiplication and subtraction.

If multiplication is not allowed then there also seem to be plenty of integer division algorithms which just use shifts, bitwise operations and add/subtract, e.g. first hit on Google: www.bearcave.com/software/divide.htm