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

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

13.12.2008 18:13:51
Вы можете посмотреть на каждый бит, имея цикл, который >> пока не будет равен 0 (тогда вы обработаете все биты). Примените это к неподписанному сначала. Я выиграю приз?
Andrew Rollings 13.12.2008 18:29:06
Спасибо. Ваша награда - это знание, что вы помогли несчастной женщине.
user23126 13.12.2008 18:41:00
Если НЕТ операторов можно использовать, разве не исключаются побитовые операторы? Или просто + - * /?
Vilx- 13.12.2008 19:04:23
Абакус сделает это довольно хорошо, и он не использует электричество!
Steven A. Lowe 13.12.2008 20:04:42
я собираюсь использовать std :: plus <int> () (a, b)
Johannes Schaub - litb 13.12.2008 20:08:42
21 ОТВЕТ
РЕШЕНИЕ

В Си с побитовыми операторами:

#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) - сложение без переноса. (x & y)это вынос от каждого бита. (x & y) << 1это перенос в каждый бит.

Цикл продолжает добавлять переносы, пока перенос не станет нулевым для всех битов.

45
5.02.2018 01:29:25
Спасибо. Я боюсь спросить, но вычитание работает так же? Я прочитал, что я могу просто добавить два дополнения. Но когда я пытаюсь, скажем, вычесть 6-3 и превратить это в 6 + (- 3), используя дополнение к двум, я получаю бесконечный цикл в вышеприведенном алгоритме.
user23126 13.12.2008 18:39:28
add (6, -3) должен работать, вы можете поиграть с кодом здесь: codepad.org/iWSRSsUn
CMS 13.12.2008 18:43:24
Сдвиг влево отрицательного значения - неопределенное поведение, оно будет работать, как ожидается, на многих процессорах, но это не гарантировано, вы должны указать это в своем ответе. Кроме того, можете ли вы добавить \ n в ваш оператор printf? Помимо этого, хороший ответ.
Robert Gamble 13.12.2008 19:23:34
Я попытался преобразовать ваш алгоритм в Python ( codepad.org/pb8IuLnY ) и испытываю бесконечный цикл, когда передается отрицательное число (т.е. вычитание). Отличаются ли операторы Python от C?
user23126 13.12.2008 20:13:16
@ pomeranian.myopenid.com, это, скорее всего, связано с тем, как обрабатывается оператор левого сдвига в Python. Вместо достижения верхнего предела целочисленных битов и установки старшего бита, чтобы сделать число отрицательным, оно становится положительным длинным целым числом.
Lara Dougan 14.12.2008 18:24:53

Почему бы просто не увеличивать первое число так часто, как второе число?

2
13.12.2008 18:16:19
Инкремент - это просто добавление 1, поэтому оригинальная проблема все еще существует.
user23126 13.12.2008 18:17:07
не совсем, INC и ADD для разных опкодов на машинном языке;)
sindre j 13.12.2008 23:21:52

Чит. Вы можете отменить число и вычесть его из первого :)

В противном случае посмотрите, как работает двоичный сумматор. :)

РЕДАКТИРОВАТЬ: Ах, видел ваш комментарий после того, как я написал.

Подробности бинарного сложения здесь .

4
3.10.2017 01:09:17
Ссылка на двоичное дополнение не работает.
realPK 26.02.2017 07:25:30
Ссылка не работает, а остальная часть этого ответа недействительна; это должно быть удалено.
MD XF 3.10.2017 01:05:17
Ссылка исправлена, и ответ имеет отношение к контексту комментариев к исходному вопросу.
Andrew Rollings 3.10.2017 01:11:11

Причина, по которой ADD реализован в ассемблере как отдельная инструкция, а не как некоторая комбинация побитовых операций, заключается в том, что это трудно сделать. Вы должны беспокоиться о переносах с данного бита младшего разряда на следующий бит старшего разряда. Это то, что машины делают быстро на оборудовании, но даже с C вы не можете делать это быстро в программном обеспечении.

2
13.12.2008 18:32:16
Если вам удастся написать что-то в C, точно совпадающее с тем, что addделает аппаратная инструкция для всех входных данных, которые не вызывают неопределенного поведения, компилятор может использовать add. Сейчас мы находимся именно в такой ситуации, например popcnt, где единственный способ получить popcntинструкцию в чистом ISO C - это то, что компилятор распознает идиому и оптимизирует ваш цикл или последовательность битхаков в popcnt(и да, компиляторы это сделают). Или для поворота. stackoverflow.com/questions/776508/… .
Peter Cordes 3.10.2017 01:30:28
Очевидно, что наличие +оператора в C намного лучше, чем альтернатива, но основной проблемой будет не уродливый источник, а не медленный код. Хех, или foo = (int) &((char*)x)[y]использовать синтаксис индекса массива в качестве +оператора, но даже создание фиктивного указателя - это UB в C.
Peter Cordes 3.10.2017 01:32:06

Определите «лучшее». Вот версия Python:

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

+Список выполняет конкатенацию, а не дополнение.

5
3.09.2014 00:04:27
without using the + operator- не говорит without using the addition operator.
MD XF 26.09.2017 03:40:41

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

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

1
13.12.2008 18:46:38

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

Мой сумматор с неравномерным переносом работает как для целых чисел без знака, так и для целых чисел дополнения 2, если вы установили значение carry_in на 0, и целых чисел дополнения 1, если значение carry_in установлено на 1. Я также добавил флаги, чтобы отобразить переполнение или переполнение при сложении.

#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;
}
4
16.06.2018 12:53:41
К сожалению, оператор приращения (current_bit_position ++) требует добавления. Nitpicky, я знаю.
user23126 14.12.2008 16:50:38
@ pomeranian.myopenid.com да, это правда в этом случае. В аппаратном обеспечении есть отдельные логические элементы для каждого бита, и не используется цикл. Если этот цикл развернуть, вы можете использовать его без оператора ++.
Lara Dougan 14.12.2008 18:17:48
@ Лара: Да, развернись. Для 32 битов это будет 32 копии кода в цикле while. Это даст хороший аппаратный псевдокод и бонусное очко: он даже исполняемый! Аппаратные средства программирования следуют другим правилам, чем программные средства программирования, поэтому некоторые лучшие практики здесь не применимы ...
nalply 20.09.2011 11:39:39

Нет + верно?

int add(int a, int b) 
{
   return -(-a) - (-b);
}
10
13.12.2008 19:09:20
В комментариях к вопросу @ pomeranian.myopenid.com упоминается, что нельзя использовать арифметические операторы. Кроме того, было бы лучше использовать как - (-b), чтобы использовать вычитание в качестве операции замены.
Lara Dougan 13.12.2008 19:17:43
int add(int a, int b) {
   const char *c=0;
   return &(&c[a])[b];
}
23
25.09.2013 18:50:23
Я не совсем понял, как это работает, объяснение было бы здорово!
ffledgling 24.10.2013 23:21:05
@ffledgling Адрес cизначально равен 0. Адрес c[a]есть 0 + a = a. И адрес (&c[a])[b]есть a + b. Хороший чит, хотя все еще addиспользуется неявно.
Landys 3.09.2014 03:24:09
Обратите внимание, что вам нужно выделить массив, достаточно большой для наибольшей суммы. В противном случае создание указателя, который превышает границы массива, является неопределенным поведением .
Nayuki 3.07.2016 05:17:34
@ Наюки Это не массив, хотя.
wizzwizz4 16.03.2019 17:40:59

Функция add () в CMS прекрасна. Он не должен быть запятнан унарным отрицанием (небитовая операция, равносильная использованию сложения: -y == (~ y) +1). Итак, вот функция вычитания, использующая тот же только побитовый дизайн:

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;
}
5
22.02.2010 12:21:19
Это не дает ответа на вопрос, который требует сложения, а не вычитания.
MD XF 3.10.2017 01:04:54
@MD XF, я давал ответ на вопрос user23126, заданный в комментариях к ответу CMS . Я чувствовал, что ответ CMS на этот комментарий был неудовлетворительным, поскольку, как я объяснил выше, унарное отрицание равносильно использованию сложения. Нет способа поместить многострочный код в комментарий, поэтому я разместил его в качестве ответа. Также обратите внимание, что user23126 был исходным вопросом, задавшим вопрос - так что в некотором смысле это квалифицируется как ответ на вопрос.
Deadcode 8.12.2018 04:24:33
Кроме того, в то время как вопрос буквально спрашивает, как добавить два числа без использования оператора +, это тривиально возможно с a - (-b)другими заявленными. Поэтому ответ на вопрос, как это сделать без использования арифметических операторов, больше соответствует духу вопроса. Кроме того, пользователь 23126 прямо заявил, что оператор, который буквально +все еще не приемлем для использования, если он делает сложение, и ++очень похож на часть того, что отрицание делает за кадром.
Deadcode 8.12.2018 04:43:51

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

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

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);
}
0
16.06.2018 12:54:07

Я видел это как проблему 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)

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

0
16.06.2018 12:54:27

Коды 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)))))
-2
23.08.2015 07:29:21

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

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

public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
0
3.07.2016 05:00:23
Это тот же алгоритм, что принятый ответ, CMS.
Peter Cordes 6.07.2016 14:54:57
Я тоже так думал, но этот ответ не прошел все тесты, которые у меня были. Поэтому я предложил то, что в конечном итоге мне помогло, на другом языке программирования. Иногда люди сталкиваются с вопросами задолго до того, как они были опубликованы, и оказываются в несколько отличных от первоначального постера ситуациях. Я надеялся помочь кому-то в ситуации, похожей на ту, в которой я находился. Извините, если я вас обидел, и не стесняйтесь редактировать мой ответ, если вы чувствуете необходимость.
Jake Smith 6.07.2016 15:09:05
Я не присматривался; чем ваш алгоритм отличается от CMS? Ваша проверка конца рекурсии немного отличается. О, стоит ли проверять функции CMS while(x)вместо while(a)? В любом случае, если есть проблема с принятым ответом, вы должны прокомментировать это либо как комментарий, либо как часть текста этого ответа (или обоих). Во всяком случае, я не обижаюсь лично, я просто не думал, что этот ответ приносит большую пользу, так как то, что выглядит так же, уже было опубликовано.
Peter Cordes 6.07.2016 15:17:23
Там нет проблем с этим. Это просто не переводит на C # без дополнения. Я думаю, что ключ - это разница в языке. Я не думаю, что смещенные негативы ведут себя одинаково. На самом деле сдвинутые негативы не должны гарантировать правильного обращения с негативами в математическом смысле, потому что это не суть сдвига битов. Мой ответ специально ориентирован на разработчиков C # и скрывает комментарий, который включает в себя решение, которое отличается от других, может быть пропущено кем-то, кому может помочь этот ответ.
Jake Smith 6.07.2016 15:50:36

Это моя реализация на 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
0
16.06.2018 12:54:42

Решение Java с побитовыми операторами:

// 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;
}
4
26.02.2017 07:38:23
Удаление public staticиз обоих заставляет его работать и в Си. +1
MD XF 3.10.2017 01:08:19
Это именно тот ответ CMS (принятый в настоящее время), но со значимыми именами переменных и пояснением со встроенными комментариями, а не в тексте (ответ CMS отсутствовал в течение многих лет, но я добавил его в июле 2016 года). для объяснения этого ясно и правильно.
Peter Cordes 3.10.2017 01:24:20
На самом деле, было бы лучше сказать, что xorэто надстройка без переноса. Первый комментарий в рекурсивной версии говорит, что это сумма двух целых чисел , что неверно.
Peter Cordes 3.10.2017 01:27:05
Ответ @PeterCordes CMS включает основной метод и является допустимым кодом C. Я добавил только допустимые методы Java. Этот код протестирован на моей локальной машине и не копируется напрямую из другого источника. Спасибо за ваши комментарии, хотя.
realPK 3.10.2017 07:03:46

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

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
0
16.06.2018 12:55:06

В питоне используются побитовые операторы:

def sum_no_arithmetic_operators(x,y):
    while True:
        carry = x & y
        x = x ^ y
        y = carry << 1
        if y == 0:
            break
    return x
1
19.09.2018 00:03:39
это приведет к ошибкам для пар (-1,1), мы должны использовать маску, чтобы получить последние 32 бита stackoverflow.com/questions/365522/…
Prajilesh 13.10.2019 16:39:52

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

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

Решение на основе Go

func add(a int, b int) int {

for {
    carry := (a & b) << 1
    a = a ^ b
    b = carry 
    if b == 0 {
        break
    }
}

return a 

}

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

Например: если мы не используем маску, мы не получим результат для чисел (-1,1)

def add(a,b):   
    mask = 0xffffffff

    while b & mask:
        carry = a & b
        a = a ^ b
        b = carry << 1

    return (a & mask)
2
13.02.2020 15:04:34
Было бы проще просто return a&mask. Проверка, чтобы увидеть, не нужно ли вам просто усложнять код, и &стоит дешево.
Peter Cordes 13.10.2019 16:52:04