面试笔试做不出长整数加法的是不是 coding 能力就基本当没有了？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1557 天前的主题，其中的信息可能已经有所发展或是发生改变。

最近面试，按说候选人背景也都不错吧。

我们对算法要求没那么高，业务代码为主。

因此对于各种语言的候选人，我基本都会问一道长整数加法的问题。

俩数相加，都没有符号 /没有小数点 /字符串表示返回和 /用字符串表示

这题难吗？

考察的知识点点挺广的：

字符串 /数组操作，循环控制，流程逻辑，边界条件等等。

这也基本上是编程的时候经常能遇到的问题。

但是我遇到的面试者写的千奇百怪的都有：

反复强调不能转 Int/number 还要强行转之后加起来的
说了不能转但是按位 map 一下乘以 10 的幂加起来的
- 乘方还写反的 idx ** 10
字符串 /数组非得 reverse 否则不会写循环的
- reverse 拼成 reserve/压根不会写这个函数的
循环次数拎不清的，把短的的长度加一下长的就不管了
- 好一点的知道再处理梳理一下长的数字的剩余位数
最后多的一个进位忘记了的（很多）
- 当然也不排除先相加判断是不是大于 10，再加上之前的进位的
啰啰嗦嗦写了一大堆的
- 极限是一个 go 的候选人干了七十多行还漏掉一些逻辑
- 有人写 if a 长度>b 长度 then .... 我问他 else 写啥

等等吧

所以如果你遇到这个题，如何优雅的写一个 a+b?

稍后我写一个我自己花了一小点时间写的答案，八行，没有很过分的压缩代码我的代码大概长这样：

function add(a, b) {
    let ...
    some magic {
    	cast something
        cast other
    }
    return ...
}

正经逻辑三四行写完，晚一些我贴条的方式公布我的答案。

如果要你写，你写啥？

第 1 条附言 · 2020-08-20 11:35:54 +08:00

漏了一句：
也不许用 BigInt/各种高精度计算库了。。。

坚持抖机灵会被面试官打死的。

第 2 条附言 · 2020-08-20 11:41:34 +08:00

补充我写的 Emca Script 的版本：

```
function add(a, b) {
let pos = 0, res = ''
while(a.length > pos || b.length > pos) {
let carry = res.length - pos++
res = (~~a[a.length - pos] + ~~b[b.length - pos] + carry) + res.substring(carry)
}
return res
}
```

这个进位处理也是受到某个面试者启发的，最后一次进位直接拼上去不处理了。

进位

Reverse

Cast

写

321 条回复 • 2020-08-24 11:54:05 +08:00

1 2 3 4

❮

❯

islxyqwe

2020-08-20 11:07:07 +08:00

const add = (a,b)=>(BigInt(a) + BigInt(b)).toString()

phpfpm

2020-08-20 11:07:45 +08:00

@islxyqwe 好的，下一位，被面试官打死了。

march1993

2020-08-20 11:08:45 +08:00 via iPhone

都字符串了那就按字符串按位拼呗…

luckyrayyy

2020-08-20 11:10:00 +08:00

我应该就是啰啰嗦嗦那种了。循环，字符取一位，转成 int，相加，记录进位，剩余的转回 str 加到结果上。

Jooooooooo

2020-08-20 11:11:57 +08:00

我理解写 a+b 如果是 string 就是考察最基本的代码能力

如果是 int 那考察思考全面性 (溢出怎么办?

dartabe

2020-08-20 11:13:16 +08:00

我咋看好多答案都用的 bigint

phpfpm

2020-08-20 11:16:35 +08:00

@Jooooooooo 溢出就 try-catch 一下吧，前置判断没啥意思了

@dartabe big int 用了我考啥。。。我也是反复强调不能用（当然绝大多数面试者不知道 hhh ）
主贴写的时候写漏了。

@march1993
@luckyrayyy
真的写一下估计会漏一些情况（比如最后的进位）

hytex

2020-08-20 11:18:39 +08:00

怎么感觉是字符串相加的那个题… 按位取余多的进 1，然后叠加就行了啊…

hytex

2020-08-20 11:19:27 +08:00

@hytex 字符串 append 最后倒一下…

lijialong1313

2020-08-20 11:19:54 +08:00

字符串 /数组，反转处理不好吗……

而且不能转 number 的话，难不成是两个字符串加起来之后减去对应的值？（ C 语言）

DL9412

2020-08-20 11:21:29 +08:00

这不是上周的每日打卡题么，模拟竖式就完事了

phpfpm

2020-08-20 11:22:49 +08:00

@lijialong1313 c 处理 atoi 也确实可以这么干
主要是反转吧必要性没那么大
太多人只会正着写 for，不会反着写 for，不会写 while ；
或者你要用 map-reduce 之类的方法把字符串先 reverse 我还能忍

@hytex 话是这么说，欢迎提供代码~
能贴条的时候我补充我的版本。

phpfpm

2020-08-20 11:23:51 +08:00

@DL9412 talk is~~~ show us your code~~~

hytex

2020-08-20 11:26:12 +08:00

@phpfpm 格式我不会弄这个，每日一题我做过这个。

public String addStrings(String num1, String num2) {
int a = num1.length() -1 , b = num2.length() - 1 , add = 0;
StringBuffer ans = new StringBuffer();
while(a >= 0 || b >= 0 || add != 0 ) {
int x = a>=0 ? num1.charAt(a) - '0' : 0;
int y = b>=0 ? num2.charAt(b) - '0': 0;
int res = x + y + add;
add = res / 10 ;
ans.append(res % 10);
a -- ;
b --;
}
ans.reverse();
return ans.toString();
}

lijialong1313

2020-08-20 11:26:59 +08:00

@phpfpm 主要是不反转的话，对于最左的进位就需要额外的一次移动所有字符串操作（ c 语言），我做 oj 遇到这种都是习惯反着处理。

hytex

2020-08-20 11:27:35 +08:00

@hytex 如果最后反转不能 reverse，那再稍微处理下就好了…

yhxx

2020-08-20 11:28:54 +08:00

import { BigNumber } from 'big-number';

return BigNumber(a).add(b);

（手动滑稽

phpfpm

2020-08-20 11:29:40 +08:00

@lijialong1313 你可以输出的结果是反着的，都拼好了统一反转一次（逃

@hytex goodjob，还能再短点么（虽然我知道 java 的代码量要除以 2 hhh

lijialong1313

2020-08-20 11:31:36 +08:00

@phpfpm 那这样的话，这玩意儿应该满地都是大数加法算法了吧（ C 语言）

hytex

2020-08-20 11:32:38 +08:00

@phpfpm 我看了大佬的，确实可以短一些，不过我个人水平做这个题就这样了 :D

banishee

2020-08-20 11:32:53 +08:00

@hytex 请问这个代码考虑最后一个进位了吗

hytex

2020-08-20 11:34:18 +08:00

@banishee add = 0

phpfpm

2020-08-20 11:34:46 +08:00

@lijialong1313 满地都是大数加法算法了吧——没跟上。
我们不招 c 的，不过有年头比较长嵌入式北京的我会随口问一句 C 的 VLA
形如
```
struct foo {
char bar;
int[0] baz;
};

```
这个 trick 了
（我也只会这个了 hhh

no1xsyzy

2020-08-20 11:39:36 +08:00

主要是 reverse 太方便了（

https://repl.it/repls/ExpensiveWorriedAgents

islxyqwe

2020-08-20 11:39:48 +08:00

addr 0 [] xs = reverse xs
addr n [] xs = addr 0 (show n) xs
addr n xs [] = addr n [] xs
addr n (x:xs) (y:ys) = (addr left xs ys) ++ (show digit) where
(left, digit) = divMod ((read [x] ::Integer) + (read [y] ::Integer) + n) 10
add a b = addr 0 (reverse a) (reverse b)

ytmsdy

2020-08-20 11:41:24 +08:00 via iPhone

我记得当年刚刚开始玩 acm 的时候，zoj 上的第一道题就是大数 a+b 。那时候花了快 3 天才搞完！
现在想想，从最后一位开始模拟手工计算的过程就好了！

cyrbuzz

2020-08-20 11:41:52 +08:00

```
function add(a, b) {
let max = Math.max(a.length, b.length);
a = a.padStart(max, '0');
b = b.padStart(max, '0');

let result = ''
let pad = 0

for (let i=max-1; i>-1; i--) {
let c = String(Number(a[i])+Number(b[i])+Number(pad))
c = c.padStart(2, '0')
pad = c[0]
result = `${c[1]}${result}`
}

return `${pad === '0' ? '' : pad}${result}`
}

console.log(add('1001', '200'))
```

no1xsyzy

2020-08-20 11:42:25 +08:00

@no1xsyzy #24 没编辑前后文断裂
这个是不带 reverse 的，还是 padding
但结构上用了一种诡异的方式来解决所有进位问题

phpfpm

2020-08-20 11:43:19 +08:00

@islxyqwe 膜拜 Scala 大佬（其实我也不知道叫啥，没准是 scheme 之类的

phpfpm

2020-08-20 11:45:01 +08:00

@no1xsyzy
@cyrbuzz
@ytmsdy
@islxyqwe
@no1xsyzy
@hytex
@lijialong1313
@yhxx
@dartabe
@Jooooooooo
@luckyrayyy
@march1993
@islxyqwe

我在贴条 Append 的地方写了我的解法了——很遗憾，那边好像不支持 markdown 。。

```
function add(a, b) {
let pos = 0, res = ''
while(a.length > pos || b.length > pos) {
let carry = res.length - pos++
res = (~~a[a.length - pos] + ~~b[b.length - pos] + carry) + res.substring(carry)
}
return res
}
```

希望回复能好看点。。。。

no1xsyzy

2020-08-20 11:55:27 +08:00

@phpfpm #30 APPEND 需要自己选择语法是 Default 还是 Markdown
这个用 res.length 来记录是否有进位有点奇技淫巧了

banishee

2020-08-20 11:57:06 +08:00

@phpfpm 请问这不会造成数组边界溢出吗

no1xsyzy

2020-08-20 11:58:27 +08:00

@phpfpm #30 也不能说奇技淫巧，就是在各种地方找到能放信息的地方
还是 add(x,y) = x&y<<1 + x|y 更奇技淫巧……

no1xsyzy

2020-08-20 11:59:45 +08:00

@banishee #32 唯一处理数组的地方是取 a[] 和 b[]，JS 下溢出是 undefined， ~~x 之后就是 0，这点上无法替换为 +x，因为 +x 会变成 NaN

murmur

2020-08-20 12:00:21 +08:00

有大整数类为啥要自己写，你能保证写出来的过的单元测试比库更多么

wutiantong

2020-08-20 12:02:21 +08:00

std::string add(std::string a, std::string b) {
std::string result;
auto a_i = a.rbegin(), b_i = b.rbegin();
char ten = 0;
while (true) {
char x = 0;
if (a_i != a.rend()) x = (*a_i++) - '0';
char y = 0;
if (b_i != b.rend()) y = (*b_i++) - '0';
auto c = x + y + ten;
if (c == 0) break;
else if (c > 9) {
c -= 10;
ten = 1;
} else ten = 0;
result.insert(result.begin(), c + '0');
}
return result;
}

lijialong1313

2020-08-20 12:02:52 +08:00

@phpfpm 我写了一个 c 语言的： https://paste.ubuntu.com/p/YjF5DZqXnR/

YuTengjing

2020-08-20 12:09:48 +08:00 via Android

这道题很常见啊，不会做说明没怎么准备面试算法

XiaoxiaoPu

2020-08-20 12:12:04 +08:00