高精度基础

高精度加法

分两种情况讨论

• 正序数据
• 反序数据

其实两种情况都差不多都可以利用Collections.reverse()进行翻转。

一般无论是正序还是反序，最好都将数据弄成反序，因为简单。

正序数据

给定数据是正序的，例如：需要123+456，给定的数据就是a = 123,b = 456;

简单的高精度加法的模板，只考虑a，b同号的情况，如果不同号，就调用高精度减法就好。

例如：a = 123456
b = 123456789
对齐：a = 123456 6的下标：5 1的下标：0 size = 6
b = 123456789 9的下标：8 4的下标：3 size = 9
delta = 3 = 8 - 5 = 9 - 6
所以a的个位：a.get(bs-delta),为了节约内存开销就用bs来—；
所以a的首位：a.get(bs-delta),这时候bs = delta，所以当bs < delta后就只有b的高位了，没有a的高位了

// c = a + b, a ,b同号
publid List<char> add(List<char> a, List<char> b) {
    if(a.get(0) == '-' && b.get(0) == '+' || a.get(0) == '+' && b.get(0) == '-')
        return sub(a,b);//异号用减法就好
    
    if(a.size() > b.size()) return add(b,a);// 控制 'a < b'位数小于，狭义的
    
    List<char> ans = new ArrayList<>();//答案列表
    int as = a.size(),bs = b.size();
	int delta = b.size() - a.size();
    if(a.get(0) == '-') delta++;//同号，所以判断一个即可，如果都为负数，那么a.get(0)='-'不需要，少遍历一位
    int temp = 0;//同一位上相加之后的结果
    while(bs >= 0){
        temp = int(b.get(bs));
        if(temp == 45){ // '-' 的ASCII码等于45，加法的进位不可能超过20，如果有45，那一定是负号
            ans.add('-');
            break;
        }
        if(bs < delta) temp += int(a.get(bs-delta));
        ans.add(char(temp%10));
        temp /= 10;
        bs--;
    }
    Collections.reverse(ans);
    return ans;
}

如果不考虑符号，给定的数据就是纯int类型的就简单一些了（delta不需要变了，也不用数据转型，也不用判断最前面的负号）。

// c = a + b,a ,b同号
public List<Integer> add(List<Integer> a,List<Integer> b) {
    if(a.size() > b.size()) return add(b,a);// 控制 'a < b'位数小于，狭义的
    List<char> ans = new ArrayList<>();//答案列表
    int as = a.size(),bs = b.size();
	int delta = b.size() - a.size();
    int temp = 0;//同一位上相加之后的结果
    while(bs >= 0){
        temp = b.get(bs);
        if(bs < delta) temp += a.get(bs-delta);
        ans.add(temp%10);
        temp /= 10;
        bs--;
    }
    Collections.reverse(ans);
    return ans;
}

反序数据

给定数据是反序的，例如：需要123+456，给定的数据就是a = 321,b = 654;

这种情况又要比正序简单，因为可以直接下标相同的增加。

// c = a + b,a ,b同号
public List<Integer> add(List<Integer> a,List<Integer> b) {
    if(a.size() > b.size()) return add(b,a);// 控制 'a < b'位数小于，狭义的
    List<Integer> ans = new ArrayList<>();//答案列表
    int as = a.size(),bs = b.size();//bs > as
	int index = 0,temp = 0;
    while(index < bs) {
        temp += b.get(index);//只要在循环里，就需要添加b中数据，一位b的位数高
        if(index < as) temp += a.get(index);//只要还在index比a的大小小才能加a中数据否则越界
        ans.add(temp%=10);//存入本位的数据
        temp/=10;//剩下的就是进位了
    }
    Collections.reverse(ans);//将结果正序
    return ans;
}

如果数据是正序的但是想要使用这种反序方法只需要添加两行代码：

Collections.reverse(a);
Collections.reverse(b);

复制粘贴这两行代码很快就写好了，主要是出错率比正序低。

当然如果说是有正负，翻转函数还是可以用，这个时候负号在末尾，除了转换类型，其他只需要将：if中的index < as 的判断条件改为：index < as -1就可少遍历a的最后一位了，当然while中的index < bs修改为：index < bs - 1即可

完整代码：

// c = a + b,a ,b同号
public List<char> add(List<char> a,List<char> b) {
    if(a.get(a.size() - 1) == '-' && b.get(b.size() -1) == '-') return add2(a,b);
    if(a.size() > b.size()) return add(b,a);// 控制 'a < b'位数小于，狭义的
    List<char> ans = new ArrayList<>();//答案列表
    int as = a.size(),bs = b.size();//bs > as
	int index = 0,temp = 0;
    while(index < bs) {
        temp += int(b.get(index));//只要在循环里，就需要添加b中数据，一位b的位数高
        if(index < as) temp += int(a.get(index));//只要还在index比a的大小小才能加a中数据否则越界
        ans.add(char(temp%=10));//存入本位的数据
        temp/=10;//剩下的就是进位了
    }
    Collections.reverse(ans);//将结果正序
    return ans;
}

public List<char> add(List<char> a,List<char> b) {
    if(a.size() > b.size()) return add(b,a);
    List<char> ans = new ArrayList<>();
    int as = a.size(),bs = b.size();
	int index = 0,temp = 0;
    while(index < bs - 1) {
        temp += int(b.get(index));
        if(index < as - 1) temp += int(a.get(index));
        ans.add(char(temp%=10));
        temp/=10;
    }
    ans.add('-');
    Collections.reverse(ans);
    return ans;
}

虽然代码量好像有点多，仔细一看add2()是copyadd()的。

高精度减法

和加法一样，高进度减法也是可能有正序数据和倒序数据两种情况。

对于负号：如果是异号就转换成相加就好了，如果是同号（但是都是负数）调用函数交换位置如sub(a,b)中调用sub(b,a)

正序数据

其实思路都是从低位次运算到高位次，加法要进位，减法要借位，所以从低往高运算必不可更改。

当然使用和加法一样的倒过来遍历（利用bs的下标来遍历其实也行，和加法的类似，只是改成同位之差小于0，需要借前位就行）

就不写那种了，直接反序：

Collections.reverse(a);
Collections.reverse(b);

之后看反序的情况下的代码

反序数据

// c = a - b,为了简单，规定a >= b，且都不小于零（没有负号，所以是纯数字）
public List<Integer> add(List<Integer> a,List<Integer> b) {
    List<Integer> ans = new ArrayList<>();//答案列表
    int as = a.size(),bs = b.size();
    int temp = 0,index = 0;
    while(index < as){// as >= bs
        temp = a.get(index) - temp;//借位
        if (index < bs) temp -= b.get(index);// 相当于：temp = a.get(index) - b.get(index) - temp;
        ans.add((temp + 10) % 10);//无脑先向高位借10，取模10获取个位不管需不需要借位数据都不会出错
        if (temp < 0) temp = 1;//需要借位，就让下次减的temp为1，表示借了位
        else temp = 0;//要调整位0，避免多借几次位
    }
    Collections.reverse(ans);//看情况需不需要翻转
    return ans;
}

高精度乘低精度

// c = a * b, a >= 0, b >= 0
List<Integer> mul(List<Integer> a, int b)
{
    List<Integer> ans = new ArrayList<>();

    int temp = 0;
    for (int i = 0; i < a.size() || temp != 0; i ++ )
    {
        if (i < a.size()) temp += a.get(i) * b;
        ans.add(temp % 10);
        temp /= 10;
    }
    
    // 可能还会需要去除高位的多余的0

    return ans;
}

高精度除低精度

其实一般高精度除非都会转换为 高精度 乘 被除数的逆元

• c++
• java

// a / b = c ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    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());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

Java:

// a / b = c ... r, A >= 0, b > 0
public List<Integer> div(List<Integer> a,int b,int r){
    List<Integer> ans = new ArrayList<>();
    r = 0;
    int index = a.size() - 1;
    while(index >= 0){
        r = r*10 + a.get(index);
        ans.add(r/b);
        r %= b;
    }
    Collections.reverse(ans);
    
    // 去除高位的0
    //...
    
    return ans;
}