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) O(1)

---

. 而且，這就是 LeetCode Meditations 系列的最後一題！我們將在下一篇文章中給出結論——在此之前，祝您編碼愉快。

以上是LeetCode 冥想：兩個整數總和的詳細內容。更多資訊請關注PHP中文網其他相關文章！