LeetCode 371《两整数之和》位运算解法详解不借助加减号实现加法LeetCode-Book 精选题解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本文是《Krahets 笔面试精选 88 题》题单中 371. 两整数之和 的深度题解对应仓库中 selected_coding_interview/docs/371. 两整数之和.md 一文的完整展开。题目要求在不使用运算符和-的前提下计算两个整数的和核心考点是位运算实现加法。读完本文你将掌握异或^与无进位和、与运算与进位之间的等价关系能够独立推导并实现 Java / C / Python 三种语言的getSum解法并理解 Python 中负数补码的特殊处理方式。一、问题本质把加法拆成无进位和 进位设两个数字的二进制形式为 $a, b$其求和 $s a b$。若逐位考察$a(i)$ 代表 $a$ 的二进制第 $i$ 位$b(i)$ 代表 $b$ 的二进制第 $i$ 位则每一位的运算结果可以分为四种情况$a(i)$$b(i)$无进位和 $n(i)$进位 $c(i1)$$0$$0$$0$$0$$0$$1$$1$$0$$1$$0$$1$$0$$1$$1$$0$$1$观察真值表可以发现两条关键规律无进位和与异或运算^的规律完全一致两 bit 相同得 0、相异得 1进位与与运算的规律一致两 bit 均为 1 时产生进位且进位需要左移一位才能落到正确的更高位。于是无进位和 $n$ 与进位 $c$ 可以统一写成$$ \begin{cases} n a \oplus b 非进位和异或运算 \ c a b 1 进位与运算 左移一位 \end{cases} $$而“和 $s$”恰好等于“非进位和 $n$”与“进位 $c$”之和因此原问题被等价转化为$$ s a b \Rightarrow s n c $$只要循环求 $n$ 和 $c$直至进位 $c 0$此时 $s n$直接返回 $n$ 即可。整个过程只用到位运算完全避开了/-运算符。二、三种语言的实现代码原文档给出了 Java、C、Python 三份完整实现以下代码与 selected_coding_interview/codes 目录中的仓库源码保持一致。Java 实现对应仓库文件lc_371_sum_of_two_integers.javaclass Solution { public int getSum(int a, int b) { // 循环当进位为 0 时跳出 while (b ! 0) { int c (a b) 1; // c 进位 a ^ b; // a 非进位和 b c; // b 进位 } return a; } }C 实现对应仓库文件lc_371_sum_of_two_integers_s1.cppclass Solution { public: int getSum(int a, int b) { // 循环当进位为 0 时跳出 while (b ! 0) { int c (unsigned int)(a b) 1; // c 进位 a ^ b; // a 非进位和 b c; // b 进位 } return a; } };注意C 中左移负数属于未定义行为因此代码将(a b)先强转为unsigned int再左移避免对负数做左移运算时产生未定义行为。这是 C 版本与 Java 版本唯一的实现差异。Python 实现对应仓库文件lc_371_sum_of_two_integers.pyclass Solution: def getSum(self, a: int, b: int) - int: x 0xffffffff a, b a x, b x # 循环当进位为 0 时跳出 while b ! 0: # a, b 非进位和, 进位 a, b (a ^ b), (a b) 1 x return a if a 0x7fffffff else ~(a ^ x)三种语言的循环骨架完全一致while b ! 0判断进位是否清零循环体内同时更新“非进位和a”与“进位b”。仓库中 C 文件还附带了可直接运行的测试驱动a 1, b 2输出3Java 与 Python 文件则预留了 Test Case / Driver Code 结构方便自行补全用例验证。三、补码为什么正负数的加法都能被统一处理一个重要的事实是在计算机系统中数值一律用补码来表示和存储。补码的核心优势在于——加法、减法可以统一处理CPU 只需加法器即可完成全部整数运算。这意味着上述“非进位和 进位”的位运算方法同时适用于正数和负数的加法负数在补码形式下同样满足异或、与运算的逐位规律减法a (-b)本质上仍是补码加法因此不需要任何额外分支。这也是本题能成立的根本前提加法器的硬件实现正是异或得和、与得进位、左移进位、迭代直至无进位这一套逻辑的物理载体。理解这一点后位运算求和的思路就不仅是技巧而是对计算机底层运算机制的还原。四、复杂度分析时间复杂度 $O(1)$最差情况下例如 $a \text{0x7fffffff}$、$b 1$ 时需要循环 32 次属于常数次迭代每轮中的位运算均为常数时间操作因此总体为 $O(1)$ 时间。空间复杂度 $O(1)$只使用了常数大小的额外空间仅一个临时变量保存进位。在 LeetCode 的 32 位int语义下进位最终必然在 32 次迭代内归零因此循环次数有明确上界。五、Python 的特殊处理无位数概念下的补码由于 Python 的数字存储特点需要做特殊考虑。Python、Java、C 等语言中的数字都是以补码形式存储的。但 Python 没有int、long等不同长度的整数类型编程时没有“位数”的概念——整数可以无限扩展负数的补码在概念上是无限长的 1 序列。因此 Python 版本需要额外两步处理1. 获取负数的补码入口截断获取负数的补码需要将数字与十六进制数 $\text{0xffffffff}$ 相与。这一步可以理解为舍去此数字 32 位以上的数字将 32 位以上全部置为 $0$把无限长度的整数“截断”为一个 32 位整数从而与 Java / C 的int语义对齐print(hex(1)) # 0x1 补码 print(hex(-1)) # -0x1 负号 原码 Python 特色Java 会直接输出补码 print(hex(1 0xffffffff)) # 0x1 正数补码 print(hex(-1 0xffffffff)) # 0xffffffff 负数补码 print(-1 0xffffffff) # 4294967295 Python 将其认为正数从输出可以看到hex(-1)在 Python 中显示为-0x1负号 原码这是 Python 的显示特色而 Java 会直接输出补码执行-1 0xffffffff后得到0xffffffff即 32 位补码形式此时 Python 将其视为正数4294967295。2. 返回前数字还原出口还原返回前数字还原循环结束后若补码 $a$ 为负数$\text{0x7fffffff}$ 是 32 位最大的正数的补码即最高位为 0 的上界需执行~(a ^ x)操作将 32 位补码还原为 Python 的存储格式。拆解来看a ^ x将 1 至 32 位按位取反~对整个数字取反二者组合~(a ^ x)将 32 位以上的位取反而 1 至 32 位保持不变从而把截断后的无符号形式还原为 Python 中真正的负数。这也是 Python 解法中return a if a 0x7fffffff else ~(a ^ x)这行代码的完整含义。同样的处理手法也出现在仓库 sword_for_offer/codes/python/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.py剑指 Offer 65 题解测试用例a 1, b 1中说明这是该项目 Python 位运算题解的统一约定。六、在仓库中进一步探索本题在仓库中有多处对应实现可相互印证语言仓库路径Javaselected_coding_interview/codes/java/lc_371_sum_of_two_integers/lc_371_sum_of_two_integers.javaCselected_coding_interview/codes/cpp/lc_371_sum_of_two_integers/lc_371_sum_of_two_integers_s1.cppPythonselected_coding_interview/codes/python/lc_371_sum_of_two_integers.py同源题剑指 Offer 65sword_for_offer/codes/python/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.py此外LeetCode-Book 仓库的《图解算法数据结构》分册中LCR 190. 加密运算 一题与本题考察的是完全相同的位运算加法模型仅变量名不同读者可以对照阅读体会同一考点在不同题面下的变形。仓库整体结构可参考 README.mdleetbook_ioa、selected_coding_interview、sword_for_offer三个分册分别对应《图解算法数据结构》《Krahets 笔面试精选 88 题》《剑指 Offer》的题解与源码。七、小结核心模型s n c其中 $n a \oplus b$无进位和$c (a b) 1$进位循环迭代直至 $c 0$。正确性前提计算机以补码存储整数加/减统一为加法运算因此该算法对正负数同样成立。语言差异Java / C 依赖定长int自然结束循环C 需用unsigned int规避负数左移的未定义行为Python 需通过 0xffffffff截断、~(a ^ x)还原来处理无位数概念下的补码。复杂度时间 $O(1)$最多 32 次迭代空间 $O(1)$。掌握本题后你不仅会解一道题更理解了加法器在硬件层面的工作方式——这是位运算题目中最值得沉淀的原理性收获。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 371《两整数之和》位运算解法详解：不借助加减号实现加法（LeetCode-Book 精选题解）
LeetCode 371《两整数之和》位运算解法详解不借助加减号实现加法LeetCode-Book 精选题解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本文是《Krahets 笔面试精选 88 题》题单中 371. 两整数之和 的深度题解对应仓库中 selected_coding_interview/docs/371. 两整数之和.md 一文的完整展开。题目要求在不使用运算符和-的前提下计算两个整数的和核心考点是位运算实现加法。读完本文你将掌握异或^与无进位和、与运算与进位之间的等价关系能够独立推导并实现 Java / C / Python 三种语言的getSum解法并理解 Python 中负数补码的特殊处理方式。一、问题本质把加法拆成无进位和 进位设两个数字的二进制形式为 $a, b$其求和 $s a b$。若逐位考察$a(i)$ 代表 $a$ 的二进制第 $i$ 位$b(i)$ 代表 $b$ 的二进制第 $i$ 位则每一位的运算结果可以分为四种情况$a(i)$$b(i)$无进位和 $n(i)$进位 $c(i1)$$0$$0$$0$$0$$0$$1$$1$$0$$1$$0$$1$$0$$1$$1$$0$$1$观察真值表可以发现两条关键规律无进位和与异或运算^的规律完全一致两 bit 相同得 0、相异得 1进位与与运算的规律一致两 bit 均为 1 时产生进位且进位需要左移一位才能落到正确的更高位。于是无进位和 $n$ 与进位 $c$ 可以统一写成$$ \begin{cases} n a \oplus b 非进位和异或运算 \ c a b 1 进位与运算 左移一位 \end{cases} $$而“和 $s$”恰好等于“非进位和 $n$”与“进位 $c$”之和因此原问题被等价转化为$$ s a b \Rightarrow s n c $$只要循环求 $n$ 和 $c$直至进位 $c 0$此时 $s n$直接返回 $n$ 即可。整个过程只用到位运算完全避开了/-运算符。二、三种语言的实现代码原文档给出了 Java、C、Python 三份完整实现以下代码与 selected_coding_interview/codes 目录中的仓库源码保持一致。Java 实现对应仓库文件lc_371_sum_of_two_integers.javaclass Solution { public int getSum(int a, int b) { // 循环当进位为 0 时跳出 while (b ! 0) { int c (a b) 1; // c 进位 a ^ b; // a 非进位和 b c; // b 进位 } return a; } }C 实现对应仓库文件lc_371_sum_of_two_integers_s1.cppclass Solution { public: int getSum(int a, int b) { // 循环当进位为 0 时跳出 while (b ! 0) { int c (unsigned int)(a b) 1; // c 进位 a ^ b; // a 非进位和 b c; // b 进位 } return a; } };注意C 中左移负数属于未定义行为因此代码将(a b)先强转为unsigned int再左移避免对负数做左移运算时产生未定义行为。这是 C 版本与 Java 版本唯一的实现差异。Python 实现对应仓库文件lc_371_sum_of_two_integers.pyclass Solution: def getSum(self, a: int, b: int) - int: x 0xffffffff a, b a x, b x # 循环当进位为 0 时跳出 while b ! 0: # a, b 非进位和, 进位 a, b (a ^ b), (a b) 1 x return a if a 0x7fffffff else ~(a ^ x)三种语言的循环骨架完全一致while b ! 0判断进位是否清零循环体内同时更新“非进位和a”与“进位b”。仓库中 C 文件还附带了可直接运行的测试驱动a 1, b 2输出3Java 与 Python 文件则预留了 Test Case / Driver Code 结构方便自行补全用例验证。三、补码为什么正负数的加法都能被统一处理一个重要的事实是在计算机系统中数值一律用补码来表示和存储。补码的核心优势在于——加法、减法可以统一处理CPU 只需加法器即可完成全部整数运算。这意味着上述“非进位和 进位”的位运算方法同时适用于正数和负数的加法负数在补码形式下同样满足异或、与运算的逐位规律减法a (-b)本质上仍是补码加法因此不需要任何额外分支。这也是本题能成立的根本前提加法器的硬件实现正是异或得和、与得进位、左移进位、迭代直至无进位这一套逻辑的物理载体。理解这一点后位运算求和的思路就不仅是技巧而是对计算机底层运算机制的还原。四、复杂度分析时间复杂度 $O(1)$最差情况下例如 $a \text{0x7fffffff}$、$b 1$ 时需要循环 32 次属于常数次迭代每轮中的位运算均为常数时间操作因此总体为 $O(1)$ 时间。空间复杂度 $O(1)$只使用了常数大小的额外空间仅一个临时变量保存进位。在 LeetCode 的 32 位int语义下进位最终必然在 32 次迭代内归零因此循环次数有明确上界。五、Python 的特殊处理无位数概念下的补码由于 Python 的数字存储特点需要做特殊考虑。Python、Java、C 等语言中的数字都是以补码形式存储的。但 Python 没有int、long等不同长度的整数类型编程时没有“位数”的概念——整数可以无限扩展负数的补码在概念上是无限长的 1 序列。因此 Python 版本需要额外两步处理1. 获取负数的补码入口截断获取负数的补码需要将数字与十六进制数 $\text{0xffffffff}$ 相与。这一步可以理解为舍去此数字 32 位以上的数字将 32 位以上全部置为 $0$把无限长度的整数“截断”为一个 32 位整数从而与 Java / C 的int语义对齐print(hex(1)) # 0x1 补码 print(hex(-1)) # -0x1 负号 原码 Python 特色Java 会直接输出补码 print(hex(1 0xffffffff)) # 0x1 正数补码 print(hex(-1 0xffffffff)) # 0xffffffff 负数补码 print(-1 0xffffffff) # 4294967295 Python 将其认为正数从输出可以看到hex(-1)在 Python 中显示为-0x1负号 原码这是 Python 的显示特色而 Java 会直接输出补码执行-1 0xffffffff后得到0xffffffff即 32 位补码形式此时 Python 将其视为正数4294967295。2. 返回前数字还原出口还原返回前数字还原循环结束后若补码 $a$ 为负数$\text{0x7fffffff}$ 是 32 位最大的正数的补码即最高位为 0 的上界需执行~(a ^ x)操作将 32 位补码还原为 Python 的存储格式。拆解来看a ^ x将 1 至 32 位按位取反~对整个数字取反二者组合~(a ^ x)将 32 位以上的位取反而 1 至 32 位保持不变从而把截断后的无符号形式还原为 Python 中真正的负数。这也是 Python 解法中return a if a 0x7fffffff else ~(a ^ x)这行代码的完整含义。同样的处理手法也出现在仓库 sword_for_offer/codes/python/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.py剑指 Offer 65 题解测试用例a 1, b 1中说明这是该项目 Python 位运算题解的统一约定。六、在仓库中进一步探索本题在仓库中有多处对应实现可相互印证语言仓库路径Javaselected_coding_interview/codes/java/lc_371_sum_of_two_integers/lc_371_sum_of_two_integers.javaCselected_coding_interview/codes/cpp/lc_371_sum_of_two_integers/lc_371_sum_of_two_integers_s1.cppPythonselected_coding_interview/codes/python/lc_371_sum_of_two_integers.py同源题剑指 Offer 65sword_for_offer/codes/python/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.py此外LeetCode-Book 仓库的《图解算法数据结构》分册中LCR 190. 加密运算 一题与本题考察的是完全相同的位运算加法模型仅变量名不同读者可以对照阅读体会同一考点在不同题面下的变形。仓库整体结构可参考 README.mdleetbook_ioa、selected_coding_interview、sword_for_offer三个分册分别对应《图解算法数据结构》《Krahets 笔面试精选 88 题》《剑指 Offer》的题解与源码。七、小结核心模型s n c其中 $n a \oplus b$无进位和$c (a b) 1$进位循环迭代直至 $c 0$。正确性前提计算机以补码存储整数加/减统一为加法运算因此该算法对正负数同样成立。语言差异Java / C 依赖定长int自然结束循环C 需用unsigned int规避负数左移的未定义行为Python 需通过 0xffffffff截断、~(a ^ x)还原来处理无位数概念下的补码。复杂度时间 $O(1)$最多 32 次迭代空间 $O(1)$。掌握本题后你不仅会解一道题更理解了加法器在硬件层面的工作方式——这是位运算题目中最值得沉淀的原理性收获。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考