九日集训 Leetcode 371.两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

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

示例 2：

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

提示：

-1000 <= a, b <= 1000

一、信息

1.给我两个整数

2.不使用+和-号

3.计算两整数之和

二、步骤

第一步申请两个整型变量

第二步输入两个整数并赋值给这两个整型变量

第三步 return 即可

三、分析

问题出现：

问题1：题目中告诉我们不能用+和-那我们该怎么运算呢？

思考：

首先我们先来回忆一下记忆空间中哪些加法的实现可以不用+-，我能想到的第一个就是二进制加法这在计算机组成原理设计加法器中就有所体现。

那我们先观察一下二级进制加法的特点以便提取其中的规律

1 1 0 1（13）

+1 0 1 0（10）

——————

1 0 1 1 1（23）

不难看出二进制的加法实则就是异或运算

但是又有不同因为加法有时会进位那么新的问题就出现了其次二进制中可没有正负号，而且负数的加法又该怎么设计呢？这样又要引入反码和补码，又一个问题出现

问题2：该如何解决进位问题？

通过移位运算符，问题又出现了，移位运算符该怎么用呢？问题三解决了。那么接下来就要解决这个问题了。

目前确定两种思路：

思路一直接异或

是直接异或在异或的过程中记录进了多少位

思路二模拟

就是一位一位的进位模拟这样的好处是省去了思考难度直接根据平时计算的习惯，算一位然后检查是否进位，如果进位那么下一位在异或的时候就要在异或进位的数，直接通过循环控制

问题3：位运算符怎么用

我的这篇文章有讲解

答案：

传送门：4.8 位运算符

问题四：该如何解决负数的问题引入符号位吗？

存储的数据结构：

思路一：我觉得由于这个实现的机制我们可以把它先存在一个整型变量中

思路二：一位一位的存我认为最直观的还是存在一列数组里面

答案：

我的答案：

我们可以使用位运算来实现这个功能。下面是基本思路：

1. **无进位和**：进行异或运算。
2. **进位**：进行与运算，并左移一位。
3. 将无进位和与进位相加，即重复上述两步，直到进位为0。

### C语言实现

#include <stdio.h>int getSum(int a, int b) {while(b != 0) {unsigned int carry = (unsigned int)(a & b) << 1; // 计算进位a = a ^ b; // 计算无进位和b = carry; // 更新进位}return a;
}int main() {printf("%d\n", getSum(1, 2)); // 输出3printf("%d\n", getSum(2, 3)); // 输出5return 0;
}

### C++实现

#include <iostream>class Solution {
public:int getSum(int a, int b) {while (b != 0) {unsigned int carry = (unsigned int)(a & b) << 1; // 计算进位a = a ^ b; // 计算无进位和b = carry; // 更新进位}return a;}
};int main() {Solution solution;std::cout << solution.getSum(1, 2) << std::endl; // 输出3std::cout << solution.getSum(2, 3) << std::endl; // 输出5return 0;
}

### Java实现

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;}public static void main(String[] args) {Solution solution = new Solution();System.out.println(solution.getSum(1, 2)); // 输出3System.out.println(solution.getSum(2, 3)); // 输出5}
}

### 分析过程

1. **异或运算**：异或运算可以得到两个整数的无进位和。例如，对于二进制数`1101`和`1001`，其无进位和为`0100`。

2. **与运算**：与运算可以得到两个整数的进位。例如，对于二进制数`1101`和`1001`，其进位为`1001`。

3. **左移运算**：左移一位可以得到进位后的值。例如，`1001`左移一位为`10010`。

4. **循环**：将无进位和与进位相加，即重复上述三个步骤，直到进位为0。这是因为每一次无进位和与进位相加，都可能产生新的进位。当进位为0时，无进位和即为两数之和。

这个方法可以避免使用加法和减法运算符，仅通过位运算实现两整数的加法。