欢迎阅读 欢迎来到「两整数之和」题解之旅本文将带你从不用加号算出两数之和这一看似矛盾的场景出发深入理解位运算模拟加法的巧妙运用并掌握如何用异或求无进位和、与运算求进位来在循环中完成加法。在开始之前建议你先了解题目背景这是 LeetCode 371 题给定两个整数a和b要求不使用、-运算符计算它们的和。本质上加法的二进制过程可拆为**无进位和与进位两部分**反复迭代直到进位为 0问题转化为位运算的递归/循环模拟。明确学习目标掌握异或求无进位和、(a b) 1求进位的核心公式理解为什么循环必然终止并熟练处理负数补码参与运算等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如a 1, b 2输出3a 2, b 3输出5。本文将从问题转化、无进位和、进位传递、终止条件到代码实现层层递进。即使你对位运算还不熟悉我们也会从先加不算进位的再把进位补上去这一直觉出发让你轻松抓住核心思想——异或得和、与移得进位进位清零即成。现在让我们一起用位运算模拟加法吧 ➕愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》钱塘江上潮信来今日方知我是我✨当前学习内容《位运算》一.题目371. 两整数之和 - 力扣LeetCode 二、算法分析一、问题分析前置分析题目要求计算a b不允许使用、-运算符。关键约束a、b可能为负数结果可能溢出 int 范围题目保证在 int 内。核心思路十进制加法可拆为本位与进位——二进制同理a ^ b 无进位和(a b) 1 进位。把进位当作新的加数反复相加直到进位为 0得到最终结果全程只用到位运算。 例子为什么异或与与运算能拆分加法a 1 (01), b 2 (10)a ^ b 11 3每一位都不同无进位直接是一位的和a b 00没有同为 1 的位故无进位→ 结果 3。再看a 1 (01), b 3 (11)a ^ b 10 2不吃进位的本位和、a b 01左移一位10 2就是该进上去的进位——加法的本质被拆成和与进位两部分。二、算法策略位运算模拟加法 · 异或 与移核心步骤循环条件只要b ! 0还有进位就继续。计算无进位和sum1 a ^ b异或同位不同为 1不处理进位。计算进位sum2 (a b) 1同为 1 的位产生进位左移一位送到高位。更新迭代a sum1新的和、b sum2新的进位下轮继续相加。返回进位为 0 时循环结束a即最终结果。 示例a 2 (010), b 3 (011)期待5轮次absum1 a^bsum2 (ab)1说明初始010 (2)011 (3)——准备相加第1轮010011001 (1)(010)1 100 (4)本位和 1进位 4第2轮001 (1)100 (4)101 (5)(000)1 000 (0)本位和 5无进位结束101 (5)0——b0 退出返回5✅第 1 轮把23拆成本位和 1 与进位 4第 2 轮把 1 和 4 相加得 5 且不再产生进位——两轮就把加法完成与2 3 5一致。三、正确性说明简单版本拆分完备二进制加法中每一位的本位结果由两数该位是否不同决定^是否向高位进位由两数该位是否同为 1决定后左移。两者合起来恰好完整描述加法不重不漏。迭代等价把进位b当作新的加数与sum1相加正是先算本位、再补进位的加法过程每轮结果与真实加法逐步逼近。必然终止每轮b (a b) 1进位至少左移一位而 int 只有 32 位进位最终会移出高位变为 0循环最多执行 32 次即结束不会死循环。负数天然支持C 中整数用补码存储位运算直接作用于补码负数参与^、、的结果与真实加法的补码完全一致无需特判。 例子进位为什么必然消失a 1, b 1第 1 轮sum1 0、sum2 (11)1 2进位到第 1 位第 2 轮a0, b2sum1 2、sum2 (02)1 0无进位→ 返回 2 ✅。进位每次至少左移一位在 32 位整型中最多 32 轮后移出范围归零循环必然结束。四、实现细节边界防护初始化sum1 0、sum2 0临时变量循环内赋值。边界防护循环条件是while (b)进位非 0 才继续若写成while (a)则逻辑错误(a b) 1中若最高位产生进位会移出 int 范围有符号左移溢出为 UB但本题保证结果在 int 内故安全负数用补码参与运算无需特判符号。复杂度时间 O(1)最多循环 32 次每轮位运算 O(1)空间 O(1)两个临时变量。关键操作sum1 a ^ b;无进位和、sum2 (a b) 1;进位左移、a sum1; b sum2;迭代更新。 例子负数补码如何自动正确a -1, b 1补码下-1 0xFFFFFFFF、1 0x00000001。第 1 轮sum1 0xFFFFFFFE -2、sum2 (0xFFFFFFFF 1) 1 2第 2 轮a-2, b2sum1 0xFFFFFFFC ^ ...继续迭代最终收敛到0✅——补码让位运算自动处理符号无需区分正负。五、返回值目标映射返回a两数之和循环结束时b 0a已累积全部结果对应题目不使用 和 - 计算两整数之和。三.代码class Solution { public: int getSum(int a, int b) { int sum1 0; // 无进位和异或结果 int sum2 0; // 进位与运算后左移一位 // 只要还有进位就把它当作新的加数继续相加 while (b) { sum1 a ^ b; // 异或同位不同为 1得到“不含进位”的本位和 sum2 (a b) 1; // 与运算找出同为 1 的位产生进位左移送到高位 a sum1; // 更新本位和成为新的 a b sum2; // 更新进位成为新的 b下一轮继续相加 } // 进位为 0 时a 就是最终的和 return a; } };四、易错点分析难点1为什么a ^ b是无进位和sum1 a ^ b; // 异或异或的规则是同位不同为 1、相同为 0。二进制加法中不考虑进位时000、011、101、110本位为 0、产生进位——这与异或的真值表完全一致。所以a ^ b恰好给出丢掉进位的本位和。不理解真值表的对应关系就容易误以为异或能直接算出加法。难点2为什么进位是(a b) 1而不是a bsum2 (a b) 1; // 必须左移一位a b找出的是两数同为 1 的位这些位在加法中会产生进位但进位要送到更高一位所以必须左移一位。若漏掉 1进位会被放在原位与本位和重叠相加结果完全错误——这是本题最常见的错误且a b本身看着很合理容易漏移位。难点3循环条件为什么是while (b)而不是while (a)while (b) // b 是进位循环的终止条件是进位为 0b在本算法中被复用为进位。当b 0时a ^ 0 a、(a 0) 1 0继续循环也不会再变化说明加法已完成。若写成while (a)则可能在进位未处理完时提前退出或在a 0却有进位时直接跳过循环返回错误结果。难点4为什么循环最多 32 次必然终止b (a b) 1; // 每轮至少左移一位每轮新的进位b都是上一轮a b左移一位的结果即进位的最低位至少上移一位。int 只有 32 位进位最终必然移出最高位变成 0 或被丢弃。因此最多 32 轮后b 0循环结束——终止性由位宽有限保证这是位运算循环不会死循环的根本原因。难点5负数与有符号左移的溢出问题sum2 (a b) 1; // 有符号左移最高位进位会溢出C 中有符号整数左移溢出是 UB未定义行为。本题中a b若最高位为 1左移会溢出 int理论上属于 UB。LeetCode 的用例保证结果在 int 范围内故实际可通过但严谨写法应使用unsigned int无符号左移是良定义的取模行为或long long承载进位避免 UB——这是位运算题常见的隐藏陷阱。五、流程图 闭幕 恭喜你完成了「两整数之和」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题用异或计算无进位和用与运算左移计算进位循环直到进位为 0。为什么异或能得到无进位和与运算左移为什么代表进位循环条件while (b)中b初始是第二个加数后来变成进位。为什么当进位为 0 时a就是最终结果如果进位永远不为 0 会怎样代码中sum2 (a b) 1使用左移一位。为什么进位要左移如果不左移结果会怎样延伸挑战如果要求不用和-实现减法a - b你如何基于本题的加法器改造请描述核心思路。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案异或相同位为 0不同位为 1正好对应“不考虑进位时的本位和”。与运算只有两位都为 1 时才为 1表示该位产生进位左移一位送到更高位。当进位为 0 时说明没有需要再向高位传播的进位此时a已包含所有位的最终和返回即可。进位在有限位整数中最终会左移出最高位变为 0所以循环一定终止。进位必须左移因为进位是加到高一位的。例如11在最低位产生进位应加到十位即左移 1 位。不左移会错误地加回本位。延伸挑战答案减法a - b可转化为a (-b)其中-b可通过~b 1得到补码取负然后调用加法器即可。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨ LeetCode 371 ： 两整数之和（位运算） —— 题解
欢迎阅读 欢迎来到「两整数之和」题解之旅本文将带你从不用加号算出两数之和这一看似矛盾的场景出发深入理解位运算模拟加法的巧妙运用并掌握如何用异或求无进位和、与运算求进位来在循环中完成加法。在开始之前建议你先了解题目背景这是 LeetCode 371 题给定两个整数a和b要求不使用、-运算符计算它们的和。本质上加法的二进制过程可拆为**无进位和与进位两部分**反复迭代直到进位为 0问题转化为位运算的递归/循环模拟。明确学习目标掌握异或求无进位和、(a b) 1求进位的核心公式理解为什么循环必然终止并熟练处理负数补码参与运算等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如a 1, b 2输出3a 2, b 3输出5。本文将从问题转化、无进位和、进位传递、终止条件到代码实现层层递进。即使你对位运算还不熟悉我们也会从先加不算进位的再把进位补上去这一直觉出发让你轻松抓住核心思想——异或得和、与移得进位进位清零即成。现在让我们一起用位运算模拟加法吧 ➕愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》钱塘江上潮信来今日方知我是我✨当前学习内容《位运算》一.题目371. 两整数之和 - 力扣LeetCode 二、算法分析一、问题分析前置分析题目要求计算a b不允许使用、-运算符。关键约束a、b可能为负数结果可能溢出 int 范围题目保证在 int 内。核心思路十进制加法可拆为本位与进位——二进制同理a ^ b 无进位和(a b) 1 进位。把进位当作新的加数反复相加直到进位为 0得到最终结果全程只用到位运算。 例子为什么异或与与运算能拆分加法a 1 (01), b 2 (10)a ^ b 11 3每一位都不同无进位直接是一位的和a b 00没有同为 1 的位故无进位→ 结果 3。再看a 1 (01), b 3 (11)a ^ b 10 2不吃进位的本位和、a b 01左移一位10 2就是该进上去的进位——加法的本质被拆成和与进位两部分。二、算法策略位运算模拟加法 · 异或 与移核心步骤循环条件只要b ! 0还有进位就继续。计算无进位和sum1 a ^ b异或同位不同为 1不处理进位。计算进位sum2 (a b) 1同为 1 的位产生进位左移一位送到高位。更新迭代a sum1新的和、b sum2新的进位下轮继续相加。返回进位为 0 时循环结束a即最终结果。 示例a 2 (010), b 3 (011)期待5轮次absum1 a^bsum2 (ab)1说明初始010 (2)011 (3)——准备相加第1轮010011001 (1)(010)1 100 (4)本位和 1进位 4第2轮001 (1)100 (4)101 (5)(000)1 000 (0)本位和 5无进位结束101 (5)0——b0 退出返回5✅第 1 轮把23拆成本位和 1 与进位 4第 2 轮把 1 和 4 相加得 5 且不再产生进位——两轮就把加法完成与2 3 5一致。三、正确性说明简单版本拆分完备二进制加法中每一位的本位结果由两数该位是否不同决定^是否向高位进位由两数该位是否同为 1决定后左移。两者合起来恰好完整描述加法不重不漏。迭代等价把进位b当作新的加数与sum1相加正是先算本位、再补进位的加法过程每轮结果与真实加法逐步逼近。必然终止每轮b (a b) 1进位至少左移一位而 int 只有 32 位进位最终会移出高位变为 0循环最多执行 32 次即结束不会死循环。负数天然支持C 中整数用补码存储位运算直接作用于补码负数参与^、、的结果与真实加法的补码完全一致无需特判。 例子进位为什么必然消失a 1, b 1第 1 轮sum1 0、sum2 (11)1 2进位到第 1 位第 2 轮a0, b2sum1 2、sum2 (02)1 0无进位→ 返回 2 ✅。进位每次至少左移一位在 32 位整型中最多 32 轮后移出范围归零循环必然结束。四、实现细节边界防护初始化sum1 0、sum2 0临时变量循环内赋值。边界防护循环条件是while (b)进位非 0 才继续若写成while (a)则逻辑错误(a b) 1中若最高位产生进位会移出 int 范围有符号左移溢出为 UB但本题保证结果在 int 内故安全负数用补码参与运算无需特判符号。复杂度时间 O(1)最多循环 32 次每轮位运算 O(1)空间 O(1)两个临时变量。关键操作sum1 a ^ b;无进位和、sum2 (a b) 1;进位左移、a sum1; b sum2;迭代更新。 例子负数补码如何自动正确a -1, b 1补码下-1 0xFFFFFFFF、1 0x00000001。第 1 轮sum1 0xFFFFFFFE -2、sum2 (0xFFFFFFFF 1) 1 2第 2 轮a-2, b2sum1 0xFFFFFFFC ^ ...继续迭代最终收敛到0✅——补码让位运算自动处理符号无需区分正负。五、返回值目标映射返回a两数之和循环结束时b 0a已累积全部结果对应题目不使用 和 - 计算两整数之和。三.代码class Solution { public: int getSum(int a, int b) { int sum1 0; // 无进位和异或结果 int sum2 0; // 进位与运算后左移一位 // 只要还有进位就把它当作新的加数继续相加 while (b) { sum1 a ^ b; // 异或同位不同为 1得到“不含进位”的本位和 sum2 (a b) 1; // 与运算找出同为 1 的位产生进位左移送到高位 a sum1; // 更新本位和成为新的 a b sum2; // 更新进位成为新的 b下一轮继续相加 } // 进位为 0 时a 就是最终的和 return a; } };四、易错点分析难点1为什么a ^ b是无进位和sum1 a ^ b; // 异或异或的规则是同位不同为 1、相同为 0。二进制加法中不考虑进位时000、011、101、110本位为 0、产生进位——这与异或的真值表完全一致。所以a ^ b恰好给出丢掉进位的本位和。不理解真值表的对应关系就容易误以为异或能直接算出加法。难点2为什么进位是(a b) 1而不是a bsum2 (a b) 1; // 必须左移一位a b找出的是两数同为 1 的位这些位在加法中会产生进位但进位要送到更高一位所以必须左移一位。若漏掉 1进位会被放在原位与本位和重叠相加结果完全错误——这是本题最常见的错误且a b本身看着很合理容易漏移位。难点3循环条件为什么是while (b)而不是while (a)while (b) // b 是进位循环的终止条件是进位为 0b在本算法中被复用为进位。当b 0时a ^ 0 a、(a 0) 1 0继续循环也不会再变化说明加法已完成。若写成while (a)则可能在进位未处理完时提前退出或在a 0却有进位时直接跳过循环返回错误结果。难点4为什么循环最多 32 次必然终止b (a b) 1; // 每轮至少左移一位每轮新的进位b都是上一轮a b左移一位的结果即进位的最低位至少上移一位。int 只有 32 位进位最终必然移出最高位变成 0 或被丢弃。因此最多 32 轮后b 0循环结束——终止性由位宽有限保证这是位运算循环不会死循环的根本原因。难点5负数与有符号左移的溢出问题sum2 (a b) 1; // 有符号左移最高位进位会溢出C 中有符号整数左移溢出是 UB未定义行为。本题中a b若最高位为 1左移会溢出 int理论上属于 UB。LeetCode 的用例保证结果在 int 范围内故实际可通过但严谨写法应使用unsigned int无符号左移是良定义的取模行为或long long承载进位避免 UB——这是位运算题常见的隐藏陷阱。五、流程图 闭幕 恭喜你完成了「两整数之和」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题用异或计算无进位和用与运算左移计算进位循环直到进位为 0。为什么异或能得到无进位和与运算左移为什么代表进位循环条件while (b)中b初始是第二个加数后来变成进位。为什么当进位为 0 时a就是最终结果如果进位永远不为 0 会怎样代码中sum2 (a b) 1使用左移一位。为什么进位要左移如果不左移结果会怎样延伸挑战如果要求不用和-实现减法a - b你如何基于本题的加法器改造请描述核心思路。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案异或相同位为 0不同位为 1正好对应“不考虑进位时的本位和”。与运算只有两位都为 1 时才为 1表示该位产生进位左移一位送到更高位。当进位为 0 时说明没有需要再向高位传播的进位此时a已包含所有位的最终和返回即可。进位在有限位整数中最终会左移出最高位变为 0所以循环一定终止。进位必须左移因为进位是加到高一位的。例如11在最低位产生进位应加到十位即左移 1 位。不左移会错误地加回本位。延伸挑战答案减法a - b可转化为a (-b)其中-b可通过~b 1得到补码取负然后调用加法器即可。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨