写在前面

周五腾讯模拟笔试（2016.03.25），出了个题，关于大数相乘的问题。这样的题以前也有，网上也有很多实现代码（笔者写完算法后搜索了一下，确有很多，并未细看，并不知道是否有和笔者相同的解决方案）。笔者将算法用java实现，写出来给各位参考一下，不足之处，请各位多多指正。

问题

问题描述

输入两个整数，要求输出两个整数的乘积，该乘积可能超出整型范围。

问题分析

首先，依题意，肯定是不能用两个整数直接相乘，得到结果。故要考虑分解问题，即如何将两个大数的乘法，换成一系列小一点的数的运算。由此，笔者根据小学竖式，想到了不进位乘法，觉得可以用不进位乘法来解决大数相乘的问题。至此，算法已经确定，接下来就是如何处理两个整数和其乘积了。笔者自以为可以用ArrayList来存储。

算法描述

基本思想：采用不进位乘法计算，然后再将结果进行转换
如计算12345*123 （num1*num2）

1  2  3  4  5       list1    5 4 3 2 1
         *        1  2  3       list2    3 2 1
          ————————————————
            3  6  9 12 15
         2  4  6  8 10
      1  2  3  4  5
      ——————————————————————
      1  4  9 16 22 22 15   listres 15 22 22 16  9  4  1
 转换为：
      1  5  1  8  5  3  5    
 注意：list中，数据存储的顺序是从最低位开始，依次到最高位

算法实现

具体实现代码如下：

import java.util.ArrayList;
/** * @Title: 大数相乘list实现（本例中指针对大整数） * @Description: 给定两个大数，其相乘结果可能超出整数的范围， * 溢出。通过本算法实现大数相乘，并打印结果。 * @author: JerryZhou * @date:2016年3月27日 * @version:V1.0 */
public class bigNumMultiple {
    /* * 基本思想：采用不进位乘法计算，然后再将结果进行转换 * 如计算12345*123 （num1*num2） * 1 2 3 4 5 list1 5 4 3 2 1 * * 1 2 3 list2 3 2 1 * ———————————————— * 3 6 9 12 15 * 2 4 6 8 10 * 1 2 3 4 5 * —————————————————————— * 1 4 9 16 22 22 15 listres 15 22 22 16 9 4 1 * 转换为： * 1 5 1 8 5 3 5 * 注意：list中，数据存储的顺序是从最低位开始，依次到最高位 */
    public static void main(String[] args) {
        int a =12345;
        int b = 123;
        Multiple(a,b);
    }
    /** * @Title Multiple * @Description 大数相乘，打印结果 * @param num1 * @param num2 */
    public static void Multiple(int num1,int num2){
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        ArrayList<Integer> listres = new ArrayList<Integer>();
        if(num1<num2){   //将较大的数放在前面
            int tmp = 0;
            tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        while(num1/10!=0){ //将num1，从个位开始，依次存入list1中
            list1.add(num1 % 10);
            num1 = num1 / 10;
        }
        list1.add(num1);
        while(num2/10!=0){ //将num2，从个位开始，依次存入list2中
            list2.add(num2 % 10);
            num2 = num2 / 10;
        }
        list2.add(num2);
        int firstlen = list1.size(); //num1的位数
        int secondlen = list2.size(); //num2的位数
        for(int i = 0;i < secondlen; i++){ //不进位乘法运算
            for(int j = 0;j< firstlen;j++){
                if(listres.size()<j+i+1){
                    listres.add(0);
                    listres.set(j+i,listres.get(j+i)+list1.get(j)*list2.get(i));
                }else{
                    listres.set(j+i,listres.get(j+i)+list1.get(j)*list2.get(i));
                }   
            }
        }
        int len = listres.size(); 
        for(int i =0;i<len;i++){ //结果转换
            if(listres.get(i)>9){
                int temp = listres.get(i)/10;
                listres.set(i,listres.get(i)%10);
                if(listres.size()<i+2){ //考虑到最高为的进位问题，可能导致list需要开辟新空间
                    listres.add(0);
                }
                listres.set(i+1,listres.get(i+1)+temp);
            }else{
                continue;
            }
        }
        while(len>0){  //打印大数相乘的最后结果
            System.out.print(listres.get(len-1));
            len-=1;
        }
    }
}

以上程序经笔者测试，确实是成功解决了大数相乘的问题，但笔者认为还有很大的优化空间。希望各位读者多多指正。