有符号整数的MIPS师
题
我想知道是否有人会知道如何在MIPS两个有符号整数之间进行分工,不使用内置的除法运算。
在问题规格,我被告知除数寄存器,ALU,与商寄存器都是32个位宽,而其余寄存器是64位。
解决方案
的如何你手工执行二进制除法想:
# 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
本“小学”长除法算法可以被写入(在Python - 我让你把它转换为MIPS)为:
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
有关签署师,你可以划分绝对值,同时保持跟踪标志(假设你想要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
其他提示
有多种方法 - 我建议牛顿 - 拉夫逊,这是简单且快速的,并且仅使用乘法和减法。
如果乘法不允许再有也似乎是大量的整数除法的算法,其只使用移位,位运算和加法/减法,例如先打在谷歌: www.bearcave.com/software/divide.htm
不隶属于 StackOverflow