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，这会导致错误的答案。