大整数与int型数据的除法

大整数与int型数据的除法也可以叫做高精度与低精度的除法，所谓的高精度就是基本数据类型无法存储的数据，比如1000个数位的整数；而所谓的低精度就是可以用基本数据类型存储的数据，比如int类型。那么该如何进行相除呢？其实本质上和小学的乘法是一样的。我们将无法储存的大整数放进int型的数组，大整数的高位存储在数组的高位，低位存储在数组的低位。从大整数的高位开始，上一步的余数(余数的初始值为0)乘以10加上该步的位，得到该步临时的被除数，将其与除数比较：如果不够除，则该位的商为0；如果够除，则商即为对应的商，余数即为对应的余数。最后一步需要注意高位可能有多余的0，要去除，但同时也要保证至少有一位数。有一点需要注意的是：这里的除法函数当中使用了引用变量，引用不产生副本，而是给原变量取了一个别名，对引用变量的操作就是对原变量(即算法中的全局变量)的操作。这里的算法没有考虑大整数和整数为负的情况。具体的算法如下：

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

struct bign {
    int d[1000];//使用int型数组存放大整数的每一位。
    int len;//记录大整数的长度。
    bign() {//"构造函数"用于初始化结构体。
        memset(d, 0, sizeof(d));
        len=0;
    }
};

bign change(char str[]) {//将存储在字符数组中的大整数转换为bign
    bign a;
    a.len = strlen(str);
    for (int i = 0;i < a.len;i++) {//大整数的高位存储在数组的高位，低位存储在数组的低位。
        a.d[i] = str[a.len - i - 1] - '0';
    }
    return a;
}

bign divide(bign a, int b,int &r) {//a/b
    bign c;
    c.len = a.len;//被除数的每一位和商的每一位是一一对应的。
    for (int i = c.len - 1;i >= 0;i--) {//从高位开始除。
        r = r * 10 + a.d[i];//和上一位的余数进行组合。这里的r是引用变量，对引用变量的操作就是对原全局变量的操作。
        if (r < b) c.d[i] = 0;//不够除，该位的商为0。
        else {
            c.d[i] = r / b;//商
            r = r % b;//获得新的余数。
        }
    }
    while((c.len-1>=1)&&c.d[c.len-1]==0){
        c.len--;//去除高位的0，同时至少保留一位最低位。
    }
    return c;
}

void print(bign a) {//输出bign。
    for (int i = a.len - 1;i >= 0;i--) {
        cout << a.d[i];
    }
}

int main() {
    char str1[1000];
    int b,r=0;
    cin >> str1 >> b;
    bign a = change(str1);
    print(divide(a, b,r));//商
    cout <<" "<< r;//余数
    system("pause");
    return 0;
}