2 つの整数の合計 - leetcode - Python

「 」演算子を使用せずに 2 つの整数を加算する核心に入りましょう。 これにはバイナリ操作が必要です。

通常の加算と同様に、バイナリを使用してこれにアプローチします。

1. 通常と同じように、右から追加していきます: 1 1、0 1、1 0、0 0。
2. 2 進数で作業しているため、合計が 2 に達したら、0 にリセットします (1 1 = 10 2 進数、桁上げで 0 になります)。
3. すべてのビットに対してこれを繰り返します。これにより、今のところキャリーを無視した部分和が得られます。

XOR (^) ビット演算子は、この初期合計を完全に処理します。

• ビットが同じ場合、結果は 0 になります。ビットが異なる場合、結果は 1 になります。

これは、1 1 → 0 (キャリーあり)、0 1 または 1 0 → 1、および 0 0 → 0 のニーズと一致します。

さて、キャリーについて考えてみましょう。 AND (&) 演算子はそれらを見つけるのに役立ちます:

• 両方のビットが 1 の場合、結果は 1 (キャリー) になります。

キャリーを左にシフトするには、左ビット シフトを使用します。

アルゴリズム:

1. 初期化:
   • sum = a ^ b (キャリーなしの合計の XOR)
   • carry = (a & b) (およびキャリー用)
2. 反復:
   • carry == 0まで繰り返します:
     • a = sum
     • b = carry << 1 (桁上げのための左ビットシフト)

例 (5 3):

1. 初期値:
2. 反復 1:
   • sum = 0101 ^ 0011 = 0110
   • carry = 0101 & 0011 = 0001
3. 反復 2:
   • sum = 0110 ^ 0010 = 0100
   • carry = 0110 & 0010 = 0010
4. 反復 3:
   • sum = 0100 ^ 00100 = 0000
   • carry = 0100 & 0100 = 0100
5. 反復 4:
   • sum = 0000 ^ 1000 = 1000
   • carry = 0000 & 1000 = 0000

キャリーは 0 なので、最終的な合計は 1000 (8) です。

Python の無制限の整数は、負の数で問題を引き起こします。 左ビットシフトは無限の成長につながる可能性があります。 これを修正するには、固定サイズの整数 (例: 32 ビット) をシミュレートする必要があります。

32 ビット マスク (0xFFFFFFFF) を使用してビット数を制限します。

これにより、最後の 32 ビットのみが考慮されるようになり、無限の増大が防止されます。 また、必要に応じて、潜在的な負の結果を 32 ビットの 2 の補数表現に変換することで処理します。

このアプローチは、Python 内で 32 ビット整数演算を効果的にシミュレートし、無制限の整数と負の数の問題を解決します。 if a > MAX_INT 条件は、結果が 32 ビットの符号付き整数の範囲内に収まることを保証します。 -12 と -8 を使用した例は、この補正がどのように機能して -20 という予想される結果を生成するかを示しています。

私の名前は Jaimin Bariya です。何か役立つものを見つけたら、「いいね！」とコメントを付けて、github jaimin-bariya をフォローしてください

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