c++ - 大整数加法，我知道理论......在实践中仍然生疏

所以，我正在尝试构建一个简单的大整数类，我已经阅读了互联网上的一些页面以及所有这些，但我被卡住了。我知道这个理论，我知道我需要一个进位，但我见过的所有例子，他们更多地关注字符和基数 10，好吧，我正在使用不同的方法来使它更快一点。我会很感激加号赋值运算符的一些帮助，其余的我会尝试自己解决。

#include <iostream>
#include <string>
#include <vector>

using std::cout;
using std::endl;

class big_integer {
    using box = std::vector<int unsigned>;
    box data {0};

    box split(std::string const & p_input) const {
        box output;
        for (size_t i {}; i < p_input.size(); i += 8) {
            output.push_back(stoi(p_input.substr(i, 8)));
        }
        return output;
    }

public:
    big_integer(std::string const & p_data)
        : data {split(p_data)}
    {}

    big_integer(int unsigned const p_data)
        : data {p_data}
    {}

    big_integer & operator +=(big_integer const & p_input) {
        int carry {};

        for (size_t i {}; i < data.size(); ++i) {

            //Need help here!
            //All examples I see either use primitive arrays
            //or are too esoteric for me to understand.
            //data[i] += p_input.data[i] + carry;

        }

        return *this;
    }

    std::string to_string() const {
        std::string output;
        output.reserve(data.size() * 8);
        for (auto const i : data) {
            output.append(std::to_string(i));
        }
        return output;
    }
};

std::ostream & operator <<(std::ostream & p_output, big_integer const & p_input) {
    return p_output << p_input.to_string();
}

int main() {
    big_integer test1 {"126355316523"};
    big_integer test2 {255};

    test1 += test1;

    cout << test1 << endl;
    cout << test2 << endl;
    return 0;
}

最佳答案

正确的。所以基本的问题是如何做 unsigned + unsigned + carry 给 unsigned 和 carry 。如果我们考虑 16 位整数(它在 32 位中工作相同，但输入更多)，在第一个数字上，0xFFFF + 0xFFFF == 0xFFFE + 1 进位。在后续数字上 0xFFFF + 0xFFFF + 进位 == 0xFFFF + 进位。因此carry只能是一个。算法是:

    unsigned lhs, rhs, carry_in;  // Input
    unsigned sum, carry_out;      // Output

    sum = lhs + rhs;
    carry_out = sum < lhs ;
    sum += carry_in;
    carry_out = carry_out || sum < lhs;

基本上，这个想法是在 unsigned 中进行添加，然后检测包装(并因此进位)。非常烦人的是，这是大量的条件逻辑和实现“带进位加法”的多条指令，这是我使用过的每个指令集中的一条指令。 (注意:carry_out 的最终计算可能值得使用 | 而不是 || - 它节省了分支，这对性能不利。一如既往，分析看看是否有帮助。)

如果您最终要支持乘法，则需要一种宽度是“数字”两倍的类型 - 在这种情况下，您也可以将其用于加法。使用上面的变量，并假设“unsigned long long”是你的“wide”类型:

    const auto temp = (unsigned long long)lhs + rhs + carry_in;
    sum = temp; // Will truncate.
    carry_out = temp > UINT_MAX;

选择“宽”类型可能会很棘手。首先，最好将 uint32_t 用于数字，将 uint64_t 用于宽类型。

有关实现多精度算术的更多详细信息，Chapter 14 from Handbook of Applied Cryptography 看起来很有用。

关于c++ - 大整数加法，我知道理论......在实践中仍然生疏，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41077514/

0xffff

c++ - 大整数加法，我知道理论......在实践中仍然生疏