Как лучше всего добавить два числа без использования оператора +?

Question

Мы с другом возвращаемся назад и вперед с дразнилками, и я понятия не имею, как решить этот вопрос. Я предполагаю, что это возможно с некоторыми побитовыми операторами, но не уверен.

Answer 1

В питоне с использованием побитовых операторов:

def sum_no_arithmetic_operators(x,y):
    while True:
        carry = x & y
        x = x ^ y
        y = carry << 1
        if y == 0:
            break
    return x

Answer 2

Добавление двух целых чисел не так сложно; Есть много примеров бинарного сложения онлайн.

Более сложной проблемой являются числа с плавающей запятой! Вот пример на http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html

Answer 3

Ответ с наибольшим количеством голосов не будет работать, если входные данные имеют противоположный знак. Следующее однако будет. Я обманул в одном месте, но только чтобы сохранить код немного чистым. Любые предложения по улучшению приветствуются

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 4

Это моя реализация на Python. Это хорошо работает, когда мы знаем количество байтов (или бит).

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 5

Я сам работал над этой проблемой в C # и не смог пройти все тесты. Затем я наткнулся на это .

Вот реализация в C # 6:

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

Answer 6

Коды Python: (1)

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

использовать лямбда-функцию с оператором '-'

(2)

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

Answer 7

Я видел это как проблему 18.1 в интервью по кодированию. Мое решение на 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)

Этот метод использует итерацию, поэтому временная сложность не является оптимальной. Я считаю, что лучший способ - работать на более низком уровне с побитовыми операциями.

Answer 8

Реализовано так же, как мы могли бы сделать двоичное сложение на бумаге.

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

Улучшено для скорости будет ниже ::

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 9

Вот переносное однострочное троичное и рекурсивное решение.

int add(int x, int y) {
    return y == 0 ? x : add(x ^ y, (x & y) << 1);
}

Answer 10

Вы можете сделать это, используя сдвиг битов и операцию 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;
}