Ajout d'un entier binaire sans utiliser + ou -

Question

Ajoutez deux entiers sans utiliser + ou -.

Ceci est ma solution.

class Solution { 
public: 
    int getSum(int a, int b) { 
     int temp=a & b; 
     a=a^b; 
     while (temp>0){ 
      b=temp<<1; 
      temp=a & b; 
      a=a^b; 
     } 
     return a; 
    } 
}; 

Mais il ne fonctionne pas sur les cas où a = -12, b = -8.

---

Comparer côte à côte avec la solution de travail d'un autre peuple, il a:

class Solution { 
public: 
    int getSum(int a, int b) { 
     int sum = a; 

     while (b != 0) 
     { 
      sum = a^b;//calculate sum of a and b without thinking the carry 
      b = (a & b) << 1;//calculate the carry 
      a = sum;//add sum(without carry) and carry 
     } 

     return sum; 
    } 
}; 

qui est bascially même. Pourquoi ma solution ne fonctionne pas?

Answer 1

Strictement parlant votre solution et celle avec laquelle vous comparez sont incorrectes, à moins que vous ne fassiez des suppositions spécifiques sur la représentation des types intégraux signed. La raison pour laquelle vous êtes différent est l'ordre des opérations.

L'explication est écrite dans la norme C elle-même. Par exemple, à partir de la norme ISO 2011 C (ISO/IEC 9899: 2011) Section 6.5, paragraphe 4.

Certains opérateurs (l'opérateur unaire ~, et les opérateurs binaires < <, >>, &,^, et |, décrits collectivement comme des opérateurs au niveau du bit) doivent avoir des opérandes qui ont un type intégral. Ces opérateurs renvoient des valeurs qui dépendent des représentations internes des entiers et ont donc des aspects définis par l'implémentation et non définis pour les types signés.

Ces préoccupations frappé la maison avec des expressions comme a & b si l'a ou b est négatif .... et votre exemple a les deux. a << 1 donne une préoccupation similaire si a est négatif.

Pour éliminer votre problème, vous devez utiliser les valeurs unsigned (pour lesquelles les opérateurs bit à bit ont un comportement bien défini). Si vous devez gérer des valeurs négatives, il suffit de suivre le signe d'une autre manière (par exemple, une autre variable de type bool).

En pratique, les opérations sur les bits fonctionnent comme prévu pour les types signed avec une représentation à deux-complément. Le problème de s'en remettre à cela, cependant, est qu'une implémentation n'est pas requise pour utiliser une telle représentation.