之前面試的時(shí)候被問(wèn)到兩個(gè)很大很大的數(shù)相乘在java中怎么把它算出來(lái)，顯然不能直接相乘，當(dāng)時(shí)我只回答出來(lái)了用BigInteger,然而不是最好的答案。大數(shù)相乘的核心思想是將數(shù)字轉(zhuǎn)化為字符串，然后逐位相乘轉(zhuǎn)化最后才得出結(jié)果。
先上一段代碼：

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);//高低位對(duì)調(diào)
        convert(s2,len2);
        int csize = len1+len2+3;
        //創(chuàng)建一個(gè)數(shù)組，處理相乘后的結(jié)果，兩個(gè)數(shù)相乘之后的結(jié)果的位數(shù)不超過(guò)兩個(gè)數(shù)的位數(shù)的和加3
        //比如兩個(gè)兩位數(shù)相乘是定小于100*100的
        int c[] = new int[csize];
        // 乘積數(shù)組填充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方法，這里高低位對(duì)調(diào)的目的是將各位放在數(shù)組的最前面，方便數(shù)組下標(biāo)進(jìn)行操作，當(dāng)然也可不用這么干，看個(gè)人。其他的代碼沒(méi)難度，最核心的思想在這里：

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; 
            }
        }

解釋下：這里是將兩個(gè)數(shù)組循環(huán)遍歷，個(gè)位數(shù)的數(shù)字相乘。為什么可以這么做呢？舉個(gè)列子：
假設(shè)有兩個(gè)數(shù)
A=863
B=974
那么乘積的個(gè)位不用說(shuō)為3x4的個(gè)位得來(lái)，即12%10=2，想高位進(jìn)1；
十位數(shù)：先看看將兩個(gè)數(shù)的十位相乘7x6=42,后面再加兩個(gè)0，即4200，這樣不可能得出一個(gè)數(shù)的乘機(jī)的十位，一個(gè)數(shù)的十位那么一定是十位和個(gè)位的乘積：6x4+7x3 = 45,加個(gè)0為450，即十位是5，百位進(jìn)4。
轉(zhuǎn)為數(shù)組、反序后：

01.png

就有C[i+j] += A[i]*B[j]；這里的下標(biāo)運(yùn)用的很巧妙。相當(dāng)于10^n，從而來(lái)表示數(shù)字的位數(shù)。
余下的代碼：

//高位處理
        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("");  

結(jié)果：84773573331783328327666000249636164373012