1

我无法弄清楚非恢复整数除法的后更正。出于某种原因，我不断收到不需要更正或在需要时不更正的情况

这是算法的伪代码。Dividend是 16 位，其他是 8 位。，我的意思是它们的 MSB 是 1 Dividend_Sign，Remainder_Sign所以它们是 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

4

1 回答 1

1

该算法有效，问题是 2s 补码有一个负零。如果最后的余数为 0，则不需要更正。但该算法必须在周期内检测到 0 余数，如果遇到余数，则始终需要进行更正。

只需添加一个 0 余数标志并执行此操作：

if (!Remainder.isEmpty() && (zeroFlag || (Dividend.Sign() XOR Remainder.Sign())))
      ...do corrections
于 2012-04-25T21:55:10.317 回答