LeetCode 冥想：两个整数之和

两个整数之和的描述非常简单：

给定两个整数 a 和 b，返回 两个整数之和，不使用运算符 和 -.

例如：

Input: a = 1, b = 2
Output: 3

或者：

Input: a = 2, b = 3
Output: 5

---

在本系列的最后一个问题中，我们将使用位操作而不是我们喜爱的加运算符来添加两个整数。

添加两个位，其中任何一个只能是 1 或 0，不会有太多不同的结果。
如果我们将 1 和 0（或者 0 和 1）两个位相加，结果将为 1。如果我们将两个 0 位相加，结果将为 0。但是，如果我们将两个 1 添加位，我们有一个 进位 — 这意味着我们必须在输出 中写入 0，但是 还带有一个1.

例如，2和3相加会得到5，我们在运算过程中会有一个进位值：

在不考虑进位值的情况下，添加两位后我们需要的输出与 XOR 运算后的输出非常相似。如果我们有不同的位（0 和 1，或者 1 和 0），输出将为 1，否则为 0（添加 0 和 0，或者，1 和 1)。

因此，异或运算可以帮助我们获得输出。

携带怎么样？

只有当两个位都为 1 时，我们才有进位值——这看起来像 AND 运算。

因此，AND 运算可以帮助我们进行进位。

另请注意，进位值向左移动，为此我们还有一个方便的左移运算符。

因此，我们的输出和进位可以如下所示：

let output = a ^ b;
let carry = (a & b) << 1;

我们可以继续修改现有的两个值，直到没有任何进位值为止。我们可以修改a为输出，b为进位，然后返回a，它保存着最后的最终输出。

总体而言，最终的解决方案在 TypeScript 中可能如下所示：

function getSum(a: number, b: number): number {
  // while we still have carry
  while (b !== 0) {
    let output = a ^ b;
    let carry = (a & b) << 1;
    a = output;
    b = carry;
  }

  return a;
}

时间和空间复杂度

a 和 b 都是常量值，我们也不需要额外的数据结构，其大小会与输入成比例增长，因此我们的时间和空间复杂度都是常量， $O(1)$O(1) .

---

而且，这就是 LeetCode Meditations 系列的最后一题！我们将在下一篇文章中给出结论——在此之前，祝您编码愉快。

以上是LeetCode 冥想：两个整数之和的详细内容。更多信息请关注PHP中文网其他相关文章！