MIPS قسم الأعداد الصحيحة الموقعة

Question

أتساءل ما إذا كان قد يعرف أي شخص كيفية إجراء تقسيم بين مستويين موقعة في MIPS، دون استخدام عمليات التقسيم المدمجة.

في المشكلات المواصفات، أخبرت تسجيل المقسوم، 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

يمكن كتابة خوارزمية القسم الطويلة هذه "المدرسة" هذه (في بيثون - سأسمح لك بتحويلها إلى 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

هناك طرق مختلفة - أود أن أقترح نيوتن رافسون, ، وهو بسيط وسريع، ويستخدم الضرب والطرح فقط فقط.

إذا لم يسمح الضرب، فهناك الكثير من خوارزميات القسم الصحيحة التي تستخدم التحولات، وعمليات bitwise وإضافة / طرح، على سبيل المثال، اضغط لأول مرة على Google: www.bearcave.com/software/divide.htm.