本文共 7895 字，大约阅读时间需要 26 分钟。

大数溢出问题

两个int类型的整数相加或者相乘的结果可能会造成大数溢出的问题，在一些笔试和面试题中有许多隐含的大数溢出问题。一般来说，大数溢出问题都需要借助字符串（字符数组类实现）

主要思路

1、将数字用字符串表示。为了方便计算和处理进位问题，将数字反转用字符串表示，将字符串表示为字符数组。原来的数字的在数组中表示是由高位到低位的，转换后的字符在数组中是由低位到高位的。例如，对于数字123而言，需要转换成的字符数组为a = {'3', '2', '1'}。

2、表示两个数字的两个字符数组的相同索引（相同位）相加

3、处理每一位的进位问题，如果在第i位发生了进位，相应的同时更新第i位和第i+1位的值

4、打印输出，由于数字转换为字符发生了翻转，因此打印输出的时候应该从后向前逆序打印，并且按照一般的阅读习惯，字符数组的前置（逆序）的0值应当不予输出。

大数加法

/**     * 数组实现大数相加（正数）     *      * key:     * 1、字符串反转，转为数组     * 2、数组对应位置相加     * 3、处理进位     * 4、数组倒序输出，忽略前置0     */    public static String addBigNum(String str1, String str2) {        if(str1 == null || str1.length() == 0 || str2 ==null || str2.length() == 0)            return null;        int length1 = str1.length();        int length2 = str2.length();        // 加法位数最多比最长的数的长度+1        int length3 = length1 > length2 ? length1 + 1 : length2 + 1;        int[] num1 = strToNum(str1);        int[] num2 = strToNum(str2);        int[] res = new int[length3];        // 计算加法        for(int i = 0; i < length3; i++) {            // i小于一个加数的长度是直接置0，参与运算            int a = i < length1 ? num1[i] : 0;            int b = i < length2 ? num2[i] : 0;            res[i] = a + b;        }        // 处理进位        for(int i = 0; i < length3; i++) {            if(res[i] > 10) {                res[i] %= 10;                res[i + 1] += res[i] / 10;            }        }        // 倒序输出，按照习惯，前置0不输出        boolean isBegin0 = true;        StringBuffer sb = new StringBuffer();        for(int i = length3 - 1; i >=0; i--) {            if(res[i] == 0 && isBegin0)                continue;            else                sb.append(res[i]);        }        return sb.toString();    }    /**     *  字符串转为数组，注意反转  StringBuffer.reverse()     * @param str     * @return     */    public static int[] strToNum(String str) {        if(str == null || str.length() == 0)            return null;        int length = str.length();        int[] arr = new int[length];        // 字符串是从高位到低位表示的，为了方便后面的运算和处理进位        // 这里需要将其翻转为从低位到高位表示，运算时也是从低位开始        String strNew = new StringBuffer(str).reverse().toString().trim();        for(int i = 0; i < length; i++) {            arr[i] = Integer.parseInt(String.valueOf(strNew.charAt(i)));        }        return arr;    }

大数减法

/**     * 减法 正数     * @param str1     * @param str2     * @return     */    public static String minus(String str1, String str2) {        if(str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0)            return null;        int length1 = str1.length();        int length2 = str2.length();        int length3 = length1 > length2 ? length1 : length2;        int[] num1 = strToNum(str1);        int[] num2 = strToNum(str2);        int[] num3 = new int[length3];        // 判断结果的正负号        String sign = "";        if(length1 < length2)            sign = "-";        else if(length1 > length2)            sign = "";        else {            for(int i = 0; i < length1; i++) {                if(num1[i] == num2[i])                    continue;                else if(num1[i] < num2[i])                    sign = "-";            }        }        // 计算减法        for(int i = 0; i < length3; i++) {            int a = i < length1 ? num1[i] : 0;            int b = i < length2 ? num2[i] : 0;            if(sign == "-")                num3[i] = b - a;            else                num3[i] = a - b;        }        // 处理借位        for(int i = 0; i < length3 - 1; i++) {            if(num3[i] < 0) {                num3[i + 1]--;                num3[i] += 10;            }        }        // 处理负号        boolean isBegin0 = true;        StringBuffer sb = new StringBuffer();        if(sign == "-")            sb.append(sign);        for(int i = length3 - 1; i >= 0; i--) {            if(num3[i] == 0 && isBegin0)                continue;            else                isBegin0 = false;            sb.append(num3[i]);        }        // 为空         if(sb.toString().equals(""))            sb.append(0);        return sb.toString();    }

大数乘法

/**     * 腾讯实习模拟     *      * 大数乘法（正数）     *      * key: 将两个字符串反转后转为数组，     * a[i] * b[j]的结果在 res[i + j]上，res的位数不超过a.length + b.length     *      * 第一步：乘法得到res     * 第二步：若果res[i]>10，则发生了进位     * 第三步：倒序输出，忽略前置0     */    public static String mutilplyBigNum(String str1, String str2) {        if(str1 == null || str2 == null)            return null;        int length1 = str1.length();        int length2 = str2.length();        int length3 = length1 + length2;    // 两个数相乘的结果的位数最大为两个数的位数和            int[] num1 = strToNum(str1);        int[] num2 = strToNum(str2);        int[] res = new int[length3];        // 计算乘法        for(int i = 0; i < length1; i++) {            for(int j = 0; j < length2; j++) {                res[i + j] += num1[i] * num2[j];            }        }        // 处理进位        for(int k = 0; k < length3; k++) {            if(res[k] > 10) {                res[k] %= 10;                res[k + 1] += res[k] / 10;            }        }        // 从尾到头输出结果，按照习惯，前置0不输出        boolean isBegin0 = true;        StringBuffer sb = new StringBuffer();        for(int k = length3 - 1; k >= 0; k--) {            if(res[k] == 0 && isBegin0)                 continue;            else                isBegin0 = false;            sb.append(res[k]);        }        return sb.toString();    }    /**     *  字符串转为数组，注意反转  StringBuffer.reverse()     * @param str     * @return     */    public static int[] strToNum(String str) {        if(str == null || str.length() == 0)            return null;        int length = str.length();        int[] arr = new int[length];        // 字符串是从高位到低位表示的，为了方便后面的运算和处理进位        // 这里需要将其翻转为从低位到高位表示，运算时也是从低位开始        String strNew = new StringBuffer(str).reverse().toString().trim();        for(int i = 0; i < length; i++) {            arr[i] = Integer.parseInt(String.valueOf(strNew.charAt(i)));        }        return arr;    }

大数加法的栈结构实现

/**     * 字符串实现大数相加     * 栈的应用     * @param str1     * @param str2     * @return     * @throws Exception     */    public String addBigNum(String str1, String str2) throws Exception{        Stack
   
     sum = new Stack
    
     (); // 结果栈        Stack
     
       num1 = strToNum(str1);   // 加数栈        Stack
      
        num2 = strToNum(str2);   // 加数栈        int sVal = 0;   // 某一位上的和        boolean isCarry = false;    // 是否进位标记        // 两个栈均不为空        while(!num1.isEmpty() && !num2.isEmpty()) {            sVal = num1.pop() + num2.pop();            // 进位加1，重置标记            if(isCarry) {                sVal++;                isCarry = false;            }            // 和压入结果栈            if (sVal > 10) {                sVal -= 10;                sum.push(sVal);                isCarry = true;            } else {                sum.push(sVal);            }        }        //  存在一个空栈        Stack
       
         tmpStack = !num1.isEmpty() ? num1 : num2;        while(!tmpStack.isEmpty()) {            // 进位加1，压入结果栈，否则全部直接压入结果栈            if (isCarry) {                int t = tmpStack.pop();                t++;                if (t > 10) {                    t -= 10;                    sum.push(t);                } else {                    sum.push(t);                    isCarry = false;                }            } else {                sum.push(tmpStack.pop());            }        }        // 最后还进位，最高位补齐1        if (isCarry)             sum.push(1);        //  从结果栈中返回        StringBuffer strBuffer = new StringBuffer();        while(!sum.isEmpty()) {            strBuffer.append(sum.pop().toString());        }        return strBuffer.toString();    }    //  字符串去除空格转为数字，压入栈中    public Stack
        
          strToNum(String str) throws Exception { Stack
         
           stack = new Stack
          
           (); if(str == null) stack = null; for(int i = 0; i < str.length(); i++) { char c = str.charAt(i); if(c == ' ') continue; else if(c >= '0' && c <= '9') stack.push(Integer.parseInt(String.valueOf(c))); else throw new Exception("包含非数字字符"); } return stack; }
          
         
        
       
      
     
    
   

转载地址：http://yuxgi.baihongyu.com/