LeetCode-Meditationen: Summe zweier Ganzzahlen

Die Beschreibung für die Summe zweier Ganzzahlen ist sehr einfach:

Gegeben sind zwei ganze Zahlen a und b. Geben Sie die Summe der beiden ganzen Zahlen zurück, ohne die Operatoren und -.

zu verwenden

Zum Beispiel:

Input: a = 1, b = 2
Output: 3

Oder:

Input: a = 2, b = 3
Output: 5

---

In der allerletzten Aufgabe dieser Serie schließen wir mit der Addition zweier Ganzzahlen mithilfe der Bitmanipulation anstelle unseres beliebten Plusoperators ab.

Das Addieren von zwei Bits, von denen eines nur 1 oder 0 sein kann, führt nicht zu vielen unterschiedlichen Ergebnissen.
Wenn wir zwei Bits hinzufügen, die 1 und 0 sind (oder 0 und 1), ist das Ergebnis 1. Wenn wir zwei 0-Bits hinzufügen, ist das Ergebnis 0. Wenn wir jedoch zwei 1 addieren Bits haben wir einen Übertrag – was bedeutet, dass wir 0 in die Ausgabe schreiben müssen, aber auch einen tragen 1.

Zum Beispiel ergibt die Addition von 2 und 3 5, und wir haben während der Operation einen Übertragswert:

Ohne über den Übertragswert nachzudenken, ähnelt die Ausgabe, die wir nach dem Hinzufügen von zwei Bits haben müssen, stark der Ausgabe, die wir nach einer XOR-Operation hätten. Wenn wir unterschiedliche Bits haben (0 und 1, oder 1 und 0), ist die Ausgabe 1, andernfalls 0 (Hinzufügen von 0 und 0, oder , 1 und 1).

Eine XOR-Operation kann uns also bei der Ausgabe helfen.

Was ist mit dem Tragen?

Wir haben nur dann einen Übertragswert, wenn beide Bits 1 sind – was wie eine UND-Operation aussieht.

Eine UND-Verknüpfung kann uns also beim Übertragen helfen.

Beachten Sie außerdem, dass der Übertragswert nach links verschoben wird, wofür wir auch einen praktischen Linksverschiebungsoperator haben.

Unsere Ausgabe und unser Übertrag können also so aussehen:

let output = a ^ b;
let carry = (a & b) << 1;

Wir können die beiden Werte, die wir haben, weiter ändern und so lange weitermachen, bis wir keine Übertragswerte mehr haben. Wir können a als Ausgabe und b als Übertrag ändern und a zurückgeben, das am Ende die endgültige Ausgabe enthält.

Insgesamt könnte die endgültige Lösung in TypeScript so aussehen:

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;
}

Zeit- und Raumkomplexität

Sowohl a als auch b sind konstante Werte, und wir benötigen auch keine zusätzliche Datenstruktur, deren Größe proportional zur Eingabe wächst, sodass sowohl unsere zeitliche als auch unsere räumliche Komplexität konstant bleiben, $O(1)$O(1) .

---

Und das ist das letzte Problem der LeetCode Meditations-Reihe! Wir schließen es mit einem Fazit im nächsten Beitrag ab – bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Summe zweier Ganzzahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!