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

Question

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

Это был вопрос, заданный давным-давно в одном из интервью в кампусе. Во всяком случае, сегодня кто-то задал вопрос, касающийся некоторых битовых манипуляций, и в ответах было упомянуто прекрасное выражение Стэнфордский бит тиддлинг Я провел некоторое время, изучая его, и подумал, что на самом деле может быть ответ на вопрос. Я не знаю, я не мог найти один. Ответ существует?

Answer 1

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

#include <stdlib.h> /* atoi() */
#include <stdio.h>  /* (f)printf */
#include <assert.h> /* assert() */

int add(int x, int y) {
    int carry = 0;
    int result = 0;
    int i;

    for(i = 0; i < 32; ++i) {
        int a = (x >> i) & 1;
        int b = (y >> i) & 1;
        result |= ((a ^ b) ^ carry) << i;
        carry = (a & b) | (b & carry) | (carry & a);
    }

    return result;
}

int negate(int x) {
    return add(~x, 1);
}

int subtract(int x, int y) {
    return add(x, negate(y));
}

int is_even(int n) {
    return !(n & 1);
}

int divide_by_two(int n) {
    return n >> 1;
}

int multiply_by_two(int n) {
    return n << 1;
}

int multiply(int x, int y) {
    int result = 0;

    if(x < 0 && y < 0) {
        return multiply(negate(x), negate(y));
    }

    if(x >= 0 && y < 0) {
        return multiply(y, x);
    }

    while(y > 0) {
        if(is_even(y)) {
            x = multiply_by_two(x);
            y = divide_by_two(y);
        } else {
            result = add(result, x);
            y = add(y, -1);
        }
    }

    return result;
}

int main(int argc, char **argv) {
    int from = -100, to = 100;
    int i, j;

    for(i = from; i <= to; ++i) {
        assert(0 - i == negate(i));
        assert(((i % 2) == 0) == is_even(i));
        assert(i * 2 == multiply_by_two(i));
        if(is_even(i)) {
            assert(i / 2 == divide_by_two(i));
        }
    }

    for(i = from; i <= to; ++i) {
        for(j = from; j <= to; ++j) {
            assert(i + j == add(i, j));
            assert(i - j == subtract(i, j));
            assert(i * j == multiply(i, j));
        }
    }

    return 0;
}

Answer 2

Или, вместо побитового подхода Джейсона, вы можете вычислять много битов параллельно - это должно выполняться намного быстрее с большими числами. На каждом шаге определите часть переноса и часть, которая является суммой. Вы пытаетесь добавить перенос к сумме, что может снова вызвать перенос - отсюда и цикл.

>>> def add(a, b):
    while a != 0:
        #      v carry portion| v sum portion
        a, b = ((a & b) << 1),  (a ^ b)
        print b, a
    return b

когда вы добавляете 1 и 3, для обоих чисел установлен 1 бит, поэтому сумма этих 1 + 1 переносится. Следующим шагом вы добавите 2 к 2, и это приведет к правильной сумме четыре. Это вызывает выход

>>> add(1,3)
2 2
4 0
4

Или более сложный пример

>>> add(45, 291)
66 270
4 332
8 328
16 320
336

Edit: Для удобства работы со знаковыми номерами необходимо ввести верхний предел для a и b

.

>>> def add(a, b):
    while a != 0:
        #      v carry portion| v sum portion
        a, b = ((a & b) << 1),  (a ^ b)
        a &= 0xFFFFFFFF
        b &= 0xFFFFFFFF
        print b, a
    return b

Попробуйте на

add(-1, 1)

чтобы увидеть, как один бит проходит через весь диапазон и переполняется за 32 итерации

4294967294 2
4294967292 4
4294967288 8
...
4294901760 65536
...
2147483648 2147483648
0 0
0L

Answer 3

int Add(int a, int b)
{
    while (b)
    {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

Answer 4

Вы можете преобразовать схему сумматора в алгоритм. Они делают только побитовые операции =)

Answer 5

Ну, реализовать эквивалент с помощью логических операторов довольно просто: вы делаете побитовую сумму (которая является XOR), с переносом (который является AND). Как это:

int sum(int value1, int value2)
{
    int result = 0;
    int carry = 0;
    for (int mask = 1; mask != 0; mask <<= 1)
    {
        int bit1 = value1 & mask;
        int bit2 = value2 & mask;
        result |= mask & (carry ^ bit1 ^ bit2);
        carry = ((bit1 & bit2) | (bit1 & carry) | (bit2 & carry)) << 1;
    }
    return result;
}

Answer 6

Вы уже получили пару битовых ответов на манипуляции. Вот что-то другое.

В С, arr[ind] == *(arr + ind). Это позволяет нам делать немного запутанные (но законные) вещи, такие как int arr = { 3, 1, 4, 5 }; int val = 0[arr];.

Таким образом, мы можем определить пользовательскую функцию добавления (без явного использования арифметического оператора) следующим образом:

unsigned int add(unsigned int const a, unsigned int const b)
{
    /* this works b/c sizeof(char) == 1, by definition */
    char * const aPtr = (char *)a;
    return (int) &(aPtr[b]);
}

С другой стороны, если мы хотим избежать этого трюка, и если с помощью арифметического оператора они включают |, & и ^ (поэтому прямое управление битами не допускается), мы можем сделать это с помощью таблицы поиска:

typedef unsigned char byte;

const byte lut_add_mod_256[256][256] = { 
  { 0, 1, 2, /*...*/, 255 },
  { 1, 2, /*...*/, 255, 0 },
  { 2, /*...*/, 255, 0, 1 },
  /*...*/
  { 254, 255, 0, 1, /*...*/, 253 },
  { 255, 0, 1, /*...*/, 253, 254 },
}; 

const byte lut_add_carry_256[256][256] = {
  { 0, 0, 0, /*...*/, 0 },
  { 0, 0, /*...*/, 0, 1 },
  { 0, /*...*/, 0, 1, 1 },
  /*...*/
  { 0, 0, 1, /*...*/, 1 },
  { 0, 1, 1, /*...*/, 1 },
};

void add_byte(byte const a, byte const b, byte * const sum, byte * const carry)
{
  *sum = lut_add_mod_256[a][b];
  *carry = lut_add_carry_256[a][b];
}

unsigned int add(unsigned int a, unsigned int b)
{
  unsigned int sum;
  unsigned int carry;
  byte * const aBytes = (byte *) &a;
  byte * const bBytes = (byte *) &b;
  byte * const sumBytes = (byte *) ∑
  byte * const carryBytes = (byte *) &carry;

  byte const test[4] = { 0x12, 0x34, 0x56, 0x78 };
  byte BYTE_0, BYTE_1, BYTE_2, BYTE_3;

  /* figure out endian-ness */
  if (0x12345678 == *(unsigned int *)test)
  {
    BYTE_0 = 3;
    BYTE_1 = 2;
    BYTE_2 = 1;
    BYTE_3 = 0;
  }
  else 
  {
    BYTE_0 = 0;
    BYTE_1 = 1;
    BYTE_2 = 2;
    BYTE_3 = 3;
  }


  /* assume 4 bytes to the unsigned int */
  add_byte(aBytes[BYTE_0], bBytes[BYTE_0], &sumBytes[BYTE_0], &carryBytes[BYTE_0]);

  add_byte(aBytes[BYTE_1], bBytes[BYTE_1], &sumBytes[BYTE_1], &carryBytes[BYTE_1]);
  if (carryBytes[BYTE_0] == 1)
  {
    if (sumBytes[BYTE_1] == 255)
    {
      sumBytes[BYTE_1] = 0;
      carryBytes[BYTE_1] = 1;
    }
    else
    {
      add_byte(sumBytes[BYTE_1], 1, &sumBytes[BYTE_1], &carryBytes[BYTE_0]);
    }
  }

  add_byte(aBytes[BYTE_2], bBytes[BYTE_2], &sumBytes[BYTE_2], &carryBytes[BYTE_2]);
  if (carryBytes[BYTE_1] == 1)
  {
    if (sumBytes[BYTE_2] == 255)
    {
      sumBytes[BYTE_2] = 0;
      carryBytes[BYTE_2] = 1;
    }
    else
    {
      add_byte(sumBytes[BYTE_2], 1, &sumBytes[BYTE_2], &carryBytes[BYTE_1]);
    }
  }

  add_byte(aBytes[BYTE_3], bBytes[BYTE_3], &sumBytes[BYTE_3], &carryBytes[BYTE_3]);
  if (carryBytes[BYTE_2] == 1)
  {
    if (sumBytes[BYTE_3] == 255)
    {
      sumBytes[BYTE_3] = 0;
      carryBytes[BYTE_3] = 1;
    }
    else
    {
      add_byte(sumBytes[BYTE_3], 1, &sumBytes[BYTE_3], &carryBytes[BYTE_2]);
    }
  }

  return sum;
}

Answer 7

Все арифметические операции разлагаются на побитовые операции, которые должны быть реализованы в электронике с использованием вентилей NAND, AND, OR и т. Д.

Состав сумматора можно посмотреть здесь .

Answer 8

Для чисел без знака используйте тот же алгоритм сложения, который вы выучили в первом классе, но для базы 2 вместо базы 10. Пример для 3 + 2 (база 10), т.е. 11 + 10 в базе 2:

   1         ‹--- carry bit
   0 1 1     ‹--- first operand (3)
 + 0 1 0     ‹--- second operand (2)
 -------
   1 0 1     ‹--- total sum (calculated in three steps)

Answer 9

Если вы чувствуете себя комедийным, всегда есть этот невероятно ужасный подход для добавления двух (относительно небольших) целых чисел без знака. В вашем коде нет арифметических операторов.

В C #:

static uint JokeAdder(uint a, uint b)
{
    string result = string.Format(string.Format("{{0,{0}}}{{1,{1}}}", a, b), null, null);
    return result.Length;
}

В C, используя stdio (замените snprintf на _snprintf на компиляторах Microsoft):

#include <stdio.h>
unsigned int JokeAdder(unsigned int a, unsigned int b)
{
    return snprintf(NULL, 0, "%*.*s%*.*s", a, a, "", b, b, "");
}

Answer 10

Вот компактное решение C. Иногда рекурсия более читабельна, чем циклы.

int add(int a, int b){
    if (b == 0) return a;
    return add(a ^ b, (a & b) << 1);
}