13、大整数操作

缺乏、安全感 2022-05-27 10:26 117阅读 0赞

long型数据最大能对21亿以内的数字操作，可是如果两个100亿的数字相加，或者相乘呢？long型肯定不能满足需求。如果是用在天文学的计算，数字更可能达到几十位，甚至是几百位的数字。这已经不可能再使用系统定义的数据类型了，那该怎么解决？

主要思想：  
不管是大整数相加，还是大整数相乘，都可以把一个数字的各位数字存进一个数组里面，然后再对数组进行操作。就像小学时候的列竖式做加法或者乘法一样。

![Center][] ![Center 1][]

## 大数相加 ##

/******* a和b存放要相加的两个数的逆序，c将存放逆序的和，l为两个加数位数的最大值。 例如320+427：a={0,2,3},b={7,2,4},l=3,计算结果c={7,4,7}。 *******/  
    int Adding(int a[],int b[],int c[],int l)  
    {  
        int i,t;  
        for(i=0;i<l;i++)  
        {  
            t=a[i]+b[i]+c[i];  
            c[i]=t%10;  
            c[i+1]=t/10;///////////进位 
        }  
        if(c[i]!=0)  
            return i+1;  
        return i;///////////////////函数返回数组c的长度 
    }

## 大数相乘 ##

/*a和b存放要相乘的两个数的逆序，c将存放逆序的积，la、lb分别为两个乘数的位数。 例如315*66：a={5,1,3},b={6,6},la=3,lb=2,计算结果c={0,9,7,0,2}。 *******/   
    int Multiply(int a[],int b[],int c[],int la,int lb)  
    {  
        int i,j,t;  
        for(i=0;i<lb;i++)  
            for(j=0;j<la;j++)  
            {  
                t=a[j]*b[i]+c[i+j];  
                c[i+j]=t%10;  
                c[i+j+1]+=t/10;////////////进位 
            }  
        if(c[la+lb-1]!=0)  
            return la+lb;  
        return la+lb-1;////////////////////函数返回乘积的位数 
    }

参考：[https://blog.csdn.net/u012027907/article/details/12191465][https_blog.csdn.net_u012027907_article_details_12191465]

/** * @计算超大整型 */  
    public class LargeInteger {   
    
        String FirstNumStr;   //第一个数的字符串 
    
        LargeInteger(String var){  //构造方法（给第一个数字符串赋值） 
            this.FirstNumStr = var;  
        }  
        /** * 加方法 * @param SecondNumStr 被加数 * @return 相加的结果 */  
        public String add(String SecondNumStr){ //加方法 
    
            int LengthA = FirstNumStr.length(); //求出第一个数字符串长度 
            int LengthB = SecondNumStr.length();//求出第二个数字符串长度 
    
            boolean IsMinus = false; //是否带负号 
            if((FirstNumStr.charAt(0) == '-') && (SecondNumStr.charAt(0) == '-')){
       //都带负号 
                IsMinus = !IsMinus;  
            }else if(FirstNumStr.charAt(0) == '-'){ //第一个数带负号 
                FirstNumStr = FirstNumStr.substring(1);  
                String second = FirstNumStr;  
                FirstNumStr = SecondNumStr;  
                return  subtract(second);  
            }else if(SecondNumStr.charAt(0) == '-'){ //第二个数带负号 
                SecondNumStr = SecondNumStr.substring(1);  
                return subtract(SecondNumStr);  
            }  
    
            int MaxLength = LengthA >= LengthB?LengthA:LengthB; //求出最大的长度 
            MaxLength += 1; //加1是为了给可能的进位留出一位 
    
            int []FirstNum = new int[MaxLength];  //定义第一个数整型数组 
            int []SecondNum = new int[MaxLength]; //定义第二个数整型数组 
    
            int []Result = new int[MaxLength];    //定义存放结果数组 
            int MidResult = 0;  //中间结果 
            int num = 0;    //记录将字符转为整型的数 
            for(int i = LengthA-1,j = MaxLength-1; i >= 0; i--,j--){ //将第一个数字符串转为整型数组 
                switch(FirstNumStr.charAt(i)){  
                case '0':num = 0;break;  
                case '1':num = 1;break;  
                case '2':num = 2;break;  
                case '3':num = 3;break;  
                case '4':num = 4;break;  
                case '5':num = 5;break;  
                case '6':num = 6;break;  
                case '7':num = 7;break;  
                case '8':num = 8;break;  
                case '9':num = 9;break;  
                default:num = 0;break;  
                }  
                FirstNum[j] = num;  
            }  
            num = 0;  
            for(int i = LengthB-1,j = MaxLength-1; i >= 0; i--,j--){
       //将第二个数字符串转为整型数组 
                switch(SecondNumStr.charAt(i)){  
                case '0':num = 0;break;  
                case '1':num = 1;break;  
                case '2':num = 2;break;  
                case '3':num = 3;break;  
                case '4':num = 4;break;  
                case '5':num = 5;break;  
                case '6':num = 6;break;  
                case '7':num = 7;break;  
                case '8':num = 8;break;  
                case '9':num = 9;break;  
                default:num = 0;break;  
                }  
                SecondNum[j] = num;  
            }  
    
    
            for(int i = MaxLength-1; i >= 0; i--){       //从个位开始加 
                MidResult = FirstNum[i] + SecondNum[i];  //记录两数相加的中间结果 
                if(MidResult >= 10){    //进位 
                    Result[i] = MidResult % 10;  //本位的数 
                    FirstNum[i-1] = FirstNum[i-1] + 1; //进位 
                }else{  
                    Result[i] = MidResult; //没有进位直接赋值 
                }  
            }  
    
            String ResultStr = "";  
            if(IsMinus){        // 
                ResultStr = "-";  
            }  
    
            boolean flag = false;  
            for(int j = 0 ; j < MaxLength; j++){ //将整型数组转为字符串 
                if(Result[j] != 0){ //数组前面有0不赋值给字符串 
                    flag = true;  
                }  
                if(flag){  
                    ResultStr += Result[j];  
                }  
            }  
    
            return ResultStr;  
        }  
        /** * 减方法 * @param SecondNumStr * @return 相减的结果 */  
        public String subtract(String SecondNumStr){  
    
            int LengthA = FirstNumStr.length(); //求出第一个数字符串长度 
            int LengthB = SecondNumStr.length();//求出第二个数字符串长度 
    
            if((FirstNumStr.charAt(0) == '-') && (SecondNumStr.charAt(0) == '-')){  
                String second = FirstNumStr;  
                FirstNumStr = SecondNumStr.substring(1);  
                return add(second);  
    
            }else if(FirstNumStr.charAt(0) == '-'){  
                SecondNumStr = "-"+SecondNumStr;  
                return  add(SecondNumStr);  
            }else if(SecondNumStr.charAt(0) == '-'){  
                SecondNumStr = SecondNumStr.substring(1);  
                return add(SecondNumStr);  
            }  
    
            int MaxLength = LengthA >= LengthB?LengthA:LengthB; //求出最大的长度 
    
            int []FirstNum = new int[MaxLength];  //定义第一个数整型数组 
            int []SecondNum = new int[MaxLength]; //定义第二个数整型数组 
    
            int []Result = new int[MaxLength];    //定义存放结果数组 
            int MidResult = 0;  //中间结果 
            int num = 0;    //记录将字符转为整型的数 
            for(int i = LengthA-1,j = MaxLength-1; i >= 0; i--,j--){ //将第一个数字符串转为整型数组 
                switch(FirstNumStr.charAt(i)){  
                case '0':num = 0;break;  
                case '1':num = 1;break;  
                case '2':num = 2;break;  
                case '3':num = 3;break;  
                case '4':num = 4;break;  
                case '5':num = 5;break;  
                case '6':num = 6;break;  
                case '7':num = 7;break;  
                case '8':num = 8;break;  
                case '9':num = 9;break;  
                default:num = 0;break;  
                }  
                FirstNum[j] = num;  
            }  
            num = 0;  
            for(int i = LengthB-1,j = MaxLength-1; i >= 0; i--,j--){
       //将第二个数字符串转为整型数组 
                switch(SecondNumStr.charAt(i)){  
                case '0':num = 0;break;  
                case '1':num = 1;break;  
                case '2':num = 2;break;  
                case '3':num = 3;break;  
                case '4':num = 4;break;  
                case '5':num = 5;break;  
                case '6':num = 6;break;  
                case '7':num = 7;break;  
                case '8':num = 8;break;  
                case '9':num = 9;break;  
                default:num = 0;break;  
                }  
                SecondNum[j] = num;  
            }  
    
            boolean FirstNumLarger = false;  
    Breakflag:for(int i = 0; i <MaxLength; i++){  //判断第一个数是否大于第二个数 
                if(FirstNum[i] > SecondNum[i]){  
                    FirstNumLarger = true;  
                    break Breakflag;  
                }else if(FirstNum[i] == SecondNum[i]){  
                    continue;  
                }else{  
                    break Breakflag;  
                }  
            }  
    
            for(int i = MaxLength-1; i >= 0; i--){       //从个位开始加 
                if(FirstNumLarger){ //大数减小数 
                    MidResult = FirstNum[i] - SecondNum[i];  //记录两数相减的中间结果 
                }else{  
                    MidResult = SecondNum[i] - FirstNum[i];  
                }  
                if(MidResult < 0){    //借位 
                    Result[i] = 10 + MidResult ;  //本位的数 
                    if(FirstNumLarger){  
                        FirstNum[i-1] = FirstNum[i-1] - 1; //借位 
                    }else{  
                        SecondNum[i-1] = SecondNum[i-1] - 1;  
                    }  
    
                }else{  
                    Result[i] = MidResult; //没有进位直接赋值 
                }  
            }  
    
            String ResultStr = "";  
            if(!FirstNumLarger){  
                ResultStr = "-";  
            }  
            boolean flag = false;  
            for(int j = 0 ; j < MaxLength; j++){ //将整型数组转为字符串 
                if(Result[j] != 0){ //数组前面有0不赋值给字符串 
                    flag = true;  
                }  
                if(flag){  
                    ResultStr += Result[j];  
                }  
            }  
            if(ResultStr == "-"){ //相减为0时，赋值0 
                ResultStr = "0";  
            }  
            return ResultStr;  
        }  
        /** * 乘方法 * @param SecondNumStr * @return 相乘的结果 */  
        public String multiply(String SecondNumStr){  
    
            boolean IsMinus = false; //是否带负号 
            if(FirstNumStr.charAt(0) == '-'){  
                IsMinus = !IsMinus;  
                FirstNumStr = FirstNumStr.substring(1);  
            }  
            if(SecondNumStr.charAt(0) == '-'){  
                IsMinus = !IsMinus;  
                SecondNumStr = SecondNumStr.substring(1);  
            }  
            int LengthA = FirstNumStr.length(); //求出第一个数字符串长度 
            int LengthB = SecondNumStr.length();//求出第二个数字符串长度 
    
            int MaxLength = LengthA >= LengthB?LengthA:LengthB; //求出最大的长度 
            MaxLength++; //多预留一个空间 
            int ResultLength = MaxLength*2; //两个数相乘最多为两个数中最大长度的2倍 
    
            int []FirstNum = new int[MaxLength];  //定义第一个数整型数组 
            int []SecondNum = new int[MaxLength]; //定义第二个数整型数组 
            int []TempNum = new int[MaxLength];   //临时整型数组存储中间计算结果 
    
            int []Result = new int[ResultLength];    //定义存放结果数组 
            int MidResult = 0;  //中间结果 
            int num = 0;    //记录将字符转为整型的数 
    
            for(int i = LengthA-1,j = MaxLength-1; i >= 0; i--,j--){ //将第一个数字符串转为整型数组 
                switch(FirstNumStr.charAt(i)){  
                case '0':num = 0;break;  
                case '1':num = 1;break;  
                case '2':num = 2;break;  
                case '3':num = 3;break;  
                case '4':num = 4;break;  
                case '5':num = 5;break;  
                case '6':num = 6;break;  
                case '7':num = 7;break;  
                case '8':num = 8;break;  
                case '9':num = 9;break;  
                default:num = 0;break;  
                }  
                FirstNum[j] = num;  
            }  
            num = 0;  
            for(int i = LengthB-1,j = MaxLength-1; i >= 0; i--,j--){
       //将第二个数字符串转为整型数组 
                switch(SecondNumStr.charAt(i)){  
                case '0':num = 0;break;  
                case '1':num = 1;break;  
                case '2':num = 2;break;  
                case '3':num = 3;break;  
                case '4':num = 4;break;  
                case '5':num = 5;break;  
                case '6':num = 6;break;  
                case '7':num = 7;break;  
                case '8':num = 8;break;  
                case '9':num = 9;break;  
                default:num = 0;break;  
                }  
                SecondNum[j] = num;  
            }  
            int PriorNum = 0; //进位 
            int k = ResultLength - 1; //Result[k]从个位向前赋值 
    
            for(int i = MaxLength-1; i > 0; i--){      //控制第二个数的个、十、百向前推移 
                for(int j = MaxLength-1; j > 0; j--){  //使第二个数与第一个数的每一位相乘 
                    MidResult = SecondNum[i]*FirstNum[j]; //保存两个数相乘的中间结果 
                    PriorNum = MidResult / 10;  //进位数 
                // if(MidResult >= 10){ //乘的结果需要进位 
                        TempNum[j] += MidResult % 10; //本位的值 
                        if(TempNum[j] >= 10){    //如果本位的值仍需进位，则再进一位 
                            TempNum[j] = TempNum[j] % 10; //本位的最终值 
                            PriorNum++; //需要的进位数再加一 
                        }  
                        TempNum[j-1] = TempNum[j-1]+PriorNum; //进位 
                // } 
                }  
                int m = k;  
                for(int n = MaxLength-1; n >= 0; n--,m--){  //将临时存储的数组复制给最终结果数组 
                    Result[m] += TempNum[n]; //赋值 
                    if(Result[m] >= 10){  //若赋值相加需要进位，则进位 
                        Result[m-1] += Result[m]/10; //先进位 
                        Result[m] = Result[m] % 10;  //后算本位的值（这两句代码不能颠倒） 
                    }  
                    TempNum[n] = 0; //临时数组置0，以便下一个循环用 
                }  
                k--;//下一次临时数组赋值时徐翔高位移一位 
            }  
            String ResultStr = "";  
            if(IsMinus){  
                ResultStr = "-";  
            }  
    
            boolean flag = false;  
            for(int j = 0 ; j < ResultLength; j++){ //将整型数组转为字符串 
                if(Result[j] != 0){ //数组前面有0不赋值给字符串 
                    flag = true;  
                }  
                if(flag){  
                    ResultStr += Result[j];  
                }  
            }  
            if(ResultStr == ""){ //相乘为0时，显示0 
                ResultStr = "0";  
            }  
            return ResultStr;  
        }  
        /** * 除方法 * @param SecondNumStr * @return 除的结果 */  
        public String divide(String SecondNumStr){  
    
            boolean IsMinus = false; //是否带负号 
            if(FirstNumStr.charAt(0) == '-'){    //第一个数带了负号 
                IsMinus = !IsMinus;  
                FirstNumStr = FirstNumStr.substring(1);           
            }  
            if(SecondNumStr.charAt(0) == '-'){ //第二个数带了负号 
                IsMinus = !IsMinus;  
                SecondNumStr = SecondNumStr.substring(1);             
            }  
            int LengthA = FirstNumStr.length(); //求出第一个数字符串长度 
            int LengthB = SecondNumStr.length();//求出第二个数字符串长度 
    
            if(LengthA < LengthB){   //因为是整除，所以第一个数小与第二个数时，直接返回 0 
                return "0";  
            }else if(LengthA == LengthB){ //字符串相等 
                String result = subtract(SecondNumStr);   
                if(result.charAt(0) == '-'){ //第一个数小，直接返回0 
                    return "0";  
                }else if(result.charAt(0) == '0'){ //两个数相等，则返回1 
                    return "1";  
                }  
            }  
    
            int []Result =  new int[LengthA]; //存放最终结果的整型数组 
    
            String SubTemp = ""; //存放字串 
            String Temp = "";  
            String result = "";  
            String StoreFirstNumStr = FirstNumStr;//临时存放第一个数 
    
            for(int i = LengthB-1 ; i < LengthA; i++ ){  
                if(i == LengthB-1){  
                    SubTemp = FirstNumStr.substring(0,LengthB);  
                }else{  
                    FirstNumStr = SubTemp;  
                    SubTemp = subtract(Temp)+StoreFirstNumStr.substring(i,i+1);  
                }  
                for(int j = 9; j >= 0 ;j--){ //每一位的商值从9-0挨个试 
    
                    FirstNumStr = Integer.toString(j); //将整型转为字符串 
                    Temp = multiply(SecondNumStr);     //9-0中的数与被除数相乘 
    
                    FirstNumStr = SubTemp;  
                    result = subtract(Temp);//计算差值 
    
                    if(result.charAt(0) == '-'){ //若差值为负，则继续 
                        continue;  
                    }else{                      //否则，确定商，并跳出循环 
                        Result[i] = j;  
                        break;  
                    }  
                }  
            }  
             String ResultStr = "";//最终返回值的字符串 
                if(IsMinus){      //计算结果为负 
                    ResultStr = "-";  
                }  
    
            boolean flag = false;  //标记变量,标记从Result[0]-Reslult[n-1]哪一位开始不为0，才赋值给ResultStr 
            for(int j = 0 ; j < LengthA; j++){ //将整型数组转为字符串 
                if(Result[j] != 0){ //数组前面有0不赋值给字符串 
                    flag = true;  
                }  
                if(flag){  
                    ResultStr += Result[j];  
                }  
            }  
            if(ResultStr == ""){ //相乘为0时，显示0 
                ResultStr = "0";  
            }  
    
            return ResultStr;  
        }  
    
    }

测试：

public class Basic {   
    
        /** * @param args */  
        public static void main(String[] args) {  
            // TODO Auto-generated method stub 
                      //测试代码 
            LargeInteger One = new LargeInteger("1024546448494645445444464545454545456546546548897454644");  
            String Two = "1024546448494645454654";  
    
            String result1 = One.add(Two);  
            String result2 = One.subtract(Two);  
            String result3 = One.multiply(Two);  
            String result4 = One.divide(Two);  
    
            BigInteger one = new BigInteger("1024546448494645445444464545454545456546546548897454644");  
    
            BigInteger Result1 = one.add(new BigInteger("1024546448494645454654"));  
            BigInteger Result2 = one.subtract(new BigInteger("1024546448494645454654"));  
            BigInteger Result3 = one.multiply(new BigInteger("1024546448494645454654"));  
            BigInteger Result4 = one.divide(new BigInteger("1024546448494645454654"));  
    
            System.out.println(""+result1+"\n"+Result1+"\n\n");  
            System.out.println(""+result2+"\n"+Result2+"\n\n");  
            System.out.println(""+result3+"\n"+Result3+"\n\n");  
            System.out.println(""+result4+"\n"+Result4+"\n\n");  
        }  
    
    }

[Center]: https://img-blog.csdn.net/20141102234112544?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvQm9uZV9BQ0U=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220527/aebd3930c71e4f7b99727080dbdc8cdc.png
[https_blog.csdn.net_u012027907_article_details_12191465]: https://blog.csdn.net/u012027907/article/details/12191465