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

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

4 个评论

  1. 作者您好,关于您的大数运算的代码,我有一处疑惑,就是ubig zero,好像不能把它的值赋成unsigned int num = 0,在check to_string处检验到zero的值并不等于0,但是在check relation处,zero < one又并没有报错,说明它的值又是比1小的,但是这是无符号数呀,总不可能是负数的,但是它好像又不是0,要是您有空的话可以帮我解决一下疑惑吗。

    1. 你好,我没有理解你的问题,你是说下面的代码输出的不是0吗

      int main() {
          kedixa::unsigned_bigint zero(0u);
          std::cout << zero.to_string() << std::endl;
          return 0;
      }
      
      kedixa
      1. 是的是的,我不清楚是不是to_string()函数对0的处理有问题,我添加了一句
        if (a.size()==1 && a[0] == 0) return “0”;
        就不会报错了

      2. 我这边暂时未能复现这个问题,可以提供一下你的编译器版本,系统环境(Windows/Mac/Linux),以及zero.to_string()得到的是什么内容吗?

        kedixa

发表回复

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