C++大整数运算(二):加法和减法

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

本文是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相同长度的数组,但相减之后可能会导致结果位数减少,还需要做进一步处理。

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注