Méditations LeetCode : Somme de deux entiers

La description donnée pour la somme de deux entiers est très simple :

Étant donné deux entiers a et b, renvoie la somme des deux entiers sans utiliser les opérateurs et -.

Par exemple :

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

Ou :

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

Dans le tout dernier problème de cette série, nous terminerons en ajoutant deux entiers en utilisant la manipulation de bits au lieu de notre opérateur plus bien-aimé.

L'ajout de deux bits, dont l'un ne peut être que 1 ou 0, n'entraîne pas beaucoup de résultats variables.
Si nous ajoutons deux bits qui sont 1 et 0 (ou 0 et 1), le résultat sera 1. Si nous ajoutons deux bits 0, le résultat est 0. Si toutefois nous ajoutons deux 1 bits, nous avons un carry — ce qui signifie que nous devons écrire 0 dans la sortie, mais porter également un 1.

Par exemple, ajouter 2 et 3 donnera 5, et nous aurons une valeur de report lors de l'opération :

Sans penser à la valeur de report, le résultat que nous devons avoir après l'ajout de deux bits ressemble beaucoup à ce que nous aurions après une opération XOR. Si nous avons des bits différents (0 et 1, ou, 1 et 0), la sortie sera 1, sinon 0 (en ajoutant 0 et 0, ou , 1 et 1).

Ainsi, une opération XOR peut nous aider avec le résultat.

Et le transport ?

Nous avons une valeur de retenue uniquement lorsque les deux bits sont égaux à 1, ce qui ressemble à une opération ET.

Donc, une opération ET peut nous aider avec le report.

Notez également que la valeur de report est décalée vers la gauche, pour laquelle nous disposons également d'un opérateur de décalage à gauche pratique.

Ainsi, notre production et notre transport peuvent ressembler à ceci :

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

Nous pouvons continuer à modifier les deux valeurs que nous avons, et continuer jusqu'à ce qu'il ne nous reste plus aucune valeur de report. Nous pouvons modifier a pour être la sortie, et b pour être le report, et renvoyer a, qui contient la sortie finale à la fin.

Dans l'ensemble, la solution finale pourrait ressembler à ceci en 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;
}

Complexité temporelle et spatiale

a et b sont des valeurs constantes, et nous n'avons pas non plus besoin d'une structure de données supplémentaire dont la taille augmentera proportionnellement à l'entrée, donc nos complexités temporelles et spatiales seront constantes, $O(1)$O(1) .

Et c'est le dernier problème de la série LeetCode Meditations ! Nous terminerons par une conclusion dans le prochain article — d’ici là, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!