大数相乘——java版

之前面试的时候被问到两个很大很大的数相乘在java中怎么把它算出来，显然不能直接相乘，当时我只回答出来了用BigInteger,然而不是最好的答案。大数相乘的核心思想是将数字转化为字符串，然后逐位相乘转化最后才得出结果。
先上一段代码：

public static void main(String[] args) {
        String str1 = "23451515412151511212";
        String str2 = "3614844151515151515151";
        
        int len1 = str1.length();
        int len2 = str2.length();
        
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        convert(s1,len1);//高低位对调
        convert(s2,len2);
        int csize = len1+len2+3;
        //创建一个数组，处理相乘后的结果，两个数相乘之后的结果的位数不超过两个数的位数的和加3
        //比如两个两位数相乘是定小于100*100的
        int c[] = new int[csize];
        // 乘积数组填充0  
        for (int ii = 0; ii < csize; ii++) {  
            c[ii] = 0;  
        } 
        for(int i=0;i<len1;i++) {
            for(int j=0;j<len2;j++) {
                int a = Integer.parseInt(String.valueOf(s1[i]));
                int b = Integer.parseInt(String.valueOf(s2[j]));
                c[i+j] += a* b; 
            }
        }

public static void convert(char[] s,int len) {
        
        for(int i=0;i<len/2;i++) {
            s[i] += s[len-i-1];
            s[len-i-1] = (char) (s[i]-s[len-i-1]);
            s[i] = (char) (s[i] - s[len-i-1]);
        }
    }

先看convert方法，这里高低位对调的目的是将各位放在数组的最前面，方便数组下标进行操作，当然也可不用这么干，看个人。其他的代码没难度，最核心的思想在这里：

for(int i=0;i<len1;i++) {
            for(int j=0;j<len2;j++) {
                int a = Integer.parseInt(String.valueOf(s1[i]));
                int b = Integer.parseInt(String.valueOf(s2[j]));
                c[i+j] += a* b; 
            }
        }

解释下：这里是将两个数组循环遍历，个位数的数字相乘。为什么可以这么做呢？举个列子：
假设有两个数
A=863
B=974
那么乘积的个位不用说为3x4的个位得来，即12%10=2，想高位进1；
十位数：先看看将两个数的十位相乘7x6=42,后面再加两个0，即4200，这样不可能得出一个数的乘机的十位，一个数的十位那么一定是十位和个位的乘积：6x4+7x3 = 45,加个0为450，即十位是5，百位进4。
转为数组、反序后：

01.png

就有C[i+j] += A[i]*B[j]；这里的下标运用的很巧妙。相当于10^n，从而来表示数字的位数。
余下的代码：

//高位处理
        int m = 0;
        for(;m<csize;m++) {
            int carry = c[m]/10;
            c[m] = (char) (c[m]%10);
            if(carry>0) {
                c[m+1] += (char) carry;
            }
        }
        
         // 找到最高位  
        for (m = csize - 1; m >= 0;m--) {  
            if (c[m] > 0)  
                break;  
        } 
        
        // 由最高位开始打印乘积  
        for (int n = 0; n <= m; n++) {  
            System.out.print(c[m - n]);  
        }  
        System.out.println("");  

结果：84773573331783328327666000249636164373012