c++ - 如何在 C++ 中从头开始实现 bignum 加法/乘法

Question

我已经开始编写一个 bignum 库，其中包含一个短裤向量来表示值、一个打印函数和负数支持。但是，我找不到实现长加法的好方法，如下所示：

 123
+123
----
 246

我拥有的没有给出段错误的最新代码是这样的：

void add(unsigned long long b)
    {   
        for(long long i=v.size()-1;i>=0;--i)
        {
            if((b+v[i])<10)
                v[i]+=b;
            else // Carry
                {
                    if(i==0) // 1st digit
                    {
                        v.push_front(1); // Can't be more than 1
                    }
                    else
                        v[i-1]++; // Increment digit to the left
                }

        }
    }

，但带进位的加法不正确（10+1 是 21）

编辑：它被实现为一个类

Answer 1

考虑将 11 传递给函数：
如果vector[i]>= 0，则b+vector[i]> 11，因此b+vector[i]<10永远不会为真。

其他几件事：

• 您正在使用vectorand v，我很确定应该只有一个。

• i>0应该是i>=0，否则循环会跳过第一个元素。

• 让每个元素代表一个数字有点矫枉过正。您可以让每个元素表示 0-65535（无符号短整数范围）。只需将下面的 10 更改为 65535。或者 0-10000 也可能有意义，因为这样分解成数字会更简单。

• 该函数不应该接受 BigNum 类的类型参数吗？

• 从第一个元素到最后一个元素的循环会更有意义。

更好的（未经测试的）add功能可能如下所示：

const int BASE = 10;
void add(unsigned long long b)
{
    for (int i = 0; b > 0 && i < v.size(); ++i)
    {
        unsigned long long val = b + v[i];
        b = val / BASE;
        v[i] = val % BASE;
    }
    // if adding more digits
    while (b > 0)
    {
        v.push_back(b % BASE);
        b /= BASE;
    }
}