MIPS división de enteros con signo

Question

Me pregunto si alguien podría saber cómo realizar una división entre dos números enteros con signo en MIPS, sin utilizar el construido en operaciones de división.

En las especificaciones de problemas, me han dicho el registro divisor, ALU, y registro cociente son los 32 bits de ancho, y el registro restante es de 64 bits.

Answer 1

Piense en cómo le gustaría realizar una división binaria con la 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

Este algoritmo de división larga “primaria” se puede escribir (en Python - Voy a dejar que se lo convierte a MIPS) como:

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

Para la división firmado, sólo puede dividir los valores absolutos, mientras que el seguimiento de la señal (suponiendo que deseas C-estilo truncar división):

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

Existen varios métodos - Yo sugeriría de Newton-Raphson , que es simple y rápido, y utiliza sólo la multiplicación y la resta.

Si no se permite la multiplicación entonces también parece haber un montón de algoritmos de división entera, que sólo tiene que utilizar los turnos, las operaciones a nivel de bits y / menos, por ejemplo, primer éxito en Google: www.bearcave.com/software/divide.htm