2017年7月24日

高精度整数的运算

高精度整数的运算

本文中代码已通过洛谷P1601、P2142、P1303、P1480、P2005（封装导致TLE）、P1932（不压位数组长度不够）。

10进制高精度整数

存储

由于高精度运算的原理就是模拟手算竖式的过程，因此我们采用倒序存储应该会较为方便。等到我们需要输出时再将它正序输出即可。

以下代码如有出现

bint a = *this;

请使用自己喜欢的方法替代它，这是不建议使用的方法。（只是我懒得改233）

struct bint { // 封装 
    int num[1005], len;
    bool neg;
    
    bint(string s) {
        neg = false;
        int cnt = 0;
        for(string::reverse_iterator it = s.rbegin(); it != s.rend(); it++) { // 倒序存储 
            num[cnt] = (*it) - '0';
            cnt++;
        }
        if(cnt == 0) {
            num[0] = 0;
            cnt++;
        }
        for(int i = cnt - 1; i >= 1; i--) { // 处理前导0 
            if(num[i] == 0) cnt--;
            else break;
        } 
        len = cnt;
    }

    void print() {
        if(neg && *this != bint("0")) printf("-");
        for(int i = len - 1; i >= 0; i--) {
            printf("%d", num[i]);
        }
    }
};

比较

按位比较，没什么好说的。

 /* 关系运算符 按需实现 注意：并不带符号比较（仅比较绝对值） */ 
    bool operator > (const bint &b) {
        bint a = *this;
        if(a.len > b.len) return true;
        if(a.len < b.len) return false;
        for(int i = a.len - 1; i >= 0; i--) { 
            if(a.num[i] > b.num[i]) return true;
            if(a.num[i] < b.num[i]) return false;
        }
        return false;
    }
    
    bool operator < (const bint &b) { 
        bint a = *this; 
        if(a.len > b.len) return false;
        if(a.len < b.len) return true;
        for(int i = a.len - 1; i >= 0; i--) { 
            if(a.num[i] > b.num[i]) return false;
            if(a.num[i] < b.num[i]) return true;
        }
        return false;
    }
    
    bool operator == (const bint &b) {
        bint a = *this;
        if(a.len != b.len) return false;
        for(int i = 0; i < a.len; i++) { 
            if(a.num[i] != b.num[i]) return false; 
        } 
        return true; 
    } 

    bool operator != (const bint &b) { 
        bint a = *this; 
        return !(a == b); 
    } 

    bool operator >= (const bint &b) {
        bint a = *this;
        if(a.len > b.len) return true;
        if(a.len < b.len) return false;
        for(int i = a.len - 1; i >= 0; i--) { 
            if(a.num[i] > b.num[i]) return true;
            if(a.num[i] < b.num[i]) return false;
        }
        return true;
    }   
    
    bool operator <= (const bint &b) { 
        bint a = *this; 
        if(a.len > b.len) return false;
        if(a.len < b.len) return true;
        for(int i = a.len - 1; i >= 0; i--) { 
            if(a.num[i] > b.num[i]) return false;
            if(a.num[i] < b.num[i]) return true;
        }
        return true;
    }

加减法

高精度加法的原理基本是模拟手算的过程，即按位相加，超10进位。为了减少按位相加的次数，我们让较长的数加上较短的数，这样计算时循环的次数便是较短数的位数。每次按位相加记录进位并%=10，就可以实现进位。

至于高精度减法，同样也是模拟竖式计算。按位相减，退位记下来标记在下一位上。细节方面需要注意的是如果有前导0要记得删去，标记退位后要把该位补成正数。

这里的代码实现有功能限制，比如只接受操作数为正整数，但是减法可以得到一个负数。

    bint operator + (bint &b) {
        bint a = *this;
        if(a < b) swap(a, b);
        for(int i = 0; i < b.len; i++) { 
            a.num[i] += b.num[i]; 
        }
        int nxt = 0;
        for(int i = 0; i < a.len; i++) { // 处理进位 
            a.num[i] += nxt; nxt = a.num[i] / 10; 
            a.num[i] %= 10; 
        } if(nxt > 0) {
            a.num[a.len] = nxt;
            a.len++;
        }
        return a;
    }
    
   bint operator - (bint &b) {
    bint a = *this;
    if(a < b) {
        swap(a, b);
        a.neg = true;
    }
        for(int i = 0; i < b.len; i++) {
            a.num[i] -= b.num[i];
        }
        int nxt = 0;
        for(int i = 0; i < a.len; i++) { // 处理进位 
            a.num[i] += nxt;
            nxt = 0;
            if(a.num[i] < 0) { 
                nxt = -1; 
                a.num[i] += 10; 
            } 
        } 
        for(int i = a.len - 1; i >= 1; i--) { // 处理前导0 
            if(a.num[i] == 0) a.len--;
            else break;
        } 
        return a;
    }

乘法

乘法的原理依然是列竖式计算，这里我们用一例124*128讲解。

       1  2  4
   ×   1  2  8
--------------
       9  9  2
    2  4  8
 1  2  4
--------------
 1  5  8  7  2

在我们的手算列竖式的过程中，我们通常用乘数乘以被乘数的每一位，并顺便完成进位和求和的工作。在计算机中，每一步都要进位是一件很低效的事情，我们看看如果不自动进位会发生什么。

       1  2  4
   ×   1  2  8
--------------
       8 16 32
    2  4  8
 1  2  4
--------------
 1  5  8  7  2

可以发现，除了第一行8 16 32没有进位以外，其他并无差别。也就是说我们可以先把这个答案的每一位计算出来再处理进位。

进位的事情考虑完了，现在让我们考虑怎么得到答案每一位对应的数。在竖式中我们利用了对齐直接上下相加就可以得到，让我们给乘数和被乘数加个编号观察会发生什么。

       1  2  4
      (2)(1)(0)   i
   ×   1  2  8
      (2)(1)(0)   j
--------------
       8 16 32
    2  4  8
 1  2  4
--------------
(4)(3)(2)(1)(0)   k

由于我们倒序存储高精度数，自然要倒序运算。我们可以观察到答案的第k位可以由所有的i+j=k中乘数的第i位和被乘数的第j位数字的乘积的和得到，即以下式子。

c\left[ k\right] =\sum _{i+j=k}^{i,j}a\left[ i\right] \cdot b\left[ j\right]

我们很快能算出答案的各位数。至于处理进位直接看加法的处理方法就好。

 bint operator * (bint &b) {
        bint a = *this;
        if(a == bint("0") || b == bint("0")) return bint("0");
        bint c = bint("0");
        memset(c.num, 0, sizeof c.num);
        for(int i = 0; i < a.len; i++) {
            for(int j = 0; j < b.len; j++) {
                c.num[i + j] += a.num[i] * b.num[j]; 
            }
        } 
        c.len = a.len + b.len - 1;
        int nxt = 0;
        for(int i = 0; i < c.len; i++) { // 处理进位 
            c.num[i] += nxt; 
            nxt = c.num[i] / 10; 
            c.num[i] %= 10; 
        } 
        if(nxt > 0) c.num[c.len++] = nxt;
        return c;
    }

除法与取模

高精度数模低精度数

让我们回想一下我们在列竖式计算除法的时候是如何计算出最终余数的。以130987/21为例。

      6237
   -------
21 )130987
    126
    ------
      49        ←
      42
    ------
       78       ←
       63
    ------
       157      ←
       147
    ------
        10      ←

此例中，每一个被标注了←符号的步骤中，完成的是同一件事：取某几位对除数取模，将得到的结果扩大10倍并补上下一位继续计算（语文不太好……如果听不懂看代码吧qwq）。这便是我们模拟取模的方法。其实如果要证明也很容易，由取模的分配律(a + b) mod c = (a mod c + b mod c) mod c易得（其实我也不知道怎么得来的）。下面上代码。

    int operator % (int b) {
        int c = 0;
        bint a = *this;
        for(int i = a.len - 1; i >= 0; i--) {
            c *= 10;
            c = (c + a.num[i]) % b; 
        }
        return c;
    }

高精度数除以低精度数

从上面取模的过程中来看，我们只需要在取模的同时记录商就可以达到除法的效果。

 bint operator / (int b) {
        int c = 0;
        bint a = *this;
        for(int i = a.len - 1; i >= 0; i--) {
            c *= 10;
            c += a.num[i];
            a.num[i] = c / b;
            c %= b;
        }
        for(int i = a.len - 1; i >= 1; i--) { // 处理前导0 
            if(a.num[i] == 0) a.len--;
            else break;
        } 
        return a;
    }

高精度数除以高精度数

让我们回想我们在作竖式除法时候的步骤。仍以130987/21为例。

      6237
   -------
21 )130987
    126       ←
    ------
      49        
      42      ←
    ------
       78       
       63     ←
    ------
       157      
       147    ←
    ------
        10

这次打←符号的位置不同了。这是因为我们在每一个打←符号的步骤上都做了这么一件事情。一是选择被除数的几位补成一个恰好大于除数的数字，然后再找除数的几倍恰好小于这个数。这个倍数就成为了商其中的一位。由于我们并不想要把商算到小数点后面，自然会抛弃最后的余数，即对商向下取整。接下来要做的就是模拟刚刚的操作。

就实现上而言，我们可以把找倍数这样一个操作简化为“能减几个该数”这样的问题，并用while循环处理它即可。大家可以发现，商的位数不会大于被除数的长度减除数的长度，因此可以以这个量作为大循环的循环次数。下面是代码

 bint operator / (bint b) {
        bint a = *this;
        if(a < b) return bint("0");
        if(a == b) return bint("1");
        bint c = b;
        for(int i = 0; i < a.len - b.len; i++) { 
            c = c * bint("10"); 
        } char ans[MAXN]; 
        int now = 0; 
        int cnt = 0; 
        for(int i = a.len - b.len; i >= 0; i--) {
            while(a >= c) {
                now++;
                a = a - c;
            }
            ans[cnt] = now + '0';
            cnt++;
            now = 0;
            c = c / 10; 
        } 
        return bint(string(ans)); 
    }

高精度数模高精度数

此处我们仍可以借鉴上面的除法。可以发现其实减到最后小于除数的a就是整个除法做完之后得到的余数，那么我们把除法中一些不必要的步骤删去后模拟该过程并返回a就能得到余数。

 bint operator % (bint b) {
        if(b == bint("1")) return bint("0");
        bint a = *this;
        if(a < b) return a;
        if(a == b) return bint("0");
        bint c = b;
        for(int i = 0; i < a.len - b.len; i++) { 
            c = c * bint("10"); 
        } 
        for(int i = a.len - b.len; i >= 0; i--) {
            while(a >= c) {
                a = a - c;
            }
            c = c / 10; 
        } 
        return a; 
    }

需要注意的是，这里有一些特判，a<b时a%b=a和a%1=0都是需要注意的地方。

参考资料

  1. C语言中的高精度乘法 - longj's coding workbench - CSDN博客
  2. C语言 高精度减法 - Silence的程序实验室 - CSDN博客
  3. 【图文】高精度取模_百度文库
  4. 高精度取模 - 咸鱼 - CSDN博客
  5. C++的运算符重载 - 很不错的 blog - CSDN博客
  6. 算法总结——大整数除法 - LJWLgl的博客 - CSDN博客
  7. 题解 P1932 - 百科 - 洛谷
  8. 题解 P2005 - 百科 - 洛谷

注意

本文中所有示例代码都使用struct简单封装，但是实际遇到问题并不需要如此封装，因此你可以将其写的稍微裸一些来减少封装可能带来的额外时空开销。

高精度数压位运算

高精度的压位即是指上面int数组中一个位置存储不止1位的数字，相当于把一个10进制数转换成10n进制数进行存储和运算。压位后的高精度在进位上有些许不同，但是运算过程基本相同。

之后的重点并不会放在高精度上，因此这一章的更新也许会延后，实在抱歉。

高精度运算的其他应用

高精度运算尤其是运算后的进位是可以规定当前数的进制的。下面是一些高精度解决多进制运算问题的例题。

洛谷P1581、P1604

之后的重点并不会放在高精度上，因此这里可能不会有内容，实在抱歉。

Author:
Filed Under: 算法, 知识, Slider
Tags: , ,

发表回复

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

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。