我无法弄清楚非恢复整数除法的后期修正。出于某种原因,我不断遇到这样的情况:我在不需要更正的地方进行了更正,或者在需要时不更正
这是算法的伪代码。 红利
是16bits,其他是8bits。 Dividend_Sign
、Remainder_Sign
我的意思是它们的 MSB 是 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;
现在我基本上有了正确的答案,它只需要以一种或另一种方式进行后期更正……或者根本不进行后期更正。我不确定所有更正案例是什么。现在我有一半时间无法正常工作,但无论如何它在这里:
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
最佳答案
算法有效,问题是 2s 的补码有一个负零。如果最后的余数为 0,则永远不需要更正。但该算法必须在循环内检测到 0 余数,如果遇到余数,则始终需要进行校正。
只需添加一个 0 余数标志并执行此操作:
if (!Remainder.isEmpty() && (zeroFlag || (Dividend.Sign() XOR Remainder.Sign())))
...do corrections
关于algorithm - 非恢复有符号整数除法后校正,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10272975/