算法-大整数求和|乘法

ゝ一纸荒年。 2022-04-12 07:20 313阅读 0赞

### 文章目录 ###

*  大整数加法
 *   *  第一步
     *  第二步
     *  第三步
     *  代码
     *  BigDecimal
     *  DecimalFormat
 *  大整数乘法

# 大整数加法 #

以 426709752318 + 95481253129 为例，来看看大整数相加的详细步骤：

## 第一步 ##

**创建2个数组**，把整数倒序存储  
整数的个位存于数组0下标位置，最高位存于数组长度-1下标位置。之所以**倒序**存储，更加符合我们从左到右访问数组的习惯。  
**创建结果数组**，结果数组的最大长度是较大整数的位数+1  
![7d27536f61f34730ad79f1090ecb3132][]

## 第二步 ##

遍历两个数组，从左到右按照对应下标把元素两两相加，就像小学生计算竖式一样。

最先相加的是数组A的第1个元素8和数组B的第1个元素9，结果是7，进位1。把7填充到Result数组的对应下标，进位的1填充到下一个位置：  
![22d3971bedfd499089ba079584e6699a][]

## 第三步 ##

把Result数组的全部元素再次逆序，去掉首位的，就是最终结果  
![89ce8364b7a441a5a20e7ed37441989b][]

## 代码 ##

package test;
    
    /** * 两个大整数求和(超过long的表示范围) * * 思路：将整数转为String字符串，字符每位相加判断 */
    public class Test1 { 
    
        public static String addBigNum(String num1, String num2) { 
            //1. String转为char数组 
            //因为num1, num2 可能位数不一样，比如num1=123， num=1234, 翻转两个字符串后，个位十位相加比较方便
            char[] num1Chars = new StringBuffer(num1).reverse().toString().toCharArray();
            char[] num2Chars = new StringBuffer(num2).reverse().toString().toCharArray();
    
            int num1Length = num1Chars.length;
            int num2Length = num2Chars.length;
            //2. 在长的数组长度上加一来存新数组
            int maxLength = num1Length;
            if (num2Length > num1Length)
                maxLength = num2Length;
            int[] result = new int[maxLength + 1];
    
            //3. 对位相加
            for (int i = 0; i < result.length; i++) { 
                // 如果当前的i超过了某个数组的长度，就用0代替高位了，和另一个字符数组中的数字相加
                int aint = i < num1Length ? (num1Chars[i] - '0') : 0;
                int bint = i < num2Length ? (num2Chars[i] - '0') : 0;
                //result[i]可能已经有值了，是前面一位运算(i-1)进位过来的，所以不能直接赋值，要 +=
                result[i] += aint + bint;
    
                //如果大于10的就向前一位进位，本身进行除10取余
                if (result[i] >= 10) { 
                    result[i + 1] += result[i] / 10;
                    result[i] %= 10;
                }
            }
    
            //4. 存储最后的结果
            StringBuffer sb = new StringBuffer();
            //判断最高位是0还是1, 0无需保存
            if (result[result.length-1] == 1) 
                sb.append(1);
            for (int i = result.length-2; i >= 0; i--) { 
                sb.append(result[i]);
            }
            return sb.toString();
        }
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            String num1 = "11111111111111111111111111111";
            String num2 = "99999999999999999999999999999";
    
            String result = addBigNum(num1, num2);
            System.out.println("result: " + result);
        }
    }

--------------------

## BigDecimal ##

float和double类型的主要设计目标是为了科学计算和工程计算。他们执行二进制浮点运算，这是为了在广域数值范围上提供较为精确的快速近似计算而精心设计的。然而，它们没有提供完全精确的结果，所以不应该被用于要求精确结果的场合。  
https://www.cnblogs.com/LeoBoy/p/6056394.html

## DecimalFormat ##

https://www.cnblogs.com/hq233/p/6539107.html

# 大整数乘法 #

n位数 \* m位数 = n+m位

思路 ;  
689 \* 3 = 2067  
![在这里插入图片描述][20191201111341869.png]

[7d27536f61f34730ad79f1090ecb3132]: http://p99.pstatp.com/large/pgc-image/7d27536f61f34730ad79f1090ecb3132
[22d3971bedfd499089ba079584e6699a]: http://p99.pstatp.com/large/pgc-image/22d3971bedfd499089ba079584e6699a
[89ce8364b7a441a5a20e7ed37441989b]: http://p99.pstatp.com/large/pgc-image/89ce8364b7a441a5a20e7ed37441989b
[20191201111341869.png]: /images/20220412/83df9c16a3fe48209979d1de5dfecc53.png