SUMME VON ZWEI GANZZAHLEN – leetcode – Python

Kommen wir zum Kern der Addition zweier Ganzzahlen ohne Verwendung des Operators „“. Dies erfordert eine binäre Manipulation.

Wir werden dies wie bei einer regulären Addition angehen, aber mit Binärfunktion.

1. Beginnen Sie mit dem Hinzufügen von rechts, so wie Sie es normalerweise tun würden: 1 1, 0 1, 1 0, 0 0.
2. Da wir binär arbeiten, setzen Sie die Summe, wenn sie 2 erreicht, auf 0 zurück (1 1 = 10 binär, wird mit einem Übertrag zu 0).
3. Wiederholen Sie dies für alle Teile. Dadurch erhalten wir eine Teilsumme, wobei Überträge vorerst ignoriert werden.

Der bitweise XOR-Operator (^) verarbeitet diese Anfangssumme perfekt:

• Wenn die Bits gleich sind, ist das Ergebnis 0. Wenn sie unterschiedlich sind, ist das Ergebnis 1.

Dies entspricht unseren Bedürfnissen: 1 1 → 0 (mit Carry), 0 1 oder 1 0 → 1 und 0 0 → 0.

Lassen Sie uns nun die Überträger ansprechen. Der AND-Operator (&) hilft uns, sie zu finden:

• Wenn beide Bits 1 sind, ist das Ergebnis 1 (ein Übertrag).

Um den Übertrag nach links zu verschieben, verwenden wir eine Bitverschiebung nach links.

Algorithmus:

1. Initialisierung:
   • sum = a ^ b (XOR für Summe ohne Übertrag)
   • carry = (a & b) (UND für Tragen)
2. Iteration:
   • Wiederholen bis carry == 0:
     • a = sum
     • b = carry << 1 (Bitverschiebung nach links für Übertrag)

Beispiel (5 3):

1. Anfangswerte:
2. Iteration 1:
   • sum = 0101 ^ 0011 = 0110
   • carry = 0101 & 0011 = 0001
3. Iteration 2:
   • sum = 0110 ^ 0010 = 0100
   • carry = 0110 & 0010 = 0010
4. Iteration 3:
   • sum = 0100 ^ 00100 = 0000
   • carry = 0100 & 0100 = 0100
5. Iteration 4:
   • sum = 0000 ^ 1000 = 1000
   • carry = 0000 & 1000 = 0000

Der Übertrag ist 0, daher beträgt die Endsumme 1000 (8).

Pythons unbegrenzte Ganzzahlen verursachen Probleme mit negativen Zahlen. Die Linksverschiebung des Bits kann zu unendlichem Wachstum führen. Um dies zu beheben, müssen wir Ganzzahlen fester Größe (z. B. 32-Bit) simulieren.

Wir verwenden eine 32-Bit-Maske (0xFFFFFFFF), um die Anzahl der Bits zu begrenzen:

Dadurch wird sichergestellt, dass nur die letzten 32 Bit berücksichtigt werden, wodurch ein unendliches Wachstum verhindert wird. Wir behandeln auch mögliche negative Ergebnisse, indem wir sie bei Bedarf in ihre 32-Bit-Zweierkomplementdarstellung konvertieren.

Dieser Ansatz simuliert effektiv die 32-Bit-Ganzzahlarithmetik in Python und löst das Problem mit unbegrenzten Ganzzahlen und negativen Zahlen. Die if a > MAX_INT-Bedingung stellt sicher, dass das Ergebnis innerhalb des 32-Bit-Ganzzahlbereichs mit Vorzeichen bleibt. Das Beispiel mit -12 und -8 zeigt, wie diese Korrektur funktioniert, um das erwartete Ergebnis von -20 zu erzielen.

Mein Name ist Jaimin Bariya. Wenn Sie etwas Nützliches finden, liken und kommentieren Sie mich bitte und folgen Sie mir auf Github Jaimin-Bariya

Das obige ist der detaillierte Inhalt vonSUMME VON ZWEI GANZZAHLEN – leetcode – Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!