大数如何加减？- 算法小练

前言

在平时 coding 的时候，如果用到一些数学计算，那么加法和减法必然是我们代码中的常客，但是当一些数字超过 JS 可精确表示的范围时，我们又该如何计算呢？今天给大家带来的就是一个粗浅的算法思路及其实现。如果对我的内容有问题或者疑问，欢迎评论区多多交流。

理清思路

前置条件

  1. 首先要理解，因为 JS 无法准确表示超出 IEEE 754 标准规范的整数。当数字超过 -2^53到2^53 的范围时，无法精确计算 ，因此大数加法和大数减法是利用 string 类型去实现的。
  2. 因为 string 类型无法直接比较大小，需要有个方法比较大小，我这里抽象除了一个 compare 方法。
  3. compare 方法的流程如下，最终返回三种值，-1 表示小于，1 表示大于，0 表示相等。
    • 首先比符号，负数肯定比正数小。
    • 其次比位数，当符号相同那么从最高位数比，最高位大的负数更小，最高位大的正数更大。
    • 每位数字从最高位比到最低位，如果中间没有比出大小说明两数相等。
  4. 加法有进位，减法有借位，这里用 carry 表示，在计算完最后需要做相应的处理，千万不能忘记
  5. 减法根据借位情况，可能会出现前缀 0，这时前缀 0 需要去除，但要注意不要把单独的结果 0 去除 。
  6. 当涉及正负符号的时候，可以先把正负符号的结果通过比较的方式计算出来，然后最后加上符号即可

流程图

为了更加直观的理解这个流程我画了两个简单的流程图

大数加
image.png

大数减（带正负号）

image.png
image.png

开始实现

1. compare 方法

compare 方法主要处理了四种比较的情况，负数和正数，正数和负数，负数和负数，正数和正数，前两种情况分别返回 -1 和 1 即可，后两种情况需要比对数位，前面的思路阐述中已经解释过，这里为了篇幅就把详细代码放在最后总结的代码中，这里不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
function compare(a1, a2) {
  if (a1.startsWith("-") && !a2.startsWith("-")) {
    return -1;
  } else if (!a1.startsWith("-") && a2.startsWith("-")) {
    return 1;
  } else if (a1.startsWith("-") && a2.startsWith("-")) {
    return compareNegative(a1, a2);
  } else if (!a1.startsWith("-") && !a2.startsWith("-")) {
    return comparePositive(a1, a2);
  }
  return 0;
}

2. 大数加

首先获取四个变量

1
2
3
4
let carry = 0; // 进位
let i = a1.length - 1; // a1 的当前位指针，从最后一位开始
let j = a2.length - 1; // a2 的当前位指针，从最后一位开始
let arr = []; // 结果数据，最后会进行处理和组合

然后通过循环，将数字加起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while (a1[i] || a2[j] || carry) {
  // 注意这里 a1 和 a2 位数可能不同，因此当有任意一个值，都要继续
  let x = 0; // 默认 0
  if (a1[i]) {
    x = Number(a1[i]);
  }
  let y = 0; // 默认 0
  if (a2[j]) {
    y = Number(a2[j]);
  }
  let res = (x + y + carry) % 10; // x + y 同时加上进位，对 10 求余，得到当前的加法结果
  arr.unshift(res); // 放到数组最前一位
  carry = Math.floor((x + y + carry) / 10); // 计算是否进位
  i--; // 往前移动指针，准备下一位计算
  j--;
}

最后进行进位处理，返回字符串

1
2
3
4
5
if (carry) {
  // 如果最后还有进位，需要把进位加上
  arr.unshift(carry);
}
return arr.join("");

3. 大数减（带正负号）

带正负号首先要确定结果的符号，以下三种情况都是负数，因此 s需要处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let s = ""; // 符号
if (
  // 小减大，负数
  (a1[0] === "-" && a2[0] === "-") ||
  // 小减大，正数
  (a1[0] !== "-" && a2[0] !== "-")
) {
  if (compare(a1, a2) < 0) {
    // -123 - -12
    s = "-";
  }
} else if (a1[0] === "-" && a2[0] !== "-") {
  // 负数减正数
  // -123 - 789
  s = "-";
}

接着开始处理数字，前两种情况，分别是正数减负数，和负数减负数，抽象为去掉符号之后直接加上，即可得到数值结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let res = "";
if (
  // 正 - 负
  (a1[0] !== "-" && a2[0] === "-") ||
  // 负 - 正
  (a1[0] === "-" && a2[0] !== "-")
) {
  if (a1[0].startsWith("-")) {
    a1 = a1.slice(1);
  }
  if (a2[0].startsWith("-")) {
    a2 = a2.slice(1);
  }
  res = bigAdd(a1, a2);
} else if(
  ...
) {
  ...
}

后两种情况，正数减正数，负数减负数，去掉符号后通过比较让大数减小数，即可得到数值结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
if (
  ...
) {
	...
} else if (
  // 正 - 正
  (a1[0] !== "-" && a2[0] !== "-") ||
  // 负 - 负
  (a1[0] === "-" && a2[0] === "-")
) {
  if (a1[0].startsWith("-")) {
    a1 = a1.slice(1);
  }
  if (a2[0].startsWith("-")) {
    a2 = a2.slice(1);
  }
  if (compare(a1, a2) > 0) {
    res = minus(a1, a2);
  } else {
    let tmp = a1
    a1 = a2;
    a2 = tmp;
    res = minus(a1, a2);
  }
}

最后通过符号加数值的方式返回结果

1
return `${s}${res}`;

细节和注意

  1. 底层的 minuse 和 add 实现其实都相对简单，注意进位和借位即可

  2. 上层的 bigAdd 和 bigMinus 需要比较大小，同符号和异符号可能会产生不同的效果

  3. 注意加法位数不同导致的问题，当其中任意一者还有内容的时候就必须继续加下去，且这个过程不能直接借助 carry 处理

  4. 减法需要处理前缀 0，同时要保证不能处理掉结果 0

总结

通过字符串的操作就能简单实现对大数的加法和减法，下篇文章计划实现对于大数的乘法和除法，最后的计算结果会更加复杂。

最后附上完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
function bigAdd(a1, a2) {
  let carry = 0;
  let i = a1.length - 1;
  let j = a2.length - 1;
  let arr = [];
  while (a1[i] || a2[j]) {
    let x = 0;
    if (a1[i]) {
      x = Number(a1[i]);
    }
    let y = 0;
    if (a2[j]) {
      y = Number(a2[j]);
    }
    let res = (x + y + carry) % 10;
    arr.unshift(res);
    carry = Math.floor((x + y + carry) / 10);
    i--;
    j--;
  }
  if (carry) {
    arr.unshift(carry);
  }
  return arr.join("");
}

// 123 23
// 23 - 123 = - (123 - 23) =
//

function bigMin(a1, a2) {
  // 负数减负数（去掉符号，大减小）（如果 a2 > a1，正号；如果 a1 > a2，负号）
  // 正数减负数（去掉符号，加起来）（正号）
  // 正数减正数（去掉符号，大减小）（如果 a2 > a1，负号；如果 a1 > a2，正号）
  // 负数减正数（去掉符号，加起来）（负号）
  let s = "";

  if (
    // 小减大，负数
    (a1[0] === "-" && a2[0] === "-") ||
    // 小减大，负数
    (a1[0] !== "-" && a2[0] !== "-")
  ) {
    if (compare(a1, a2) < 0) {
      // -123 - -12
      s = "-";
    }
  } else if (a1[0] === "-" && a2[0] !== "-") {
    // -123 - 789
    s = "-";
  }

  let res = "";
  if (
    // 正 - 负
    (a1[0] !== "-" && a2[0] === "-") ||
    // 负 - 正
    (a1[0] === "-" && a2[0] !== "-")
  ) {
    if (a1[0].startsWith("-")) {
      a1 = a1.slice(1);
    }
    if (a2[0].startsWith("-")) {
      a2 = a2.slice(1);
    }
    res = bigAdd(a1, a2);
  } else if (
    // 正 - 正
    (a1[0] !== "-" && a2[0] !== "-") ||
    // 负 - 负
    (a1[0] === "-" && a2[0] === "-")
  ) {
    if (a1[0].startsWith("-")) {
      a1 = a1.slice(1);
    }
    if (a2[0].startsWith("-")) {
      a2 = a2.slice(1);
    }
    if (compare(a1, a2) > 0) {
      res = minus(a1, a2);
    } else {
      let tmp = a1;
      a1 = a2;
      a2 = tmp;
      res = minus(a1, a2);
    }
  }

  return `${s}${res}`;
}

function minus(a1, a2) {
  let carry = 0;
  let i = a1.length - 1;
  let j = a2.length - 1;
  let arr = [];
  while (a1[i]) {
    let x = Number(a1[i]);
    let y = 0;
    if (a2[j]) {
      y = Number(a2[j]);
    }
    let temp;
    if (x - y + carry < 0) {
      temp = x + 10;
    } else {
      temp = x;
    }
    let res = temp - y + carry;
    if (x - y + carry < 0) {
      carry = -1;
    } else {
      carry = 0;
    }
    arr.unshift(res);
    i--;
    j--;
  }
  while (arr[0] === 0 && arr.length > 1) {
    arr.shift();
  }
  return arr.join("");
}

/**
 *
 * @param {string} a1
 * @param {string} a2
 * @returns {number}
 */
// 正负数，比较大数大小
function compare(a1, a2) {
  if (a1.startsWith("-") && !a2.startsWith("-")) {
    return -1;
  } else if (!a1.startsWith("-") && a2.startsWith("-")) {
    return 1;
  } else if (a1.startsWith("-") && a2.startsWith("-")) {
    return compareNegative(a1, a2);
  } else if (!a1.startsWith("-") && !a2.startsWith("-")) {
    return comparePositive(a1, a2);
  }
  return 0;
}

function compareNegative(a1, a2) {
  // 谁位数多谁小
  if (a1.length > a2.length) {
    return -1;
  } else if (a1.length < a2.length) {
    return 1;
  } else {
    let i = 0;
    while (a1[i] && a2[i]) {
      /// 123 789
      if (a1[i] > a2[i]) {
        return -1;
      } else if (a1[i] < a2[i]) {
        return 1;
      } else {
        i++;
      }
    }
  }
  return 0;
}

function comparePositive(a1, a2) {
  if (a1.length > a2.length) {
    return 1;
  } else if (a1.length < a2.length) {
    return -1;
  } else {
    let i = 0;
    while (a1[i] && a2[i]) {
      if (a1[i] > a2[i]) {
        return 1;
      } else if (a1[i] < a2[i]) {
        return -1;
      } else {
        i++;
      }
    }
  }
  return 0;
}
大数如何加减？- 算法小练
https://blog.zer0fire.me/2023/11/22/大数如何加减？-算法小练/
Author
AlexWang
Posted on
November 22, 2023
Licensed under