SOMME DE DEUX ENTIERS - leetcode - Python

Allons au cœur de l'addition de deux entiers sans utiliser l'opérateur ' '. Cela nécessite une manipulation binaire.

Nous aborderons cela comme une addition régulière, mais en utilisant le binaire.

1. Commencez à ajouter à partir de la droite, comme vous le feriez normalement : 1 1, 0 1, 1 0, 0 0.
2. Puisque nous travaillons en binaire, si la somme atteint 2, remettez-la à 0 (1 1 = 10 binaire, devient 0 avec un report).
3. Répétez cette opération pour tous les bits. Cela nous donne une somme partielle, en ignorant les carrys pour l'instant.

L'opérateur bit à bit XOR (^) gère parfaitement cette somme initiale :

• Si les bits sont identiques, le résultat est 0. S'ils sont différents, le résultat est 1.

Cela correspond à nos besoins : 1 1 → 0 (avec un report), 0 1 ou 1 0 → 1 et 0 0 → 0.

Maintenant, abordons les portages. L'opérateur AND (&) nous aide à les trouver :

• Si les deux bits sont à 1, le résultat est 1 (un report).

Pour décaler le report vers la gauche, nous utiliserons un bit shift vers la gauche.

Algorithme :

1. Initialisation :
   • sum = a ^ b (XOR pour somme sans report)
   • carry = (a & b) (ET pour le transport)
2. Itération :
   • Répéter jusqu'à carry == 0 :
     • a = sum
     • b = carry << 1 (décalage de bit gauche pour le report)

Exemple (5 3) :

1. Valeurs initiales :
2. Itération 1 :
   • sum = 0101 ^ 0011 = 0110
   • carry = 0101 & 0011 = 0001
3. Itération 2 :
   • sum = 0110 ^ 0010 = 0100
   • carry = 0110 & 0010 = 0010
4. Itération 3 :
   • sum = 0100 ^ 00100 = 0000
   • carry = 0100 & 0100 = 0100
5. Itération 4 :
   • sum = 0000 ^ 1000 = 1000
   • carry = 0000 & 1000 = 0000

Le report est de 0, donc la somme finale est de 1000 (8).

Les entiers illimités de Python provoquent des problèmes avec les nombres négatifs. Le décalage de bit vers la gauche peut conduire à une croissance infinie. Pour résoudre ce problème, nous devons simuler des entiers de taille fixe (par exemple, 32 bits).

Nous utiliserons un masque de 32 bits (0xFFFFFFFF) pour limiter le nombre de bits :

Cela garantit que seuls les 32 derniers bits sont pris en compte, empêchant ainsi une croissance infinie. Nous traitons également les résultats négatifs potentiels en les convertissant en leur représentation en complément à deux 32 bits si nécessaire.

Cette approche simule efficacement l'arithmétique des entiers 32 bits dans Python, résolvant ainsi le problème des entiers illimités et des nombres négatifs. La condition if a > MAX_INT garantit que le résultat reste dans la plage d'entiers signés de 32 bits. L'exemple avec -12 et -8 montre comment cette correction fonctionne pour produire le résultat attendu de -20.

Je m'appelle Jaimin Bariya, si vous trouvez quelque chose d'utile, aimez et commentez, et suivez-moi sur github jaimin-bariya

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!