division MIPS des entiers signés

Question

Je me demande si quelqu'un peut savoir comment effectuer une division entre deux entiers signés en MIPS, sans utiliser le construit dans les opérations de division.

Dans les spécifications de problème, on me dit le registre diviseur, ALU, et le registre de quotient sont tous une largeur de 32 bits et le registre reste est de 64 bits.

Answer 1

Pensez à la façon dont vous souhaitez effectuer une division binaire à la main:

# 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

Cette « école primaire » algorithme de division longue peut être écrit (en Python - Je vous laisse le convertir en MIPS) comme:

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

Pour la division signée, vous pouvez simplement diviser les valeurs absolues tout en gardant la trace du signe (en supposant que vous voulez division tronquer style C):

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

Il existe différentes méthodes - Je suggère Newton-Raphson , qui est simple et rapide, et utilise uniquement la multiplication et la soustraction.

Si la multiplication n'est pas autorisé alors il semble aussi y avoir beaucoup d'algorithmes de division entiers qui utilisent simplement des changements, des opérations et au niveau du bit d'addition / soustraction, par exemple d'abord frappé sur Google: www.bearcave.com/software/divide.htm