基础算法：高精度大整数运算

数据结构与算法

2745

2021-08-08

对于C/C++来说，它没有大整数运算类，那么在计算一些与大整数有关的操作时，应该怎么办呢？

…

高精度大整数运算

只针对C来说，因为C没有大整数类，而java具有大整数类，python的整数是无限位的

对于大数运算，一般有以下几种情况：

$A + B$ 型，其中这两个的位数大概在 $10^6$
$A - B$ 型，其中这两个的位数大概在 $10^6$
$A \times \alpha$ ，其中A的长度不超过 $10^6$ ， $\alpha$ 是一个小整数，不超过 $10^5$
$A \times B$ 型，两个都是超长的整数，但是面试时要让写的概率不大
$\frac{A}{B}$ 型，两个都是超长的正数，面试时让写的概率不大

基本思想

大整数的存储

由于位数较多，一个int变量根本存放不下（可表示的最大整数是2147483647，共10位，并不能存放的下），所以可以使用数组来进行存放。

在使用数组存放的时候就有一个问题，采用小端方式还是大端方式存放，哪一个对要做的高精度整数运算更加方便呢？比较建议的是使用小端方式，即：低地址（数组下标0开始）存放个位，然后依次往后存放高位。

采用小端方式存放的原因是，在做运算时会有进位，如果从数组下标0开始依次存放大整数的个位的话，方便进位操作。因为可能会出现需要在高位补上额外的一个1，对于数组来说，在下标0处添加高位进位还需要将后面的数依次向后移动一个位置，降低了效率；而在最后面补上进位的话就方便许多，并不需要进行移位操作。

由于可能会出现混合运算，因此对于大整数的加减乘除都需要保证存储格式要一致。

大整数的运算

其实本质上就是模拟小学学过的竖式运算。

要注意，本专题讨论的大整数运算的前提是两个大整数都是非负数，即： $A \ge 0, B\ge 0$ 。如果不都是非负数，则是输入输出的问题了。

大整数加法

竖式加法运算的步骤：

个位与个位相加，如果计算结果大于10，则向前进位，并对10取余（模），得到最终结果的个位应该存放的值
然后是十位与十位相加，并加上进位。如果计算结果大于10，继续向前进位，并对10取余，得到最终结果的十位应该存放的值
重复上述操作，直到计算完毕

观察上述计算步骤，其实是三个数在做加法：两个位置的数相加再加上进位得到结果。

大整数减法

竖式减法运算的步骤：

个位与个位相减，如果不够减，则向前借一位，即：被减数的个位 + 10 - 减数的个位；被减数的十位要减去1
然后轮到十位进行上述运算
重复上述操作，直到计算完毕

上述运算步骤其实是三个数在参与运算：

如果没有借位的话，则是 $A_i - B_i + Carry$ ，此时借位carry为0
如果有借位的话，则是 $A_i + Carry - B_i$ ，此时借位carry为10

因此，做大整数减法的话是要分两个步骤

如果A小于B，则计算 $-(B - A)$ 。即，先交换做减法，后补上一个负号
如果A不小于B，则直接做减法即可

大整数乘法

与加减法的比较类似，只需要找到其中几个关键点：

进位的值等于 $carry = \lfloor (A[i] \times B) / 10 \rfloor$
当前位的值 $(A[i] \times B)\% 10$
高位的值为 $(A[i+1] \times B + carry) % 10$

需要注意的是，它是用A的每一位整体乘以的B，所以要求B不能太大，int能存放的下才行。

大整数除法

前提是高精度的整数除以低精度的整数，与大整数乘法的要求差不多。

回顾除法的竖式计算，设余数为r，被除数为A，除数为b，商为q，则有： $q = (r * 10 + A[i]) / b,r = (r * 10 + A[i]) \% 10$ 。简单的来说就是：

商等于高精度整数A的当前位加上余数乘以10除以除数。也就是列竖式中第二步中，高位的商求出来后，继续进行下一步的运算时的落式运算
求落式运算中，做完减法剩下来的余数的高位是多少

为了统一操作，高精度整数的加减乘除都使用哨兵，记初始状态的进位为0，从而可以省略了分支结构。

需要注意的是：

大整数除法是从高位开始的，而其他三种运算都是从低位开始做运算的
由于大整数除法是从高位开始做运算的，因此为了统一大整数的存储格式，其最后运算的结果要使用reverse(vector.begin(), vector.end())来做逆置操作

算法模板

大整数加法

迭代式

// A >= 0, B >= 0
vector<int> add(const vector<int>& A, const vector<int>& B) {
    vector<int> ans;
    
    int carry = 0;
    // 由于没有判断A和B哪个位数更长，而加法运算需要对每一个数位上的值都要加上一遍
    // 因此不能提前退出，使用或条件
    for (int i = 0; i < A.size() || i < B.size(); ++i) {
        int result = carry;
        // 当要加上的整数还没运算完时，加上对应的位置上的整数
        if (i < A.size()) {
            result += A[i];            
        }
        
        if (i < B.size()) {
            result += B[i];
        }
        
        // 对10取模，得到该位置上的值
        ans.push_back(result % 10);
        // 计算进位
        carry = result / 10;
    }

    // 当还有进位的时候，证明需要在最高位补上一个1
    if (carry) {
        ans.push_back(carry);
    }
    
    return ans;
}

递归式

vector<int> add(const vector<int>& A, const vector<int>& B) {
      // 让竖式计算的最上面的那个整数是最长的
      if (A.size() < B.size()) {
            return add(B, A);
      }    
            
    vector<int> ans;
    int carry = 0;
    for (int i = 0; i < A.size(); ++i) {
        int result = carry +  A[i];
        
        // 当要加上的整数还没运算完时，加上对应的位置上的整数
        if (i < B.size()) {
            result += B[i];
        }
        
        // 对10取模，得到该位置上的值
        ans.push_back(result % 10);
        // 计算进位
        carry = result / 10;
    }
    
    // 当还有进位的时候，证明需要在最高位补上一个1
    if (carry) {
        ans.push_back(carry);
    }
    
    return ans;
}

大整数减法

比较两个大整数谁大

// 比较大整数A是否不小于大整数B
bool cmp(const vector<int>& A, const vector<int>& B) {
    if (A.size() != B.size()) {
        return A.size() >= B.size();
    }
    
    for (int i = A.size() - 1; i >= 0; --i) {
        // 这三个连续的if可以做优化，合并掉多余的操作
        if (A[i] == B[i]) {
            continue;
        } else if (A[i] > B[i]) {
            return true;
        } else {
             return false;
        }
    }
    
    return true;
}

for循环遍历的优化写法，省掉了多个分支判断：

// 比较大整数A是否不小于大整数B
bool cmp(const vector<int>& A, const vector<int>& B) {
    if (A.size() != B.size()) {
        return A.size() >= B.size();
    }
    
    for (int i = A.size() - 1; i >= 0; --i) {
        // 根据上面的分支情况，可以归结为，当两个值不等时，比较它俩的大小
        // 因此可以写成下面的这种情况
        if (A[i] != B[i]) {
            return A[i] > B[i];
        }
    }
    
    return true;
}

大整数减法模板

/* 先利用大整数比较，来将问题转为A - B的情况
vector<int> ans;
// 比较A是否不小于大整数B
if (cmp(A, B) == true) {
    ans = sub(A, B);
    
} else {
    ans = sub(B, A);
    printf("-");
}
*/

vector<int> sub(const vector<int>& A, const vector<int>& B) {
    vector<int> ans;
    
    // A一定不小于B，初始时，没有借位
    int carry = 0;
    for (int i = 0; i < A.size(); ++i) {
        // 初始时是个位进行相减，假设当前并没有借位，所以初始的借位值carry为0
        int tmp = A[i] - carry;
        // 当B还没减完时，需要继续减，变为A[i] - B[i]
        if (i < B.size()) {
            tmp = tmp - B[i]; 
        }
        // 当A[i] - B[i]的值小于0时，则A[i + 1]需要减去1
        // 因此需要将借位标志carry记为1，在下次循环时将借位减掉
        // 下列分支其实可以进行优化
        if (tmp < 0) {
            carry = 1;
            ans.push_back((tmp + 10) % 10);
        } else {
            carry = 0;
            ans.push_back(tmp % 10);
        }
    }
    
    // 如果高位都是0，则要将这些前导0都要删掉，如果最后结果就是0，则最后一个0不能弹出
    while (ans.size() > 1 && ans.back() == 0) {
        ans.pop_back();
    }
    
    return ans;
}

上述将两个数的各个位相减后的结果存储在结果数组中时，使用了分支结构。根据其功能以及取模操作%的数学含义，其实可以将上述分支取消掉，只保留计算借位标志carry的分支即可，变为：

/* 先利用大整数比较，来将问题转为A - B的情况
vector<int> ans;
// 比较A是否不小于大整数B
if (cmp(A, B) == true) {
    ans = sub(A, B);
    
} else {
    ans = sub(B, A);
    printf("-");
}
*/

vector<int> sub(const vector<int>& A, const vector<int>& B) {
    vector<int> ans;
    
    // A一定不小于B，初始时，没有借位
    int carry = 0;
    for (int i = 0; i < A.size(); ++i) {
        // 初始时是个位进行相减，假设当前并没有借位，所以初始的借位值carry为0
        int tmp = A[i] - carry;
        // 当B还没减完时，需要继续减，变为A[i] - B[i]
        if (i < B.size()) {
            tmp = tmp - B[i]; 
        }
       // 当tmp < 0 时，加上10取余没毛病；
       // 当tmp >= 0时，由于10 % 10 == 0，所以不影响最终结果
       // 故存放的还是tmp % 10其本身，所以可以去掉那个分支结构
       ans.push_back((tmp + 10) % 10);

        // 当A[i] - B[i]的值小于0时，则A[i + 1]需要减去1
        // 因此需要将借位标志carry记为1，在下次循环时将借位减掉
        if (tmp < 0) {
            carry = 1;
        } else {
            carry = 0;
        }
    }
    
    // 如果高位都是0，则要将这些前导0都要删掉，如果最后结果就是0，则最后一个0不能弹出
    while (ans.size() > 1 && ans.back() == 0) {
        ans.pop_back();
    }
    
    return ans;
}

大整数乘法

vector<int> mul(const vector<int>& A, const int& B) {
    vector<int> ans;
    
    int result = 0;
    // 当A的各个位都已经乘完乘数后，如果还有进位
    // 则将进位的整数分解成若干个整数存放到答案数组中
    // 因为A[i] * B的进位可以不只是1位数，可能是多位的整数
    for (int i = 0; i < A.size() || result; ++i) {
        if (i < A.size()) {
            result += A[i] * B;
        }
        
        // 求当前位置上应该留下的值
        ans.push_back(result % 10);
        // 求进位了多少值，与加法的很类似，但是加法最多进位是1
        // 而大整数乘法它的进位不一定是1，可能是具有若干个位的整数
        result = result / 10;
    }
    
    // 如果B为0，则需要将前导0去除，其实这个特殊情况可以放到函数入口处先判断
    // 可以不进入那个循环，提升效率
    while (ans.size() > 1 && ans.back() == 0) {
        ans.pop_back();
    }
    
    return ans;
}

将上述代码优化后，可以提升效率：

vector<int> mul(const vector<int>& A, const int& B) {
    vector<int> ans;
    if (B == 0) {
        ans.push_back(0);
        return ans;
    }
    
    int result = 0;
    // 当A的各个位都已经乘完乘数后，如果还有进位
    // 则将进位的整数分解成若干个整数存放到答案数组中
    // 因为A[i] * B的进位可以不只是1位数，可能是多位的整数
    for (int i = 0; i < A.size() || result; ++i) {
        if (i < A.size()) {
            result += A[i] * B;
        }
        
        // 求当前位置上应该留下的值
        ans.push_back(result % 10);
        // 求进位了多少值
        result = result / 10;
    }
    
    return ans;
}

上述代码的for循环的终止条件使用了一个或条件，其为了省略一个循环，如果不添加或条件，需要额外添加一个循环如下所示：

vector<int> mul(const vector<int>& A, const int& B) {
    vector<int> ans;
    if (B == 0) {
        ans.push_back(0);
        return ans;
    }
    
    int result = 0;
    // 当A的各个位都已经乘完乘数后，如果还有进位
    // 则将进位的整数分解成若干个整数存放到答案数组中
    // 因为A[i] * B的进位可以不只是1位数，可能是多位的整数
    for (int i = 0; i < A.size(); ++i) {
        result += A[i] * B;
        // 求当前位置上应该留下的值
        ans.push_back(result % 10);
        // 求进位了多少值
        result = result / 10;
    }
    
      while (result) {
          ans.push_back(result % 10);
          result = result / 10;
      }
    return ans;
}

大整数除法

要求除数一定不为0，且A为高精度整数，b为低精度整数，且A和b都为非负数，A不小于b。

其实思想很简单，就是模拟竖式除法。模拟的方法有很多，但是其中比较简单的一个思路是从余数下手。设除数为B，余数为r，商为q，从被除数的最高位开始计算，有：

竖式除法中，每次运算求出一位商的时候，都是先计算上一步运算后得到的余数。而当前的余数应该是 $r_i = r_{i - 1} * 10 + A_i$
根据当前的余数，计算当前步的商和余数，其中商为 $r_i / B$ ，余数为 $r_i \% B$
不断的根据上面的步骤来进行迭代，直到被除数的每一位都参与运算过

计算完毕后，由于大整数存储是按照小端方式存放，因此需要将结果逆置后再输出。

代码模板为：

vector<int> div(const vector<int>& A, int b, int& r) {
    vector<int> q;
    
    // r为余数，且为哨兵
    r = 0;
    for (int i = A.size() - 1; i >= 0; --i)
    {
        r = r * 10 + A[i];
        q.push_back(r / b);
        r = r % b;
    }
    
    // 由于大整数的存储是按照小端序存储的，因此需要将最后的结果逆置
    reverse(q.begin(), q.end());
    
    // 去除前导0
    while (q.size() > 1 && q.back() == 0) {
        q.pop_back();
    }
    
    return q;
}

#大整数运算 ¹ #C++大整数运算 ¹ #大整数加法 ¹ #大整数减法 ¹ #大整数乘法 ¹ #大整数除法 ¹ #基础算法 ⁵

基础算法：前缀和与差分

C++逆向：switch-case逆向分析与还原

digSelf

digSelf

基础算法：高精度大整数运算

高精度大整数运算

基本思想

大整数的存储

大整数的运算

大整数加法

大整数减法

大整数乘法

大整数除法

算法模板

大整数加法

迭代式

递归式

大整数减法

比较两个大整数谁大

大整数减法模板

大整数乘法

大整数除法

分享