Quelle est la meilleure façon d'ajouter deux nombres sans utiliser l'opérateur +?
https://stackoverflow.com/questions/365522
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Un ami et moi allons revenir en arrière avec teasers et-cerveau je ne sais pas comment résoudre celui-ci. Mon hypothèse est qu'il est possible avec certains opérateurs au niveau du bit, mais pas sûr.
La solution
En C, avec les opérateurs binaires:
#include<stdio.h>
int add(int x, int y) {
int a, b;
do {
a = x & y;
b = x ^ y;
x = a << 1;
y = b;
} while (a);
return b;
}
int main( void ){
printf( "2 + 3 = %d", add(2,3));
return 0;
}
XOR (x ^ y) est plus sans retenue. Est de (x & y) chaque bit carry out. (x & y) << 1 est le à chaque bit de report.
La boucle continue d'ajouter la porte jusqu'à ce que la retenue est égale à zéro pour tous les bits.
Autres conseils
int add(int a, int b) {
const char *c=0;
return &(&c[a])[b];
}
Non + droit?
int add(int a, int b)
{
return -(-a) - (-b);
}
Fonction de add CMS () est magnifique. Il ne doit pas être sali par la négation unaire (une opération non-bit, équivaut à l'utilisation de plus: -y == (~ y) +1). Voici donc une fonction de soustraction en utilisant la même conception uniquement au niveau du bit:
int sub(int x, int y) {
unsigned a, b;
do {
a = ~x & y;
b = x ^ y;
x = b;
y = a << 1;
} while (a);
return b;
}
Définir "meilleure". Voici une version python:
len(range(x)+range(y))
Le effectue concaténation de + liste, non plus.
solution Java avec les opérateurs binaires:
// Recursive solution
public static int addR(int x, int y) {
if (y == 0) return x;
int sum = x ^ y; //SUM of two integer is X XOR Y
int carry = (x & y) << 1; //CARRY of two integer is X AND Y
return addR(sum, carry);
}
//Iterative solution
public static int addI(int x, int y) {
while (y != 0) {
int carry = (x & y); //CARRY is AND of two bits
x = x ^ y; //SUM of two bits is X XOR Y
y = carry << 1; //shifts carry to 1 bit to calculate sum
}
return x;
}
Note, ce serait un sommateur connu comme Report Retenue sommateur , qui fonctionne, mais ne fonctionne pas de manière optimale. La plupart des additionneurs binaires intégrés dans le matériel sont une forme d'addition rapide comme un sommateur report préanalyse .
Mon sommateur Report Retenue fonctionne à la fois des entiers non signés et complément de 2 si vous définissez carry_in à 0, et les entiers de complément de 1 si carry_in est réglé sur 1. Je attire également ajouté pour montrer underflow ou débordement sur l'addition.
#define BIT_LEN 32
#define ADD_OK 0
#define ADD_UNDERFLOW 1
#define ADD_OVERFLOW 2
int ripple_add(int a, int b, char carry_in, char* flags) {
int result = 0;
int current_bit_position = 0;
char a_bit = 0, b_bit = 0, result_bit = 0;
while ((a || b) && current_bit_position < BIT_LEN) {
a_bit = a & 1;
b_bit = b & 1;
result_bit = (a_bit ^ b_bit ^ carry_in);
result |= result_bit << current_bit_position++;
carry_in = (a_bit & b_bit) | (a_bit & carry_in) | (b_bit & carry_in);
a >>= 1;
b >>= 1;
}
if (current_bit_position < BIT_LEN) {
*flags = ADD_OK;
}
else if (a_bit & b_bit & ~result_bit) {
*flags = ADD_UNDERFLOW;
}
else if (~a_bit & ~b_bit & result_bit) {
*flags = ADD_OVERFLOW;
}
else {
*flags = ADD_OK;
}
return result;
}
Pourquoi ne pas simplement incremet le premier numéro le plus souvent, comme le deuxième numéro?
La raison ADD est implememted en assembleur comme une seule instruction, plutôt que comme une combinaison des opérations binaires, est qu'il est difficile de le faire. Vous avez à vous soucier de la porte d'un peu faible ordre donné au bit suivant d'ordre supérieur. Ce sont des choses que les machines font dans le matériel rapide, mais que même avec C, vous ne pouvez pas le faire dans le logiciel rapide.
L'ajout de deux entiers est pas difficile; il existe de nombreux exemples d'addition binaire en ligne.
Un problème plus difficile est nombres à virgule flottante! Il y a un exemple à http: //pages.cs .wisc.edu / ~ Smoler / x86text / lect.notes / arith.flpt.html
En python utilisant des opérateurs au niveau du bit:
def sum_no_arithmetic_operators(x,y):
while True:
carry = x & y
x = x ^ y
y = carry << 1
if y == 0:
break
return x
travaille sur moi-même problème en C # et ne pouvait pas obtenir tous les tests à passer. Je puis couru à travers cette .
Voici une implémentation en C # 6:
public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
Mise en œuvre de la même façon que nous pourrions faire plus binaire sur le papier.
int add(int x, int y)
{
int t1_set, t2_set;
int carry = 0;
int result = 0;
int mask = 0x1;
while (mask != 0) {
t1_set = x & mask;
t2_set = y & mask;
if (carry) {
if (!t1_set && !t2_set) {
carry = 0;
result |= mask;
} else if (t1_set && t2_set) {
result |= mask;
}
} else {
if ((t1_set && !t2_set) || (!t1_set && t2_set)) {
result |= mask;
} else if (t1_set && t2_set) {
carry = 1;
}
}
mask <<= 1;
}
return (result);
}
Amélioration de la vitesse serait inférieure ::
int add_better (int x, int y)
{
int b1_set, b2_set;
int mask = 0x1;
int result = 0;
int carry = 0;
while (mask != 0) {
b1_set = x & mask ? 1 : 0;
b2_set = y & mask ? 1 : 0;
if ( (b1_set ^ b2_set) ^ carry)
result |= mask;
carry = (b1_set & b2_set) | (b1_set & carry) | (b2_set & carry);
mask <<= 1;
}
return (result);
}
J'ai vu cela comme problème 18.1 dans l'interview de codage. Ma solution python:
def foo(a, b):
"""iterate through a and b, count iteration via a list, check len"""
x = []
for i in range(a):
x.append(a)
for i in range(b):
x.append(b)
print len(x)
Cette méthode utilise itération, de sorte que la complexité du temps n'est pas optimale. Je crois que la meilleure façon est de travailler à un niveau inférieur aux opérations de manipulation de bits.
Il est ma mise en œuvre sur Python. Il fonctionne bien, quand on sait le nombre d'octets (ou bits).
def summ(a, b):
#for 4 bytes(or 4*8 bits)
max_num = 0xFFFFFFFF
while a != 0:
a, b = ((a & b) << 1), (a ^ b)
if a > max_num:
b = (b&max_num)
break
return b
Vous pouvez le faire en utilisant décalage de bits et l'opération ET.
#include <stdio.h>
int main()
{
unsigned int x = 3, y = 1, sum, carry;
sum = x ^ y; // Ex - OR x and y
carry = x & y; // AND x and y
while (carry != 0) {
carry = carry << 1; // left shift the carry
x = sum; // initialize x as sum
y = carry; // initialize y as carry
sum = x ^ y; // sum is calculated
carry = x & y; /* carry is calculated, the loop condition is
evaluated and the process is repeated until
carry is equal to 0.
*/
}
printf("%d\n", sum); // the program will print 4
return 0;
}
La réponse la plus voté ne fonctionnera pas si les entrées sont de signe opposé. Toutefois suivant sera. J'ai triché à un endroit, mais seulement de garder un peu le code propre. Toutes les suggestions pour l'amélioration bienvenue
def add(x, y):
if (x >= 0 and y >= 0) or (x < 0 and y < 0):
return _add(x, y)
else:
return __add(x, y)
def _add(x, y):
if y == 0:
return x
else:
return _add((x ^ y), ((x & y) << 1))
def __add(x, y):
if x < 0 < y:
x = _add(~x, 1)
if x > y:
diff = -sub(x, y)
else:
diff = sub(y, x)
return diff
elif y < 0 < x:
y = _add(~y, 1)
if y > x:
diff = -sub(y, x)
else:
diff = sub(y, x)
return diff
else:
raise ValueError("Invalid Input")
def sub(x, y):
if y > x:
raise ValueError('y must be less than x')
while y > 0:
b = ~x & y
x ^= y
y = b << 1
return x
Voici une solution portable ternaire et récursive d'une ligne.
int add(int x, int y) {
return y == 0 ? x : add(x ^ y, (x & y) << 1);
}
codes Python: (1)
add = lambda a,b : -(-a)-(-b)
utilisez la fonction lambda avec '-' opérateur
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))
