非還原有符號整數除法後校正

我無法找出非還原整數除法的後校正。出於某種原因，我不斷收到我糾正的地方，不需要更正或不需要糾正的地方非還原有符號整數除法後校正

繼承人僞碼算法。 Dividend是16位，其他8位。通過Dividend_Sign,Remainder_Sign我的意思是他們的最高有效位是1，所以他們是否定的2補碼。

LoopCounter = 8; 
do { 
    Shift Dividend Left with 0 in LSB; 

    if (Dividend_Sign XOR Divisor_Sign) { 
     Shift 0 into Quotient; 
     DividendHighByte = DividendHighByte + Divisor; 
    } else { 
     shift 1 into Quotient; 
     DividendHighByte = DividendHighByte - Divisor; // subtraction by 2's complement 
    } 
} while (loopCounter != 0); 

Remainder = DividendHighByte; 

// here i do the Quotient conversion 
invert MSB; // shifted out anyway. Probably should be used for overflow check, not important atm. 
shift 1 into Quotient;

現在一個地步，我基本上都正確的答案IM，它只是需要進行後糾正了這樣或那樣的......或者根本沒有糾正後。林不知道所有的糾正情況是什麼。現在我有一個心不是工作一半時間的東西，但在這裏它是無論如何：

if (Dividend_Sign XOR Remainder_sign) {  // diff signs so correct 
    if (Remainder_Sign XOR Divisor_Sign) { // diff signs just add 
     Remainder = Remainder + Divisor; 
     Quotient = Quotient - 1; 
    } else { 
     Remainder = Remainder - Divisor; 
     Quotient = Quotient + 1; 
    } 
}

http://en.wikipedia.org/wiki/Division_%28digital%29

http://www.acsel-lab.com/arithmetic/papers/ARITH17/ARITH17_Takagi.pdf

來源

2012-04-22 ollo

你能否詳細說明，或至少列舉，不工作的案件？ – 2012-04-22 23:38:48

atm發現-10：2和-10：-2是正確的預校正和糾正混亂。 -16：4需要更正，但沒有。我認爲這與他們剩下0分有關。 – ollo 2012-04-23 00:10:14

請解釋一旦校正完成後剩餘部分所需的要求（暫時忽略如何完成校正）。 – 2012-04-23 00:16:23

該算法的作品，問題是二進制補碼有一個負零。如果最後的餘數爲0，則不需要更正。但算法必須在週期內檢測0個餘數，並且如果遇到其中一個，則必須進行校正。

只是增加了一個0餘旗，這樣做：

if (!Remainder.isEmpty() && (zeroFlag || (Dividend.Sign() XOR Remainder.Sign()))) 
     ...do corrections

來源

2012-04-25 21:55:10 ollo

二進制補碼不具有負零。 1的補碼確實符號大小也是如此。 – 2012-04-25 23:58:11

這實際上是一個非常有價值的解決方案，用於簽署非恢復分區方案中的後續更正。通常不會考慮零部分餘數或最終餘數的情況，例如http://www.google.ru/search?q=computer+arithmetics+behrooz+parhami+pdf，儘管在那裏會考慮正常的後校正。如果沒有零餘數的校正後情況，該算法最終會給出與真實答案相差+ -1的錯誤結果（我現在只考慮商數，而不是餘數）。所描述的修復似乎在100％的情況下返回正確的商數。 – lvd 2015-01-21 05:22:44

非還原有符號整數除法後校正

回答

相關問題