How to add two numbers without using ++ or + or another arithmetic operator.

Question

How to add two numbers without using ++ or + or any other arithmetic operator. It was a question asked a long time ago in some campus-interview. Anyways today someone asked a question regarding some bit-manipulations, and in answers a beautiful quide *stanford Bit Twiddling * was referred. I spend some time studying it, and thought that there actually might be an answer to the question. I dont know, i could not find one. Does anyone has any hints.

Answer 1

You could transform an adder circuit into an algorithm. They only do bitwise operations =)

Answer 2

All arithmetic operations decompose to bitwise operations to be implemented in electronics, using NAND,AND,OR etc. gates. Adder composition can be seen here

Answer 3

For unsigned numbers, use the same addition algorithm as you learned in first class, but for base 2 instead of base 10. Example for 3+2 (base 10), i.e 11+1 in base 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 4

If you're feeling comedic, there's always this spectacularly awful approach for adding two (relatively small) unsigned integers. No arithmetic operators anywhere in your code.

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

In C, using stdio (replace snprintf with _snprintf on Microsoft compilers):

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

Answer 5

This is something I had written a while ago for fun. It uses a twos-complment representation and implements addition using repeated shifts with a carry bit, implementing other operators mostly in terms of addition.

#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 6

Wouldn't this work ?

x - (-y)

Answer 7

Or, rather than Jason's bitwise approach, you can calculate many bits in parallel - this should run much faster with large numbers. In each step figure out the carry part and the part that is sum. You attempt to add the carry to the sum, which could cause carry again - hence the loop.

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

when you add 1 and 3, both numbers have the 1 bit set, so the sum of that 1+1 carries. The next step you add 2 to 2 and that carries into the correct sum four. That causes an exit

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

Or a more complex example

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

Edit: For it to work easily on signed numbers you need to introduce an upper limit on a and 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

Try it on

add(-1, 1)

to see a single bit carry up through the entire range and overflow over 32 iterations

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

Answer 8

Well, to implement an equivalent with boolean operators is quite simple: you do a bit-by-bit sum (which is an XOR), with carry (which is an AND). Like this:

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 9

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

Answer 10

You've already gotten a couple bit manipulation answers. Here's something different.

In C, arr[ind] == *(arr + ind). This lets us do slightly confusing (but legal) things like int arr = { 3, 1, 4, 5 }; int val = 0[arr];.

So we can define a custom add function (without explicit use of an arithmetic operator) thusly:

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

Alternately, if we want to avoid this trick, and if by arithmetic operator they include |, &, and ^ (so direct bit manipulation is not allowed) , we can do it via lookup table:

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 11

short int ripple_adder(short int a, short int b) { short int i,c,s,ai,bi;

c=s=0;

for(i=0;i<16;i++) { ai = a & 1; bi = b & 1;

s |= (((ai ^ bi)^c) << i); c = (ai & bi) | (c & (ai ^ bi));

a >>= 1; b >>= 1; }

s |= (c << i);

return s; }

Answer 12

include

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