如果我说一道“两数相加”的题值得单独写一整篇来拆解你可能觉得我在小题大做。但“28.两数相加,进位制”这个标题里真正值钱的其实是“进位制”三个字——它才是这道简单题背后真正的题眼。工作这些年我见过太多工程师能把 LeetCode 第二题的代码背得滚瓜烂熟却讲不清为什么二进制加法能用“异或 与移位”来实现也见过刚入门的朋友看到“两数相加”就以为是a b结果在链表题和字符串加法的场景里反复吃亏。这篇文章想做的就是把这道题彻底拆透进位制到底怎么运作加法在计算机内部是怎么发生的三种主流实现各自适合什么场景以及我实际踩过的一些边界坑。1. 从“简单题”到“核心考点”两数相加到底在考什么第一次刷到“两数相加”这个标题的人多半觉得这就是个热身题。可当你把题目放在不同的容器里会发现它的复杂度完全不一样给两个整数表面上一行return a b就结束了可如果给两个“用字符串表示的大整数”或者给两条“低位在前的链表”很多人就开始手忙脚乱。原因很简单——加法这个动作本身不是考点加法背后那套“逐位相加、逢基进一”的规则才是。1.1 简单题表象下的四个真实考点第一进位规则。竖式加法里那个“满十进一”不是只有十进制才有二进制、十六进制、甚至六十进制都遵循同一套逻辑。只要理解了base这个参数任何进制的加法都可以统一处理。第二数据表示。同样的加法逻辑放在数组、字符串、链表上写出来代码结构完全不同这考察的是对数据结构的熟练度。第三边界条件。两数长度不等怎么办最后一位还有进位怎么办输入是负数怎么办这些细节才是面试官真正想看的。第四位运算等价关系。二进制的加法可以用异或和左移反复迭代实现这背后是数字电路里全加器的逻辑也是从“会用语言”到“理解机器”的分水岭。1.2 谁最需要把这道题搞懂如果你正准备算法面试这道题几乎是必刷的第一道链表题值得把每种写法都背熟如果你是嵌入式、驱动、底层方向的开发者进位制和溢出问题是日常工作的基础搞懂它比会调库重要得多即便是做业务开发写到大数计算、序列号回绕、加密算法这些场景时进位思维也会直接决定你写的代码稳不稳。所以这篇文章照顾三个层次的人刚看完循环和数组的初学者能照着代码一步步跑通有一定经验但没深究过原理的开发者能补上“为什么”准备面试的候选人则可以直接拿第 6 节的思路去用。2. 进位制的底层逻辑所有加法都是“逢基进一”很多人学加法是从背竖式口诀开始的“个位加个位满十进一。”但很少有人停下来想这个“满十进一”本质上是什么。当你在纸上算 478 865 的时候你其实在重复执行同一个公式每一位的和等于当前位的两个数字相加再加上上一位送过来的进位如果结果超过了基数就只保留余数并把商送给下一位。2.1 竖式加法的数学本质一个公式通吃所有进制用公式表示就是digit (a b carry) % basenext_carry (a b carry) // base其中a和b是当前位的数字carry是上一位过来的进位base是进位制的基数。十进制里base 10二进制里base 2十六进制里base 16。我特别喜欢把这组公式写在白板上因为它一句话说透了所有加法的本质——剩下的无非是把数字拆成位然后把进位往高位传递。拿 478 865 走一遍十进制竖式步骤计算内容本位结果进位个位8 5 1331十位7 6 1 1441百位4 8 1 1331千位进位 110最终结果是 1343。这个表看起来很简单但它是所有加法实现的核心模板不管是字符串加法、链表加法还是位运算本质都是这张表区别只在于你用什么容器来存位以及base到底是多少。2.2 换成二进制和十六进制规则只换了一个参数二进制加法和十进制唯一的区别就是“满二进一”。看一个例子计算 1011₂ 0111₂最低位1 1 2本位记 0进位 1第二位1 1 1 3本位记 1进位 1第三位0 1 1 2本位记 0进位 1最高位1 0 1 2本位记 0进位 1最前面剩下进位 1结果是 10010₂换算成十进制就是 18。你会发现整个流程和十进制一模一样只是base从 10 变成了 2。再把视野拉大到十六进制比如 0x2F 0x1A低位 F(15) A(10) 2525 - 16 9进位 1高位 2 1 1 4所以结果是 0x49也就是 73。十六进制相比二进制只是每一位能装的数更多“满十六进一”而已。2.3 计算机里其实没有“十进制加法”这句话值得反复强调。你在 C、Java、Python 里写的a b最终都会被编译器翻译成 CPU 内部的二进制运算CPU 里的加法器执行的是二进制满二进一的规则。你写十进制只是在“输入”和“输出”层面方便人阅读真正干活的加法器根本不认识9 8 17它只认识一堆高低电平。这也是为什么面试官喜欢追问“二进制加法怎么用位运算实现”——因为它直接指向了数字电路的真实运作方式。生活中也有很多非十进制的进位场景钟表是 60 进制的60 秒进 1 分、60 分进 1 小时角度也是 60 进制月份是 12 进制的。这些例子里“进位”的本质都一样累加到基数就产生一个更高位的单位。理解了这层你就掌握了进位制的通用思维。3. 三种实现两数相加的代码路径与选型思路同一个加法逻辑在不同场景下要写出不同形态的代码。这里我给出三条最常见的实现路线字符串竖式、链表加法、位运算。你需要根据输入的数据结构来决定用哪条而不是死记一种写法。3.1 字符串竖式模拟先处理“位置”和“方向”当数字大到超出语言整数范围时我们通常会收到字符串形式的输入比如12345678901234567890。这时加法必须逐位做代码如下def add_strings(a: str, b: str) - str: i, j len(a) - 1, len(b) - 1 carry 0 result [] while i 0 or j 0 or carry: x int(a[i]) if i 0 else 0 y int(b[j]) if j 0 else 0 s x y carry result.append(str(s % 10)) carry s // 10 i - 1 j - 1 return .join(reversed(result))两个关键点。第一方向必须从低位开始也就是从字符串的末尾往前遍历这和竖式从个位算起是对应的。第二循环条件要包含carry否则 99 1 这种最后还会产生进位的用例会丢结果。reversed(result)是因为我们先向列表里追加低位最后要翻转回来才是正常顺序。3.2 链表版本虚拟头节点与补零策略链表加法是 LeetCode 第 2 题的经典场景特点是链表的头节点存的是最低位比如数字 342 在链表里是2 - 4 - 3。实现时我强烈建议用虚拟头节点避免处理第一个节点时出现讨厌的空指针判断class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def add_two_numbers(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: s carry if l1: s l1.val l1 l1.next if l2: s l2.val l2 l2.next carry s // 10 cur.next ListNode(s % 10) cur cur.next return dummy.next注意while l1 or l2 or carry这个写法它天然处理了两种边界一是两链表长度不等短的节点自动视为 0二是最末位进位不会丢。dummy节点是纯辅助的最后返回dummy.next就是结果链表的真实头。时间复杂度是O(max(m, n))空间复杂度同样是O(max(m, n))因为最坏情况下多出一个最高位节点。3.3 位运算版本用“异或 与移位”模拟全加器这是最有“计算机味道”的实现也是我面试时最常追问的扩展点。两个二进制数相加可以拆成两条独立规则异或a ^ b得到的是无进位相加的结果因为000、101、011而110进位被丢掉了按位与(a b) 1得到的是进位产生的位置因为只有1 1 1才表示有进位左移一位正好把进位放到下一位上所以 A B 可以拆成(A ^ B) ((A B) 1)。但后面这个加法本身还可能产生进位所以要循环迭代直到进位为 0public int add(int a, int b) { while (b ! 0) { int carry (a b) 1; a a ^ b; b carry; } return a; }这个版本对正数、负数都能工作因为现代计算机里的整数都是补码表示加减法本质上是同一套二进制电路。唯一要小心的是 C/C 里对负数做左移操作标准上属于未定义行为稳妥做法是先转成无符号整数再移位unsigned int add(unsigned int a, unsigned int b) { while (b) { unsigned int carry (a b) 1; a a ^ b; b carry; } return a; }三条路线的选型其实很清晰常规范围内直接超大数用字符串或链表模拟竖式想体现对底层原理的理解、或者避开加号运算时用位运算。每一版代码的核心都是第 2 节那组公式换的只是容器和基数的表达方式。4. 实战里最容易翻车的四个边界问题如果你只是对着题解抄一遍代码很难体会到这题的坑有多密集。我把自己实际踩过、也看别人反复踩的四个问题列在下面每一个都有具体的翻车用例。4.1 最后一个进位99 1 的经典翻车这是我见过出现频率最高的错误。很多人的循环条件写成while i 0 or j 0然后循环结束直接返回。结果算 99 1 时个位 9 1 10本位 0进位 1十位 9 0 1 10本位 0进位 1。循环结束后进位 1 还在手里但已经没有任何位可以放它了最后只能丢掉这个最高位答案从 100 变成 00。解法只有一个把carry ! 0写进循环条件或者循环结束后单独补一位。我在代码里统一选择前者因为更符合竖式的直觉。4.2 负数输入时的取模陷阱Python 的向下取整让人防不胜防如果输入允许负数直接用第 3 节的竖式模板会出大问题。原因在于//和%在 Python 里的语义-11 // 10 -2而不是 -1因为 Python 的整除是向下取整-11 % 10 9因为余数会跟着除数取正。这导致用负数去算各位时进位会变成负数彻底打乱竖式逻辑。我的处理思路是不要直接对负数做逐位加法。一种做法是记录符号位把两个数转成绝对值后按无符号大数相加最后再根据符号调整结果另一种做法是自行实现“向零取整”的除法和取模。后者写起来麻烦我通常建议前者。记住一个经验竖式模板默认只服务非负整数遇到负数先转换不要想着在既定模板上打补丁。4.3 C/C 有符号整数溢出未定义行为比你想的还糟在 C 语言里INT_MAX 1的结果不是约定好的“变成 INT_MIN”而是未定义行为。编译器可能按补码回绕处理也可能做优化时直接假设这种情况不会发生从而产生非常诡异的结果。所以当你做普通加法前已经预估到可能溢出时有两个安全策略转成更大类型计算long long sum (long long)a b;用无符号类型无符号整数的溢出是标准定义好的回绕行为unsigned int做加法虽然可能丢高位但结果是可预测的很多业务场景里的 bug 不是算法写错而是“溢出那一刻的行为没有定义好”。这两条策略能帮你把风险控制在可预期范围内。4.4 链表不等长与位运算的符号问题链表版本另一个常见坑是短的链表走完后没有把长链表剩下的部分接上而是直接跳出循环导致结果缺位。正确做法是在循环条件里同时判断l1、l2、carry在循环体内对不存在的节点自动补 0。而位运算版本在 JavaScript 里也有坑会把数字先转成 32 位有符号整数一旦数值超过2^31运算结果就可能变负数。处理大数时要么用BigInt要么明确知道自己在 32 位语义下运算。这个细节容易被人忽略但真出 bug 时排查起来很费劲。5. 从一题到一片进位制思维在真实工程里的落点把“两数相加 进位制”放到真实工程里看你会发现它绝不是一道孤立的刷题。从 CPU 的加法器到大数运算库再到网络协议里的序列号处理到处都是这套逻辑的变体。5.1 CPU 里的进位从半加器到全加器CPU 执行加法的核心部件叫加法器。一个只考虑当前位两个输入、不考虑低位进位的加法器叫半加器它由两个逻辑门组成异或门算本位与门算进位。把进位也纳入输入就是全加器它实际上就是前文位运算代码的电路版本。当你要加两个 64 位整数时CPU 里相当于把 64 个全加器串联起来低位产生的进位像波浪一样逐级向高位传递。这个模型解释了为什么“二进制加法可以用异或和与移位表达”——因为电路就是这么搭的。5.2 大数加法的工业实现Python 的 int 内部怎么工作Python 的整数是任意精度的它内部并不是直接存一个无限长的二进制数而是把数字按 30 位一组切块存成一个数组。每次做加法时Python 会从低位块开始逐块相加每个块算完会产生一个进位传递给下一个块。这本质就是一次base 2^30的竖式加法。你可以把 Python 官方文档对“按位操作整数”的说明找出来看里面也提到了只有块内的部分才参与位运算。理解了这一点再看字符串加法、链表加法的实现会发现所有大数系统跑的都是同一套进位逻辑。5.3 回绕与溢出从 TCP 序列号到计数器设计计算机系统里有大量无符号计数器它们加到最大值后会回绕到 0这就是“溢出回绕”。最经典的例子是 TCP 的序列号它是 32 位无符号整数理论上加满后会回到 0NTP 时间戳也会在 2036 年前后回绕一次。处理这类问题时直接比较大小很可能出错需要专门写“回绕安全的比较函数”本质上是把两个数的差值放进无符号的算术语义里判断先后。这些工程里的坑底层都源自“加法产生进位而过高位的进位被丢弃”。当你理解了这两句话调试这类问题会快很多。5.4 面试题家族字符串相加、二进制求和、十六进制加法“两数相加”在算法题里有一个庞大的家族字符串相加、二进制求和、十六进制加法、链表相加、数组相加。它们的核心代码几乎是同一份区别只有三点容器不同字符串、链表、数组、基数不同10、2、16、方向约定不同正序还是倒序。如果你把第 2 节那个digit (a b carry) % base的公式吃透这个家族的所有题目都能在几分钟内改编出来。我刷题时有个习惯每换一种容器就重新手写一遍竖式模板三遍下来进位处理就变成本能反应了。6. 如果把这题放进面试怎么讲才算真的懂最后聊聊更实际的场景面试时遇到这类题你该怎么表现。说实话能把代码跑通的人很多能把“为什么”讲清楚的人很少。而面试官恰恰最喜欢在简单题上追问“为什么”因为简单题没有冗余信息每一层深挖都是基础功的照妖镜。6.1 先确认边界再动手写代码我看到很多候选人拿到题就开始敲这是个坏习惯。正确的启动顺序是先确认几件事输入的整数有没有范围限制如果超出语言内建类型范围是不是要用字符串或链表表示返回结果有没有最高位的限制输入能不能是负数符号怎么处理链表方向是低位在前还是高位在前这些确认并不会浪费多少时间却能让你的代码从一开始就对边界条件免疫。面试官听到你主动问这些通常好感度会明显上升。6.2 把“进位制”讲成加分项而不是背诵答案当面试官追问“为什么二进制加法可以用位运算实现”时千万不要只背结论“用异或和与移位”。比较好的讲法是分三层第一层二进制只有 0 和 11 1必然产生进位第二层异或恰好是不进位的加法结果与运算恰好能标出进位产生的位置左移是把进位搬到正确的位上第三层只要进位还不为 0就得继续迭代。这样讲下来面试官能看到你是真的理解而不是背过答案。6.3 我作为面试官的观察什么表现算“真懂”我面过不少候选人在“两数相加”这道题上真正让我给出高评价的往往不是最花哨的位运算写法而是能够把字符串版本和链表版本的边界处理讲清楚的人。比如主动说出“最后进位不能丢”或者“短的链表自动补 0”这些细节才是区分“写过题解”和“吃透问题”的地方。反过来只会甩位运算代码但讲不清为什么的人往往会在下一个追问“那负数怎么办”时卡壳。这道题给我们的启示很简单真懂一个知识点不是你记住了它的结论而是你能用自己的话把它的来龙去脉讲顺还能应对变化。个人体会这比多刷几十道题有用得多。最后如果你有时间建议把三种实现都写一遍然后自己给自己出几个刁钻用例比如999 1、0 0、123 456789这种不对齐的输入。能把这几组用例一次跑对你对“两数相加”和“进位制”的理解就已经超过了绝大多数人。后面再刷“二进制求和”“字符串相加”时你大概率会回来感谢这道基础题打下的底子。