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

一、题目描述

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

示例 1：

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

示例 2：

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

提示：

• -1000 <= a, b <= 1000

二、解题思路

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

1. 使用“异或”操作（^）计算不带进位的和。异或操作可以理解为不考虑进位的加法操作。
2. 使用“与”操作（&）然后左移一位（<<）计算进位。如果两个位都是1，那么就会产生进位。
3. 将不带进位的和与进位相加，重复步骤1和步骤2，直到没有进位为止。
4. 当进位为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 语句来返回最终的计算结果。

• 算法思想：

  • 使用位运算来模拟加法操作，这是解决不使用加号实现加法问题的核心思想。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。