low-level - formato - twig document

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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

No + ¿verdad?

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

Answer 5

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

Mi sumadora 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 suma.

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

Answer 6

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 suma: -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;
}

Answer 7

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

Answer 8

Puede hacerlo utilizando el cambio de bit 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;
}

Answer 9

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

Answer 10

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

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

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

Answer 11

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

Answer 12

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

Answer 13

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;

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

En su defecto, busca cómo funciona un sumador binario. :)

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

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

Answer 18

En C, con operadores bit a bit:

#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 suma 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.