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) 



<p>持っている 2 つの値を変更し続け、キャリー値がなくなるまで作業を続けることができます。 a を出力に、b をキャリーに変更して、最後に最終出力を保持する a を返すことができます。</p>

<p>全体として、TypeScript での最終的なソリューションは次のようになります。<br>
</p>

<pre class="brush:php;toolbar:false">function getSum(a: number, b: number): number {
  // while we still have carry
  while (b !== 0) {
    let output = a ^ b;
    let carry = (a & b) 



<h4>
  
  
  時間と空間の複雑さ
</h4>

<p>a と b は両方とも定数値であり、入力に比例してサイズが増加する追加のデータ構造も必要ないため、時間と空間の複雑さは両方とも一定になります。<link rel="stylesheet" href="https://assets.dev.to/assets/katex-7b986a08a52ed11e0e3379cd9c4bb3ccb187f09c249a1de099b16c423e34bb76.css">


  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow>O(1) </semantics></math><span><span>O(1)</span></span></span>
</span>
.</p>


<hr>

<p>そして、これが LeetCode Meditations シリーズの最後の問題です!次の投稿で結論を述べます。それまで、コーディングを楽しんでください。</p>


          

以上がLeetCode 瞑想: 2 つの整数の合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。