c++将存储在链表中的两个大数相乘

Question

我正在尝试编写一个将两个大数相乘的代码。两个数字都被划分并存储在一个链表中。

在我的例子中，每个节点都有 8 位数字。例如:324367823457572583 将存储为

32 | 43678234 | 57572583.

代码如下:

std::list<long long> multiply(const std::list<long long>& _a, const std::list<long long>& _b)
{
    std::list<long long> ret;
    int mod = 1e8, rem = 0;
    auto retit = ret.rbegin(), cur = retit;
    for(auto it2 = _b.rbegin(); it2 != _b.rend(); ++it2, ++cur)
    {
        retit = cur;

        for(auto it1 = _a.rbegin(); it1 != _a.rend(); ++it1, ++retit)
        {
            long long a = (*it2) * (*it1) + rem;
            if(retit == ret.rend())
                ret.push_front(a%mod);
            else
                a += *retit, *retit = a%mod;
            rem = a/mod;
        }
        *retit += rem, rem = 0;
    }
    return ret;
}

我相信这段代码应该可以工作，但它输出了错误的答案...

34677523234 * 672891258627 =

2333420 22549932 95439718(计算器输出)

2328204 22549932 95439718(我的输出)

Answer 1

你的乘法例程有多个问题。

• 两个整数相乘时32位溢出
• 取消引用指向 rend() 的 retit

这是 corrected version :

std::list<int> multiply(const std::list<int>& _a, const std::list<int>& _b)
{
    std::list<int> ret;
    int mod = 100000000, rem = 0;
    auto retit = ret.rbegin(), cur = retit;
    for (auto it2 = _b.rbegin(); it2 != _b.rend(); ++it2, ++cur)
    {
        retit = cur;

        for (auto it1 = _a.rbegin(); it1 != _a.rend(); ++it1, ++retit)
        {
            long long a = static_cast<long long>(*it2) * (*it1) + rem;
            if (retit == ret.rend())
                ret.push_front(a%mod);
            else
                a += *retit, *retit = a%mod;
            rem = (int)(a / mod);
        }
        if (rem)
        {
            if (retit == ret.rend())
                ret.push_front(rem);
            else
                *retit += rem;
            rem = 0;
        }
    }
    return ret;
}

样本输入的输出:

2333420 22549932 95439718