divisione MIPS di interi con segno

Question

Mi chiedo se qualcuno potrebbe sapere come eseguire una divisione tra due numeri interi firmati nel MIPS, senza utilizzare il costruito in operazioni di scissione.

le specifiche problematiche, mi hanno detto registro il divisore, ALU, e il registro quoziente sono tutti i 32 bit di larghezza, e registro del resto è di 64 bit.

Answer 1

Pensate a come che ci si comporta una divisione binaria a mano:

# 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

Questo algoritmo lunga divisione “scuola elementare” può essere scritto (in Python - ti farò convertirlo in MIPS) come:

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

Per la divisione firmato, si può solo dividere i valori assoluti, mantenendo traccia del segno (supponendo che si desidera C-style troncando divisione):

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

Ci sono vari metodi - Vorrei suggerire Newton-Raphson , che è semplice e veloce, e utilizza solo moltiplicazione e sottrazione.

Se moltiplicazione non è permessa allora non sembrano anche essere molti algoritmi divisione intere che utilizzano solo spostamenti, operazioni bit per bit e aggiungere / sottrarre, ad esempio prima colpito su Google: www.bearcave.com/software/divide.htm