企业官网建设流程全解析

如果我说，一道“两数相加”的题，值得单独写一整篇来拆解，你可能觉得我在小题大做。但“28.两数相加,进位制”这个标题里真正值钱的，其实是“进位制”三个字——它才是这道简单题背后真正的题眼。工作这些年，我见过太多工程师能把 LeetCode 第二题的代码背得滚瓜烂熟，却讲不清为什么二进制加法能用“异或 + 与移位”来实现；也见过刚入门的朋友看到“两数相加”就以为是a + b，结果在链表题和字符串加法的场景里反复吃亏。这篇文章想做的，就是把这道题彻底拆透：进位制到底怎么运作，加法在计算机内部是怎么发生的，三种主流实现各自适合什么场景，以及我实际踩过的一些边界坑。

1. 从“简单题”到“核心考点”：两数相加到底在考什么

第一次刷到“两数相加”这个标题的人，多半觉得这就是个热身题。可当你把题目放在不同的容器里，会发现它的复杂度完全不一样：给两个整数，表面上一行return a + b就结束了；可如果给两个“用字符串表示的大整数”，或者给两条“低位在前的链表”，很多人就开始手忙脚乱。原因很简单——加法这个动作本身不是考点，加法背后那套“逐位相加、逢基进一”的规则才是。

1.1 简单题表象下的四个真实考点

第一，进位规则。竖式加法里那个“满十进一”，不是只有十进制才有，二进制、十六进制、甚至六十进制都遵循同一套逻辑。只要理解了base这个参数，任何进制的加法都可以统一处理。第二，数据表示。同样的加法逻辑，放在数组、字符串、链表上写出来，代码结构完全不同，这考察的是对数据结构的熟练度。第三，边界条件。两数长度不等怎么办？最后一位还有进位怎么办？输入是负数怎么办？这些细节才是面试官真正想看的。第四，位运算等价关系。二进制的加法可以用异或和左移反复迭代实现，这背后是数字电路里全加器的逻辑，也是从“会用语言”到“理解机器”的分水岭。

1.2 谁最需要把这道题搞懂

如果你正准备算法面试，这道题几乎是必刷的第一道链表题，值得把每种写法都背熟；如果你是嵌入式、驱动、底层方向的开发者，进位制和溢出问题是日常工作的基础，搞懂它比会调库重要得多；即便是做业务开发，写到大数计算、序列号回绕、加密算法这些场景时，进位思维也会直接决定你写的代码稳不稳。所以这篇文章照顾三个层次的人：刚看完循环和数组的初学者，能照着代码一步步跑通；有一定经验但没深究过原理的开发者，能补上“为什么”；准备面试的候选人，则可以直接拿第 6 节的思路去用。

2. 进位制的底层逻辑：所有加法都是“逢基进一”

很多人学加法是从背竖式口诀开始的：“个位加个位，满十进一。”但很少有人停下来想，这个“满十进一”本质上是什么。当你在纸上算 478 + 865 的时候，你其实在重复执行同一个公式：每一位的和等于当前位的两个数字相加，再加上上一位送过来的进位；如果结果超过了基数，就只保留余数，并把商送给下一位。

2.1 竖式加法的数学本质：一个公式通吃所有进制

用公式表示就是：

• digit = (a + b + carry) % base
• next_carry = (a + b + carry) // base

其中a和b是当前位的数字，carry是上一位过来的进位，base是进位制的基数。十进制里base = 10，二进制里base = 2，十六进制里base = 16。我特别喜欢把这组公式写在白板上，因为它一句话说透了所有加法的本质——剩下的无非是把数字拆成位，然后把进位往高位传递。

拿 478 + 865 走一遍十进制竖式：

最终结果是 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) = 25，25 - 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, val=0, next=None): 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：得到的是无进位相加的结果，因为0+0=0、1+0=1、0+1=1，而1+1=0（进位被丢掉了）
• 按位与(a & b) << 1：得到的是进位产生的位置，因为只有1 & 1 = 1才表示有进位，左移一位正好把进位放到下一位上

所以 A + B 可以拆成(A ^ B) + ((A & B) << 1)。但后面这个加法本身还可能产生进位，所以要循环迭代，直到进位为 0：

public 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 位无符号整数，理论上加满后会回到 0；NTP 时间戳也会在 2036 年前后回绕一次。处理这类问题时，直接比较大小很可能出错，需要专门写“回绕安全的比较函数”，本质上是把两个数的差值放进无符号的算术语义里判断先后。这些工程里的坑，底层都源自“加法产生进位，而过高位的进位被丢弃”。当你理解了这两句话，调试这类问题会快很多。

5.4 面试题家族：字符串相加、二进制求和、十六进制加法

“两数相加”在算法题里有一个庞大的家族：字符串相加、二进制求和、十六进制加法、链表相加、数组相加。它们的核心代码几乎是同一份，区别只有三点：容器不同（字符串、链表、数组）、基数不同（10、2、16）、方向约定不同（正序还是倒序）。如果你把第 2 节那个digit = (a + b + carry) % base的公式吃透，这个家族的所有题目都能在几分钟内改编出来。我刷题时有个习惯：每换一种容器就重新手写一遍竖式模板，三遍下来，进位处理就变成本能反应了。

6. 如果把这题放进面试：怎么讲才算真的懂

最后聊聊更实际的场景：面试时遇到这类题，你该怎么表现。说实话，能把代码跑通的人很多，能把“为什么”讲清楚的人很少。而面试官恰恰最喜欢在简单题上追问“为什么”，因为简单题没有冗余信息，每一层深挖都是基础功的照妖镜。

6.1 先确认边界，再动手写代码

我看到很多候选人拿到题就开始敲，这是个坏习惯。正确的启动顺序是先确认几件事：输入的整数有没有范围限制？如果超出语言内建类型范围，是不是要用字符串或链表表示？返回结果有没有最高位的限制？输入能不能是负数，符号怎么处理？链表方向是低位在前还是高位在前？这些确认并不会浪费多少时间，却能让你的代码从一开始就对边界条件免疫。面试官听到你主动问这些，通常好感度会明显上升。

6.2 把“进位制”讲成加分项而不是背诵答案

当面试官追问“为什么二进制加法可以用位运算实现”时，千万不要只背结论“用异或和与移位”。比较好的讲法是分三层：第一层，二进制只有 0 和 1，1 + 1必然产生进位；第二层，异或恰好是不进位的加法结果，与运算恰好能标出进位产生的位置，左移是把进位搬到正确的位上；第三层，只要进位还不为 0，就得继续迭代。这样讲下来，面试官能看到你是真的理解，而不是背过答案。

6.3 我作为面试官的观察：什么表现算“真懂”

我面过不少候选人，在“两数相加”这道题上，真正让我给出高评价的往往不是最花哨的位运算写法，而是能够把字符串版本和链表版本的边界处理讲清楚的人。比如主动说出“最后进位不能丢”，或者“短的链表自动补 0”，这些细节才是区分“写过题解”和“吃透问题”的地方。反过来，只会甩位运算代码但讲不清为什么的人，往往会在下一个追问“那负数怎么办”时卡壳。这道题给我们的启示很简单：真懂一个知识点，不是你记住了它的结论，而是你能用自己的话把它的来龙去脉讲顺，还能应对变化。个人体会，这比多刷几十道题有用得多。

最后，如果你有时间，建议把三种实现都写一遍，然后自己给自己出几个刁钻用例，比如999 + 1、0 + 0、"123" + "456789"这种不对齐的输入。能把这几组用例一次跑对，你对“两数相加”和“进位制”的理解就已经超过了绝大多数人。后面再刷“二进制求和”“字符串相加”时，你大概率会回来感谢这道基础题打下的底子。