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.
La solution
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
Autres conseils
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