高精度加法

高精度加法

给定两个正整数（不含前导 0），计算它们的和，即大数求和。
所用方法和基本原理

该代码采用模拟竖式加法的方法来实现大数求和，基本原理如下：

• 初始化数组：
  
  
  
  • 首先找到两个字符串长度的最大值 maxLen，创建两个长度为 maxLen 的数组 addA 和 addB，用于存储两个数按位拆分后的数字。
    
  
  
• 拆分数字：
  
  
  
  • 通过从字符串的末尾开始遍历，将每个字符转换为对应的数字，并存储到相应的数组中。这样，数字的低位存储在数组的低位索引处，方便后续的加法运算。
    
  
  
• 模拟加法运算：
  
  
  
  • 创建一个长度为 maxLen + 1 的结果数组 res，用于存储加法结果。同时初始化一个进位变量 carry 为 0。
    
  • 对两个数组逐位相加，并加上进位 carry，将结果的个位存入 res 数组的对应位置，十位作为新的进位 carry。
    
  
  
• 处理最后进位：
  
  
  
  • 循环结束后，如果最后还有进位 carry != 0，则将结果数组的最高位设为 1。
    
  
  
• 构建结果字符串：
  
  
  
  • 从结果数组的最高有效位开始（跳过前导 0），将数组元素依次添加到 StringBuffer 中，最后转换为字符串返回。
    
  
  

代码及注释

1. public class BigNumberAddition {
2.     // 实现两个正整数字符串的加法
3.     public static String add(String a, String b) {
4.         // 找到两个字符串长度的最大值
5.         int maxLen = Math.max(a.length(), b.length());
6.         // 创建数组addA用于存储字符串a按位拆分后的数字
7.         int[] addA = new int[maxLen];
8.         // 创建数组addB用于存储字符串b按位拆分后的数字
9.         int[] addB = new int[maxLen];
11.         // 将字符串a按位拆分并存入addA数组
12.         for (int i = a.length() - 1, j = 0; i >= 0; i--, j++) {
13.             addA[j] = a.charAt(i) - '0';
14.         }
15.         // 将字符串b按位拆分并存入addB数组
16.         for (int i = b.length() - 1, j = 0; i >= 0; i--, j++) {
17.             addB[j] = b.charAt(i) - '0';
18.         }
20.         // 创建结果数组res，长度为maxLen + 1，以存储可能产生的进位
21.         int[] res = new int[maxLen + 1];
22.         // 创建StringBuffer用于构建结果字符串
23.         StringBuffer resStr = new StringBuffer();
25.         // 初始化进位carry为0
26.         int carry = 0;
28.         // 模拟竖式加法，逐位相加
29.         for (int i = 0; i < maxLen; i++) {
30.             // 计算当前位的和，并对10取余得到本位结果
31.             res[i] = (addA[i] + addB[i] + carry) % 10;
32.             // 计算当前位的进位
33.             carry = (addA[i] + addB[i] + carry) / 10;
34.         }
36.         // 如果最后还有进位，将结果数组的最高位设为1
37.         if (carry != 0) {
38.             res[maxLen] = 1;
39.         }
41.         // 找到结果数组中第一个非零元素的位置，跳过前导0
42.         int startIdx = maxLen;
43.         while (res[startIdx] == 0) startIdx--;
45.         // 将结果数组从有效位开始添加到StringBuffer中
46.         for (int i = startIdx; i >= 0; i--) {
47.             resStr.append(res[i]);
48.         }
50.         // 返回构建好的结果字符串
51.         return resStr.toString();
52.     }
53. }

复制代码

举例说明

假设 a = "123"，b = "4567"。

• 初始化和拆分：
  
  
  
  • maxLen = 4。
    
  • addA = [3, 2, 1, 0]（因为 a 的长度小于 maxLen，高位补 0）。
    
  • addB = [7, 5, 4, 6]。
    
  
  
• 模拟加法运算：
  
  
  
  • 第一次循环：i = 0，res[0] = (3 + 7 + 0) % 10 = 0，carry = (3 + 7 + 0) / 10 = 1。
    
  • 第二次循环：i = 1，res[1] = (2 + 5 + 1) % 10 = 8，carry = (2 + 5 + 1) / 10 = 0。
    
  • 第三次循环：i = 2，res[2] = (1 + 4 + 0) % 10 = 5，carry = (1 + 4 + 0) / 10 = 0。
    
  • 第四次循环：i = 3，res[3] = (0 + 6 + 0) % 10 = 6，carry = (0 + 6 + 0) / 10 = 0。
    
  
  
• 处理最后进位：此时 carry = 0，所以 res 数组不变，res = [0, 8, 5, 6, 0]。
  
• 构建结果字符串：
  
  
  
  • startIdx 找到第一个非零元素位置为 1。
    
  • 从 startIdx 开始添加元素到 resStr，得到 "4690"。
    
  
  

方法的优劣

• 时间复杂度：
  
  
  
  • 主要操作是遍历两个数字字符串各一次（用于拆分数字），以及一次模拟加法运算，每次操作的时间复杂度与较长数字的位数 n 成正比。所以总体时间复杂度为 (O(n))，其中 n 是两个数中较大数的位数。
    
  
  
• 空间复杂度：
  
  
  
  • 创建了三个数组（addA、addB 和 res），其大小与较长数字的位数相关，再加上一个 StringBuffer 用于构建结果字符串。总体空间复杂度为 (O(n))，n 为两个数中较大数的位数。
    
  
  

优点：
- 思路清晰，模拟竖式加法符合人类计算习惯，代码易于理解和实现。
- 能够处理任意长度的正整数加法，不受编程语言内置整数类型范围的限制。
缺点：
- 空间复杂度较高，需要额外的数组来存储数字的每一位，对于非常大的数可能会消耗较多内存。
- 由于涉及到数组操作和字符串转换，在处理大规模数据时，性能可能不如一些基于更高效数据结构或算法的大数加法实现。

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除