Summe von zwei Ganzzahlen ohne Verwendung von "+" -Operator in Python

Question

Benötigen Sie Hilfe zum Verständnis der Python-Lösungen von leetcode 371. "Summe von zwei Ganzzahlen". Ich fand https://discuss.leetcode.com/topic/49900/python-solution/2 ist die am meisten gewählte Python-Lösung, aber ich habe ein Problem, es zu verstehen.

• Wie verstehen Sie die Verwendung von "% MASK" und warum "MASK = 0x100000000"?
• Wie zu verstehen "~ ((% MIN_INT)^MAX_INT)"?
• Wenn die Summe über MAX_INT hinausgeht, schreien die Funktionen negativen Wert (zum Beispiel getSum (2147483647,2) = -2147483647), ist das nicht falsch?

---

class Solution(object): 

    def getSum(self, a, b): 
     """ 
     :type a: int 
     :type b: int 
     :rtype: int 
     """ 
     MAX_INT = 0x7FFFFFFF 
     MIN_INT = 0x80000000 
     MASK = 0x100000000 
     while b: 
      a, b = (a^b) % MASK, ((a & b) << 1) % MASK 
     return a if a <= MAX_INT else ~((a % MIN_INT)^MAX_INT) 

Answer 1

ist die MASK, MAX_INT und MIN_INT für eine Sekunde lassen außer Acht lassen.

Warum funktioniert dieses bitweise schwarze Magie-Zeug?

Der Grund, warum die Berechnung funktioniert, ist, weil (a^b) die Bits a und b "summiert". Erinnern Sie sich, dass bitweise xor 1 ist, wenn sich die Bits unterscheiden, und 0, wenn die Bits identisch sind. Beispielsweise (wobei D decimal und B binär), 20D == 10100B und 9D = 1001B:

10100 
    1001 
----- 
11101 

und 11101B == 29D.

Aber wenn Sie einen Fall mit einem tragen haben, funktioniert es nicht so gut. Betrachten Sie zum Beispiel das Hinzufügen (bitweise xor) 20D und 20D.

10100 
10100 
----- 
00000 

Oops. 20 + 20 ist sicherlich nicht gleich 0. Geben Sie den (a & b) << 1 Begriff ein. Dieser Begriff repräsentiert das "Tragen" für jede Position. Bei der nächsten Iteration der while-Schleife fügen wir den Übertrag von der vorherigen Schleife hinzu. Also, wenn wir mit dem Beispiel gehen wir vorher hatten, erhalten wir:

# First iteration (a is 20, b is 20) 
10100^10100 == 00000 # makes a 0 
(10100 & 10100) << 1 == 101000 # makes b 40 

# Second iteration: 
000000^101000 == 101000 # Makes a 40 
(000000 & 101000) << 1 == 0000000 # Makes b 0 

Jetzt b 0, sind wir fertig, so zurückkehren a. Dieser Algorithmus funktioniert im Allgemeinen nicht nur für die spezifischen Fälle, die ich skizziert habe. Der Nachweis der Korrektheit bleibt dem Leser als Übung;)

Was machen die Masken?

Alle Masken tun, ist sicherzustellen, dass der Wert eine ganze Zahl ist, weil Ihr Code sogar Kommentare hat die besagt, dass a, b, und der Rückgabetyp des Typs sind int. Also, da die maximal mögliche int (32 Bits) ist 2147483647. Also, wenn Sie 2 zu diesem Wert hinzufügen, wie Sie in Ihrem Beispiel, der int überläuft und Sie erhalten einen negativen Wert. Sie müssen dies in Python erzwingen, weil es diese Grenze nicht respektiert, die andere stark typisierte Sprachen wie Java und C++ definiert haben. Beachten Sie Folgendes:

def get_sum(a, b): 
    while b: 
     a, b = (a^b), (a & b) << 1 
    return a 

Dies ist die Version von getSum ohne die Masken.

print get_sum(2147483647, 2) 

Ausgänge

2147483649 

während

print Solution().getSum(2147483647, 2) 

Ausgänge

-2147483647 

aufgrund der Überlauf.

Die Moral der Geschichte ist die Implementierung ist korrekt, wenn Sie den Typ int definieren, um nur 32 Bits darzustellen.