通过位移和减法进行的 C++ 除法无法正常工作

Question

我想实现一个 256 位整数类型来处理大数。也就是说，我不能使用默认的算术运算符，所以我必须用按位运算重新实现它们。

到目前为止，我已经对它们中的大多数进行了单独的工作和测试，但我无法通过除法。

我这样做的部分原因是出于学习目的，所以虽然 bignum 库是受欢迎的，但它们不是我目前正在寻找的东西。

我修改了另一个答案的代码，在这里: https://stackoverflow.com/a/19780781/1619594

Int_256 operator/(Int_256 dividend, const Int_256 &divisor) {
    Int_256 quotient = { 0, 0, 0, 0 };
    int nPos = -1;
    Int_256 tempDivisor = divisor;

    while (tempDivisor < dividend) {
        tempDivisor = tempDivisor << 1;
        nPos ++;
    }

    tempDivisor = tempDivisor >> 1;

    while (nPos > -1) {
        if (dividend >= tempDivisor) {
            quotient = quotient + (1 << nPos);
            dividend = dividend - tempDivisor;
        }

        tempDivisor = tempDivisor >> 1;
        nPos -= 1;
    }

    Int_256 remaining = dividend;

    return quotient;
}

一切都应该是无符号的，事实上“Int_256”只是 4 个 64 位无符号整数。

问题是，虽然它有时可以正常工作，但有时却不行。

例如:10/5 == 1，余数为 5，8/2 == 3，余数为 2，等等。

但是 35/5 和 10/2 会给出正确的结果。

有人知道我遗漏了什么问题吗？

更新:这是请求的完整代码:http://fecka.ddns.net/gogs/fecka/int256test

它不完整且困惑，可能有很多问题，一分钟前我发现，即使乘法也不能正常工作，所以任何帮助将不胜感激。

Answer 1

问题出在边缘情况上。你最初的 while 循环应该是

while (tempDivisor <= dividend)

也检查是否相等。没有它(在 10/5 的情况下)，tempDivisor 作为 10 从该循环中出来，立即被减半为 5，这会导致错误的答案。