CODEWITHSUNDEEP
c++calgorithmbit-manipulation
Vivek Sharma
Vivek Sharma

Reputation: 3814

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

How do I add two numbers without using ++ or + or any other arithmetic operator?

It was a question asked a long time ago in some campus interview. Anyway, 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 don't know, I could not find one. Does an answer exist?

Upvotes: 54

Views: 45458

Answers (22)

Ravindra
Ravindra

Reputation: 1

Come check this:

      ln(e^a*e^b)=a+b

Upvotes: 0

crispengari
crispengari

Reputation: 9321

Without using any operators adding two integers can be done in different ways as follows:

int sum_of_2 (int a, int b){
   int sum=0, carry=sum;
   sum =a^b;
   carry = (a&b)<<1;
   return (b==0)? a: sum_of_2(sum, carry);
}
// Or you can just do it in one line as follows:
int sum_of_2 (int a, int b){
   return (b==0)? a: sum_of_2(a^b, (a&b)<<1);
}
// OR you can use the while loop instead of recursion function as follows
int sum_of_2 (int a, int b){
    if(b==0){
       return a;
   }
   while(b!=0){
     int sum = a^b;
     int carry = (a&b)<<1;
     a= sum;
     b=carry;
  }
  return a;
}

Upvotes: 0

crispengari
crispengari

Reputation: 9321

You can use double negetive to add two integers for example:

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

Upvotes: 0

Kuuo
Kuuo

Reputation: 17

With given answers above, it can be done in single line code:

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

Upvotes: 0

Tikky
Tikky

Reputation: 37

The question asks how to add two numbers so I don't understand why all the solutions offers the addition of two integers? What if the two numbers were floats i.e. 2.3 + 1.8 are they also not considered numbers? Either the question needs to be revised or the answers.

For floats I believe the numbers should be broken into their components i.e. 2.3 = 2 + 0.3 then the 0.3 should be converted to an integer representation by multiplying with its exponent factor i.e 0.3 = 3 * 10^-1 do the same for the other number and then add the integer segment using one of the bit shift methods given as a solution above handling situations for carry over to the unit digits location i.e. 2.7 + 3.3 = 6.0 = 2+3+0.7+0.3 = 2 + 3 + 7x10^-1 + 3x10^-1 = 2 + 3 + 10^10^-1 (this can be handled as two separate additions 2+3=5 and then 5+1=6)

Upvotes: 0

Anshul garg
Anshul garg

Reputation: 233

Code to implement add,multiplication without using +,* operator; for subtraction pass 1's complement +1 of number to add function

#include<stdio.h>

unsigned int add(unsigned int x,unsigned int y)
{
         int carry=0;
    while (y != 0)
    {

        carry = x & y;  
        x = x ^ y; 
        y = carry << 1;
    }
    return x;
}
int multiply(int a,int b)
{
    int res=0;
    int i=0;
    int large= a>b ? a :b ;
    int small= a<b ? a :b ;
    for(i=0;i<small;i++)
    {
           res = add(large,res);                    
    }
    return res;
}
int main()
{
    printf("Sum :: %u,Multiply is :: %d",add(7,15),multiply(111,111));
    return 0;
}

Upvotes: 0

Tarik Kaya
Tarik Kaya

Reputation: 33

Here is a compact C solution. Sometimes recursion is more readable than loops.

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

Upvotes: 3

Gnanaprakash
Gnanaprakash

Reputation: 1

int add_without_arithmatic(int a, int b)
{
    int sum;
    char *p;
    p = (char *)a;
    sum = (int)&p[b];
    printf("\nSum : %d",sum);
}

Upvotes: -1

herohuyongtao
herohuyongtao

Reputation: 50657

This can be done recursively:

int add_without_arithm_recursively(int a, int b)
{
    if (b == 0) 
        return a;

    int sum = a ^ b; // add without carrying
    int carry = (a & b) << 1; // carry, but don’t add
    return add_without_arithm_recursively(sum, carry); // recurse
}

or iteratively:

int add_without_arithm_iteratively(int a, int b)
{
    int sum, carry;

    do 
    {
        sum = a ^ b; // add without carrying
        carry = (a & b) << 1; // carry, but don’t add

        a = sum;
        b = carry;
    } while (b != 0);

    return a;
}

Upvotes: 0

Nitesh Pratap Singh
Nitesh Pratap Singh

Reputation: 53

## to add or subtract without using '+' and '-' ## 
#include<stdio.h>
#include<conio.h>
#include<process.h>

void main()
{
    int sub,a,b,carry,temp,c,d;

    clrscr();

    printf("enter a and b:");
    scanf("%d%d",&a,&b);

    c=a;
    d=b;
    while(b)
    {
        carry=a&b;
        a=a^b;
        b=carry<<1;
    }
    printf("add(%d,%d):%d\n",c,d,a);

    temp=~d+1;  //take 2's complement of b and add it with a
    sub=c+temp;
    printf("diff(%d,%d):%d\n",c,d,temp);
    getch();
}

Upvotes: 1

Frederico
Frederico

Reputation: 101

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

Upvotes: 6

D P
D P

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

Upvotes: 1

intepid
intepid

Reputation: 211

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

Upvotes: 21

keraba
keraba

Reputation: 554

The following would work.

x - (-y)

Upvotes: 0

Indy9000
Indy9000

Reputation: 8851

All arithmetic operations decompose to bitwise operations to be implemented in electronics, using NAND, AND, OR, etc. gates.

Adder composition can be seen here.

Upvotes: 6

Jason C
Jason C

Reputation: 22067

This is something I have written a while ago for fun. It uses a two's complement 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;
}

Upvotes: 99

surya
surya

Reputation: 11

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

Upvotes: 1

rampion
rampion

Reputation: 89043

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 *) &sum;
  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;
}

Upvotes: 7

Tom Leys
Tom Leys

Reputation: 19029

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

Upvotes: 53

Fabio Ceconello
Fabio Ceconello

Reputation: 16039

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

Upvotes: 8

ChrisV
ChrisV

Reputation: 3423

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

Upvotes: 4

Samuel Carrijo
Samuel Carrijo

Reputation: 17919

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

Upvotes: 18

Related Questions