高精度大数运算

1. 高精度定义

在C/C++中，各种数据类型都是有一定取值范围的，但在实际生产/计算中，有些位数很多的大数是C语言中的数据类型无法表示的。比如len(a) = 1e10，则在类C语言中，a无法直接进行计算，我们需要用数组或者vector来进行模拟计算。相关数据类型取值范围如下；

类型名             			 		  	  取值范围
signed char        			   		        -128~127
unsigned char					  	  	   	  0~255
short int        			  	       	  -32768~32767
int            		 				-2147483648~2147483647
unsigned int							 	 0~4294967295
long         	          		  	 -2147483648~2141483647
unsigned long 								 0~4294967295
long long 	 		     	-9223372036854775808~9223372036854775807
unsigned long long 						      0~18446744073709551615

此时我们需要高精度计算方法。

2. 高精度加法（两个高精度整数相加）

2.1 算法思想

2.2 算法模板

计算模板：

// C = A + B, A >= 0, B >= 0
vector add(vector &A, vector &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

大整数存储模板（大端存储会极大简化计算过程,需考虑进位）：

int main()
{
    std::string s1,s2;
    cin >> s1 >> s2;
    vector a,b;
    for (int i = s1.size()-1 ; i >= 0 ; i--)     a.push_back( s1[i] - '0');//a,b采用大端存储的方式，数字低位存放在向量的低位，方便对高位数据进行操作，进位/去除前导0
    for (int i = s2.size()-1 ; i >= 0 ; i--)     b.push_back( s2[i] - '0');

    auto c = add(a,b);//auto表示自动选择函数的返回类型给到c,c采用为大段存储
    
    for (int i = c.size() - 1 ; i >= 0 ; i--)   cout << c[i];
    
    system("pause");
    return 0;

}

3. 高精度减法（两个高精度整数相减）

3.1 算法思想

同竖式减法

3.2 算法模板

存储方式同高精度加法

计算模板（假设AB均为整数且A>=B的前提下）：

采用大端存储，去除前导0（因为采用大端存储，所以高位的0要除去，比如减法所得结果为009，应输出9，则需要去掉前面高位的两个0）

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector sub(vector &A, vector &B)
{
    vector C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;					//此时t == 被减数减去上一位的借位
        if (i < B.size()) t -= B[i];	 //此时t == t-减数
        C.push_back( (t + 10) % 10 );
        //当t = 被减数 - 借位 - 减数 > 0 时，(t + 10) % 10表示差
        //当t = 被减数 - 借位 - 减数 < 0 时，(t + 10) % 10表示借位后的差
        if (t < 0) t = 1;	 //标记借位
        else t = 0;			//标记未借位
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
    return C;
}

比较模板（比较两个高精度整数大小）

bool cmp(vector &A, vector &B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    //返回 “A比B长度（位数）大” 这个布尔表达式的结果。即当A长度大于B时，布尔表达式成立，返回true；当A长度小于B时，布尔表达式不成立，返回false。

    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];
    //返回 “A的元素值比B大” 这个布尔表达式的结果。当A的元素值大于B的元素值时，布尔表达式成立，返回true；当A的元素值小于B的元素值时，布尔表达式不成立，返回false。

    return true;//A与B相等
}

4. 高精度乘法（一个高精度整数乘与一个低精度整数）

4.1 算法思想

不同于一般竖式乘法

4.2 算法模板

存储模板与高精度加法类似

乘法模版与加法模板类似

// C = A * b, A >= 0, b >= 0
vector mul(vector &A, int b)
{
    vector C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )//注意退出条件不仅仅是i < A.size()，还要考虑乘法进位的情况，即退出条件为i >= A.size() && t == 0
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0，小精度整数为0的情况

    return C;
}

5. 高精度除法（高精度除以低精度）

5.1 算法思想

5.2 算法模板

// A / b = C ... r, A >= 0, b > 0
vector div(vector &A, int b, int &r)
{
    vector C;
    r = 0;//r表示余数
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);//上商
        r %= b;
    }
    reverse(C.begin(), C.end());//将大端存储改为小端存储，方便去除前导0以及输出
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
    return C;
}