江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第371题：两整数之和

不使用运算符 + 和 -，计算两整数 a、b 之和。

📖 文章摘要

本文详细解析LeetCode第371题“两整数之和”，这是一道位运算问题。文章提供了基于位运算的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升位运算能力的读者。

核心知识点： 位运算、加法器原理、异或运算 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升位运算能力的程序员

题目描述

不使用运算符 + 和 -，计算两整数 a、b 之和。

示例

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

提示

  • -1000 <= a, b <= 1000

解题思路

本题可以使用位运算解决：

  1. 使用异或运算计算无进位和
  2. 使用与运算计算进位
  3. 将进位左移一位
  4. 重复上述步骤直到进位为0

时间复杂度： O(1) 空间复杂度： O(1)

图解思路

位运算过程

步骤 a b 无进位和 进位
1 1 2 3 0
2 2 3 1 4
3 1 4 5 0

二进制表示

数值 二进制 说明
1 0001 第一个数
2 0010 第二个数
3 0011 结果

代码实现

C# 实现

public class Solution {
    public int GetSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

Python 实现

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 处理Python中的负数
        mask = 0xFFFFFFFF
        
        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
            
        # 处理负数结果
        if a > 0x7FFFFFFF:
            a = ~(a ^ mask)
            
        return a

C++ 实现

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

执行结果

C# 实现

  • 执行用时：36 ms
  • 内存消耗：14.8 MB

Python 实现

  • 执行用时：28 ms
  • 内存消耗：13.2 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：5.9 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 5.9 MB 执行效率最高，内存占用最小
Python 28 ms 13.2 MB 代码简洁，内存占用适中
C# 36 ms 14.8 MB 类型安全，内存占用较大

代码亮点

  1. 🎯 使用位运算实现加法
  2. 💡 处理负数情况
  3. 🔍 处理Python特殊整数
  4. 🎨 代码结构清晰，易于维护

常见错误分析

  1. 🚫 未处理负数
  2. 🚫 整数溢出
  3. 🚫 位运算错误
  4. 🚫 Python特殊整数处理

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
位运算 O(1) O(1) 高效，不使用运算符 实现较复杂
循环 O(n) O(1) 直观，易于理解 时间复杂度高

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第371题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！