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) .
そして、これが LeetCode Meditations シリーズの最後の問題です!次の投稿で結論を述べます。それまで、コーディングを楽しんでください。
以上がLeetCode 瞑想: 2 つの整数の合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。