LeetCode 瞑想: 2 つの整数の合計

2 つの整数の合計についての説明は非常に簡単です:

2 つの整数 a と b が与えられた場合、演算子を使用せずに 2 つの整数の合計を返します および -.

例:

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

または:

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

---

このシリーズの最後の問題では、人気のプラス演算子の代わりにビット操作を使用して 2 つの整数を加算して終了します。

2 つのビットを加算しても、どちらも 1 か 0 のみになり、結果はそれほど変わりません。
1 と 0 (または 0 と 1) の 2 つのビットを追加すると、結果は 1 になります。0 のビットを 2 つ追加すると、結果は 0 になります。ただし、1 を 2 つ追加すると、結果は 0 になります。 キャリーがあります。つまり、出力に0を書き込む必要がありますが、キャリーも必要です。 1.

たとえば、2 と 3 を加算すると 5 になり、演算中に桁上げ値が得られます。

桁上げ値について考えなければ、2 ビットを追加した後に必要な出力は、XOR 演算後に得られるものとよく似ています。異なるビット (0 と 1、または 1 と 0) がある場合、出力は 1 になり、それ以外の場合は 0 (0 と 0 を加算する) になります。 、1 と 1)。

したがって、XOR 演算は出力に役立ちます。

キャリーはどうですか?

両方のビットが 1 の場合にのみキャリー値が得られます。これは AND 演算のように見えます。

したがって、AND 演算は桁上げに役立ちます。

キャリー値が左にシフトされることにも注意してください。これには便利な左シフト演算子もあります。

したがって、出力とキャリーは次のようになります:

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

持っている 2 つの値を変更し続け、キャリー値がなくなるまで作業を続けることができます。 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 瞑想: 2 つの整数の合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。