LeetCode题练习与总结：两整数之和--371

一、题目描述

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

示例 1：

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

示例 2：

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

提示：

-1000 <= a, b <= 1000

二、解题思路

这个问题可以通过位运算来解决。位运算中的“与”操作（&）和“异或”操作（^）可以帮助我们实现加法。以下是解题步骤：

使用“异或”操作（^）计算不带进位的和。异或操作可以理解为不考虑进位的加法操作。
使用“与”操作（&）然后左移一位（<<）计算进位。如果两个位都是1，那么就会产生进位。
将不带进位的和与进位相加，重复步骤1和步骤2，直到没有进位为止。
当进位为0时，不带进位的和就是最终结果。

三、具体代码

class Solution {public int getSum(int a, int b) {while (b != 0) {// 计算不带进位的和int temp = a ^ b;// 计算进位b = (a & b) << 1;// 将不带进位的和赋值给a，用于下一轮计算a = temp;}// 当没有进位时，a就是最终结果return a;}
}

这段代码通过循环不断地计算不带进位的和以及进位，直到没有进位为止，最后返回的结果即为两数之和。

四、时间复杂度和空间复杂度

1. 时间复杂度

该算法包含一个循环，循环的次数取决于进位（b）的次数。
在最坏的情况下，如果 a 和 b 都是最大值（例如 1000），进位可能会发生多次，但是因为 b 是在每次迭代中被更新为进位后的值，所以进位发生的次数是有限的。
每一次循环都会至少减少一个进位（即 b 中的一个最高位的1），因此循环次数最多为 a 和 b 中最高位1的位置数，这个数字通常远小于 a 和 b 的位数。
假设 a 和 b 都是 32 位整数，那么循环最多执行 32 次（即每个位上都有进位）。

因此，时间复杂度是 O(1)，因为循环的次数是常数级别的，不随输入规模变化。

2. 空间复杂度

该算法只使用了固定数量的额外空间，即 temp 变量和 b 的更新值。
这些变量都是整数类型，占用的空间是常数级别的。

因此，空间复杂度也是 O(1)，因为无论输入规模如何，算法使用的额外空间都不会改变。

五、总结知识点

位运算符：
- 异或运算符（^）：用于计算不带进位的和。如果两个位不相同，则结果为1；如果相同，则结果为0。
- 与运算符（&）：用于找出哪些位会进位。如果两个位都是1，则结果为1，表示需要进位；否则结果为0。
- 左移运算符（<<）：用于将进位左移一位，以便在下一次迭代中加到不带进位的和上。
循环控制：
- while循环：用于重复执行位运算操作，直到没有进位为止（即 b 等于0）。
整数类型：
- 使用 int 类型来存储整数，这是Java中的基本数据类型之一，用于表示32位的有符号整数。
变量赋值：
- 使用赋值运算符（=）来更新变量 a 和 b 的值。
逻辑运算：
- 使用 != 运算符来检查 b 是否不等于0，这是循环的继续条件。
函数返回值：
- 使用 return 语句来返回最终的计算结果。
算法思想：
- 使用位运算来模拟加法操作，这是解决不使用加号实现加法问题的核心思想。