¿Cuál es la mejor manera de agregar dos números sin usar el operador +?

Un amigo y yo vamos y viniendo con acertijos y no tengo idea de cómo resolverlo. Mi suposición es que es posible con algunos operadores bit a bit, pero no estoy seguro.

En C, con operadores bit a bit:

#include 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 ) es sum sin acarreo. (x & y) es el resultado de cada bit. (x & y) << 1 es el acarreo de cada bit.

El ciclo sigue agregando los acarreos hasta que el acarreo sea cero para todos los bits.

 int add(int a, int b) { const char *c=0; return &(&c[a])[b]; } 

No + ¿verdad?

 int add(int a, int b) { return -(-a) - (-b); } 

Definir “lo mejor” Aquí hay una versión de Python:

 len(range(x)+range(y)) 

El + realiza concatenación de lista, no sum.

La función add () de CMS es hermosa. No debe ser mancillado por la negación unaria (una operación no bit a bit, equivalente a usar la sum: -y == (~ y) +1). Así que aquí hay una función de resta que usa el mismo diseño solo bit a 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; } 

Solución Java con operadores bit a bit:

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

Engañar. Podrías negar el número y restarlo del primero 🙂

En su defecto, busca cómo funciona un sumdor binario. 🙂

EDITAR: Ah, viste tu comentario después de haber publicado.

Los detalles de la adición binaria están aquí .

Tenga en cuenta que esto sería para un sumdor conocido como ripple-carry adder , que funciona, pero no funciona de manera óptima. La mayoría de los sumdores binarios integrados en el hardware son una forma de sumdor rápido, como un sumdor de llevar-mirar hacia adelante .

Mi sumdora de ripple-carry funciona tanto para enteros sin complemento como para complementos de 2 si defines carry_in en 0 y complementos de complemento en 1 si carry_in está establecido en 1. También agregué flags para mostrar underflow o overflow en la sum.

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

¿Por qué no boost el primer número tan a menudo como el segundo número?

La razón por la que ADD se implementa en el ensamblador como una instrucción única, en lugar de como una combinación de operaciones bit a bit, es que es difícil de hacer. Debe preocuparse por los acarreos desde un bit de orden baja hasta el siguiente bit de orden superior. Esto es algo que las máquinas hacen en hardware rápido, pero que incluso con C, no se puede hacer en un software rápido.

Agregar dos enteros no es tan difícil; hay muchos ejemplos de adición binaria en línea.

¡Un problema más desafiante es el número de coma flotante! Hay un ejemplo en http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html

Estaba trabajando en este problema yo mismo en C # y no pude obtener todos los casos de prueba para pasar. Entonces me encontré con esto .

Aquí hay una implementación en C # 6:

 public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a; 

Implementado de la misma manera que podríamos hacer una adición binaria en papel.

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

Mejorado para la velocidad estaría debajo ::

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

Vi esto como el problema 18.1 en la entrevista de encoding. Mi solución 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) 

Este método usa iteración, por lo que la complejidad del tiempo no es óptima. Creo que la mejor manera es trabajar en un nivel inferior con operaciones a nivel de bit.

Es mi implementación en Python. Funciona bien, cuando sabemos la cantidad de bytes (o 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 

Puede hacerlo utilizando el cambio de bit y la operación AND.

 #include  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 respuesta más votada no funcionará si las entradas son de signo opuesto. Lo siguiente sin embargo lo hará. He hecho trampa en un lugar, pero solo para mantener el código un poco limpio. Cualquier sugerencia de mejora bienvenida

 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 

Códigos Python: (1)

 add = lambda a,b : -(-a)-(-b) 

use la función lambda con el operador ‘-‘

(2)

 add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b))))) 
Intereting Posts