大数字符串求和

发表于 分类于

引子

字节面试的过程中，被问到了一道处理大数求和的问题，求两个大数整数字符串的和，要求不能使用Number直接转换相加。

因为js中浮点数精度问题，处理大数求和的时候，不能直接使用浮点数配合科学计数法这种方式处理。这里我选取了按照各位数上的数字相加，单独处理进位数字的方式来实现的。

思路

我的大概思路是这样的：

  1. 将数字字符串按照从个位到高位数字的顺序处理成数组保存；
  2. 用一个结果数组保存两个运算数组各位数字相加的结果，中间需要处理满10进位的逻辑，可以使用临时变量temp存储，下一位求和的时候加上进位数字即可；
  3. 需要注意最终循环结束后，如果有进位数字，需要额外处理；
  4. 最终将结果数组reverse，拼接成字符串，再转换成结果数值，或者也可以遍历结果数组，把所有数位上的数字相加求值。

代码实现

下面是我的简单实现：

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
/**
* 整数类型的大数字符串求和， 2020.06 .16 字节跳动企业应用部门面试
*/
//  例如：strA = '123456', strB = '22345', 实现一个方法，返回两个数的和，不使用Number方法直接转换相加，整数类型的数字，且首尾不会出现0
function strNumberAdd(a, b){
    let res = 0;
    // 数字字符串拆分，将字符串按照从各位到高位的顺序存进数组
    function splitNum(str){
        const numArr = [];
        const arr = str.split('');
        for (let i = arr.length - 1; i >= 0; i--) {
            numArr.push(arr[i]);
        }
        return numArr;
    }

    // 拆分两部分数字
    const aArr = splitNum(a);
    const bArr = splitNum(b);

    const aLen = aArr.length;
    const bLen = bArr.length;
    const len = Math.max(aLen, bLen);

    const sumArr = [];
    let temp = 0;   // 用来存储前一位求和大于10向下一位进位的
    // 遍历各位，分别求和，存入sumArr
    for (let j = 0; j < len; j++) {
        if (j < Math.min(aLen, bLen)) {
            // 求和，如果有进位的，也要加上，加完temp重置为0
            sumArr[j] = Number(aArr[j]) + Number(bArr[j]) + temp;
        } else {
            let num;
            if (aLen > bLen) {
                num = Number(aArr[j]);
            } else if(aLen === bLen){
                num = Number(aArr[j]) + Number(bArr[j]);
            } else {
                num = Number(bArr[j]);
            }

            sumArr[j] =  num + temp;
        }
        // temp加完后重置为0
        temp = 0;
        // 求和超过10向下一位进1
        if (sumArr[j] >= 10) {
            sumArr[j] = sumArr[j] % 10;
            temp = 1;
        }
    }

    // 如果最高位有进位，还需要单独处理一下
    if (temp === 1) {
        sumArr.push(1);
        temp = 0;
    }
    console.log('各个数位上的数字求完和之后的数组是', sumArr);
    
    // 遍历sumArr，按照各位数上的数字相加求和
    for (let k = 0; k < sumArr.length; k++) {
        const val = sumArr[k];
        res += Number(`${val}e${k}`);
    }

    // 这里也可以直接把字符串数组反转后拼接成字符串，然后转换成数字返回
    // res = sumArr.reverse().join('') * 1;

    return res;
}

// 测试正确性
const a = strNumberAdd('126435', '2584327');
console.log('实现的函数计算出来a的值是：', a);
console.log('事实上a的值应该是126435 + 2584327 = ', 126435 + 2584327);
const b = strNumberAdd('546435', '584262');
console.log('实现的函数计算出来b的值是：', b);
console.log('事实上b的值应该是546435 + 584262 = ', 546435 + 584262);

需要注意的点

最开始我写的代码里，忘记了处理最高位有进位数字的情况，后来才发现这个问题，加了处理方案。如果数组循环完毕后temp的值不为0的话，说明最高位有进位，需要在最高位数字补加1。这个处理完毕应该就没问题了。另外一个需要注意的点应该就是两个数字长度不同时，最终处理相同数位上的数字求和的方式有所区别。