C++大整数运算（二）：加法和减法

C++大整数运算系列文章讲述了实现大整数四则运算的基本思路和方法，对算法做简单的介绍并采用C++代码做进一步说明。本文并不试图写成一篇教程，而是对实现过程进行整理和概括。实现过程中学习了 Donald E. Knuth 著作的 The Art of Computer Programming 中的相关内容，特此致敬。

本文是C++大整数运算系列文章的第二篇，主要介绍如何实现大整数运算的加减运算。

目录

• C++大整数运算（一）：概述
• C++大整数运算（二）：加法和减法
• C++大整数运算（三）：乘法
• C++大整数运算（四）：除法
• C++大整数运算（五）：进制转换

由于我们采用的是2^32进制，定义每个[0, 2^32)中的数为一个数位。

首先需要解决的是两个数位的带进位加法。我们选择的进制已经超过了unsigned类型的表达范围，因此两个数位相加可能会产生溢出，因此需要表达范围更大的数据类型来保存运算结果，比如：long long、unsigned long long。

// 带进位的一位加法，c(上一个进位)、x和y相加，结果保存到z中，并返回进位。
unsigned adder(unsigned x, unsigned y, unsigned c, unsigned &z)
{
    unsigned long long carry = unsigned long long(c) + x + y;
    z = unsigned(carry);
    carry >>= 32;
    return unsigned(carry);
}

虽然我们选择的是以2^32为基数，基本的运算还是和手工运算是一致的，即将数位对齐，依次计算。下面的函数计算两个“大整数”的和，并返回结果。

vector<unsigned> add(vector<unsigned> x, vector<unsigned> y)
{
    size_t lenx = x.size(), leny = y.size();
    vector<unsigned> z(max(lenx, leny));
    unsigned long long carry = 0;
    for(size_t i = 0; i < z.size(); ++i)
    {
        if(i < lenx) carry += x[i]; // >
        if(i < leny) carry += y[i]; // >
        z[i] = unsigned(carry); // 当前数位结果
        carry >>= 32;             // 当前进位
    }
    if(carry) z.push_back(carry); // 进位
    return std::move(z);
}

减法的操作和加法相似，但由于减法会因为不够减而产生借位，可能使用long long会比unsigned long long更方便。下面的函数计算两个“大整数”的差，假设x >= y。

vector<unsigned> sub(vector<unsigned> x, vector<unsigned> y)
{
    size_t lenx = x.size(), leny = y.size();
    vector<unsigned> z(lenx);
    long long borrow = 0;
    for(size_t i = 0; i < z.size(); ++i)
    {
        borrow += x[i]; 
        borrow -= (i < leny) ? y[i] : 0; // >
        z[i] = unsigned(borrow); 
        borrow >>= 32;
    }
    return std::move(z);
}

上述代码只处理了 x >= y的情况，对于不够减的情况，应当抛出异常，或者其他方法表示减法出现了错误。此时我们只考虑无符号数的减法，不够减的情况原则上应当产生一个负数，这里暂时忽略。

上述代码中我们将结果分配了与x相同长度的数组，但相减之后可能会导致结果位数减少，还需要做进一步处理。

本文简单介绍了大整数加法和减法的基本运算，但为了简洁而忽略了一些细节，需要的读者可以到这里查看完整的代码。下一节将会简单介绍乘法运算。