符号付き整数のMIPS部門

Question

誰もが除算演算に建て使用せずに、MIPSに2つの符号付き整数間の割り算を実行する方法を知っている可能性がある場合、

私は思ったんだけど。

問題の仕様では、Iは除数レジスタ、ALU、及び商レジスタは広い全て32ビットであり、残りのレジスタは64ビットである。

聞いてい

Answer 1

あなたが手でバイナリ除算を実行したいかを考えてみます：

# 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

Answer 2

様々な方法があります - 私はニュートン・ラプソンを示唆していますシンプルかつ高速で、かつ唯一の乗算と減算を使用していますに、。

乗算が許可されていない場合、

次に、まただけ減算/シフト、ビット演算を使用して、追加整数除算アルゴリズム、例えばたっぷりがあるように思われます最初にGoogleでヒット： www.bearcave.com/software/divide.htmする