MIPS Teilung unterzeichnet ganzen Zahlen

Question

Ich frage mich, ob jemand vielleicht wissen, wie eine Trennung zwischen zwei Integer mit Vorzeichen in MIPS ausführen, ohne die Verwendung der in Divisionsoperationen gebaut.

In dem Problem specs, ich bin dem Divisor-Register gesagt, ALU und Quotientenregistern sind alle 32 Bits breit, und das Rest-Register ist 64 Bit.

Answer 1

denke daran, wie Sie eine binäre Division von Hand durchführen würde:

# 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

Dieser „Grundschule“ long Divisions-Algorithmus geschrieben werden kann (in Python - Ich lasse Sie es zu MIPS konvertieren) als:

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

Für Division mit Vorzeichen, kann man einfach die absoluten Werte teilen, während Spur des Zeichens zu halten (vorausgesetzt, Sie wollen C-Stil Kürzen Abteilung):

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

Es gibt verschiedene Methoden - Ich würde vorschlagen, Newton-Raphson , die einfach und schnell ist, und verwendet nur Multiplikation und Subtraktion.

Wenn Multiplikation dann nicht erlaubt ist es auch von Integer-Division Algorithmen viel zu sein scheint, die nur Verschiebungen verwenden, bitweise Operationen und addieren / subtrahieren, z.B. zuerst auf Google getroffen: www.bearcave.com/software/divide.htm