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

Question

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

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

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

我修改了另一个答案的代码，在这里：

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

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

C++ division by bit shifting and substractiing won't work correctly

c++

binary

division