¿Cuál es la mejor manera de añadir dos números sin utilizar el operador +?
https://stackoverflow.com/questions/365522
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Un amigo y yo nos vamos hacia atrás y adelante con acertijos y no tengo idea de cómo resolver este caso. Mi suposición es que es posible con algunos operadores bit a bit, pero no estoy seguro.
Solución
En C, con operadores de bits:
#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) es además sin acarreo. (x & y) es el acarreo de salida de cada bit. (x & y) << 1 es el equipaje de mano en el que cada bit.
El bucle mantiene añadiendo la lleva hasta el acarreo es cero para todos los bits.
Otros consejos
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);
}
complemento del CMS () es hermosa. No debe ser manchado por negación unaria (una operación no bit a bit, equivalente a la utilización de adición: == -y (~ y) 1). Así que aquí hay una función resta utilizando el mismo diseño bit a bit de sólo:
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;
}
Definir "mejor". Aquí hay una versión de Python:
len(range(x)+range(y))
La lista + realiza la concatenación, no adición.
solución de Java con operadores de bits:
// 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;
}
trucos. Se podía negar el número y restarlo de la primera:)
De no ser así, buscar cómo funciona un sumador binario. :)
EDIT: Ah, vio su comentario después de que he publicado
.Los detalles de la suma binaria son aquí .
Tenga en cuenta, esto sería para una sumadora conocido como ondulación de transportar víbora, que funciona, pero no lleva a cabo de manera óptima. La mayoría de los sumadores binarios incorporados en el hardware son una forma de serpiente rápida tales como llevar a-look-ahead víbora .
Mi ondulación acarreo del sumador funciona tanto sin firmar y de 2 enteros complemento si se establece carry_in a 0 y enteros en complemento a 1 si carry_in se establece en 1. También añadió banderas para mostrar desbordara por arriba o en la adición.
#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 incremet el primer número tan a menudo, ya que el segundo número?
La razón ADD se implememted en ensamblador como una sola instrucción, en lugar de como una combinación de operaciones bit a bit, es que es difícil de hacer. Usted tiene que preocuparse de los acarreos de un bit de orden dada al siguiente bit de orden superior. Esto es algo que las máquinas pueden hacer en el hardware rápido, pero que aún con C, no se puede hacer en software rápido.
Adición de dos números enteros no es tan difícil; hay muchos ejemplos de adición binaria en línea.
Un problema más difícil es flotante números de punto! Hay un ejemplo en http: //pages.cs .wisc.edu / ~ Smoler / x86text / lect.notes / arith.flpt.html
En Python usando operadores de bits:
def sum_no_arithmetic_operators(x,y):
while True:
carry = x & y
x = x ^ y
y = carry << 1
if y == 0:
break
return x
Implementado en misma manera que podríamos hacer la suma binaria en el 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);
}
La mejora de la velocidad estaría por 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 un problema 18.1 en la entrevista de codificación. Mi solución pitón:
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 utiliza iteración, por lo que la complejidad del tiempo no es óptimo. Creo que la mejor forma de hacerlo es trabajar a un nivel inferior con operaciones bit a bit.
Es mi aplicación en Python. Funciona bien, cuando sabemos el número 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 bit-desplazamiento y la operación AND.
#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 respuesta más votada no funcionará si las entradas son de signo opuesto. El embargo de siguiente. He hecho trampa en un solo lugar, pero sólo para mantener el código un poco limpio. Cualquier sugerencia o modificación de 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
Esto es una solución de una línea ternaria y recursivo portátil.
int add(int x, int y) {
return y == 0 ? x : add(x ^ y, (x & y) << 1);
}
Los códigos de Python: (1)
add = lambda a,b : -(-a)-(-b)
Uso de la función lambda con '-' operador
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))
