Add two numbers without using + and - operators

Question

Suppose you have two numbers, both signed integers, and you want to sum them but can't use your language's conventional + and - operators. How would you do that?

Based on http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml

Answer 1

#include <stdio.h>

int main()
{
    int n1=5,n2=55,i=0;
    int sum = 0;
    int carry = 0;

    while (n1 > 0 || n2 > 0) 
    {
        int b1 = n1 % 2;
        int b2 = n2 % 2;

        int sumBits = b1 ^ b2 ^ carry;
        sum = sum | ( sumBits << i);
        i++;
        carry = (b1 & b2) | (b1 & carry) | (b2 & carry);
        n1 /= 2;
        n2 /= 2;
    }   
    sum = sum | ( carry << i );

    printf("%d",sum);

    return 0;
}

Answer 2

I realize that this might not be the most elegant solution to the problem, but I figured out a way to do this using the len(list) function as a substitute for the addition operator.

'''
Addition without operators: This program obtains two integers from the user
and then adds them together without using operators. This is one of the 'hard'
questions from 'Cracking the Coding Interview' by 
'''

print('Welcome to addition without a plus sign!')
item1 = int(input('Please enter the first number: '))
item2 = int(input('Please eneter the second number: '))

item1_list = []
item2_list = []
total = 0
total_list = []
marker = 'x'
placeholder = 'placeholder'

while len(item1_list) < item1:
    item1_list.append(marker)

while len(item2_list) < item2:
    item2_list.append(marker)

item1_list.insert(1, placeholder)
item1_list.insert(1, placeholder)

for item in range(1, len(item1_list)):
    total_list.append(item1_list.pop())

for item in range(1, len(item2_list)):
    total_list.append(item2_list.pop())

total = len(total_list)

print('The sum of', item1, 'and', item2, 'is', total)

Answer 3

Cringe. Nobody builds an adder from 1-bit adders anymore.

do {
  sum = a ^ b;
  carry = a & b;
  a = sum;
  b = carry << 1;
} while (b);
return sum;

Of course, arithmetic here is assumed to be unsigned modulo 2ⁿ or twos-complement. It's only guaranteed to work in C if you convert to unsigned, perform the calculation unsigned, and then convert back to signed.

Answer 4

Not very creative, I know, but in Python:

sum([a,b])

Answer 5

Here's something different than what's been posted already. Use the facts that:

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

So:

log (e^(a + b)) = log(e^a * e^b) = a + b (if the log is base e)

So just find log(e^a * e^b).

Of course this is just theoretical, in practice this is going to be inefficient and most likely inexact too.

Answer 6

In Common Lisp:

(defun esoteric-sum (a b)
  (let ((and (logand a b)))
    (if (zerop and)
        ;; No carrying necessary.
        (logior a b)
        ;; Combine the partial sum with the carried bits again.
        (esoteric-sum (logxor a b) (ash and 1)))))

That's taking the bitwise-and of the numbers, which figures out which bits need to carry, and, if there are no bits that require shifting, returns the bitwise-or of the operands. Otherwise, it shifts the carried bits one to the left and combines them again with the bitwise-exclusive-or of the numbers, which sums all the bits that don't need to carry, until no more carrying is necessary.

Here's an iterative alternative to the recursive form above:

(defun esoteric-sum-iterative (a b)
  (loop for first = a then (logxor first second)
        for second = b then (ash and 1)
        for and = (logand first second)
        until (zerop and)
        finally (return (logior first second))))

Note that the function needs another concession to overcome Common Lisp's reluctance to employ fixed-width two's complement arithmetic—normally an immeasurable asset—but I'd rather not cloud the form of the function with that accidental complexity.

If you need more detail on why that works, please ask a more detailed question to probe the topic.

Answer 7

Simple example in Python, complete with a simple test:

NUM_BITS = 32

def adder(a, b, carry):
    sum = a ^ b ^ carry
    carry = (a & b) | (carry & (a ^ b))
    #print "%d + %d = %d (carry %d)" % (a, b, sum, carry)
    return sum, carry

def add_two_numbers(a, b):
    carry = 0
    result = 0
    for n in range(NUM_BITS):
        mask = 1 << n
        bit_a = (a & mask) >> n
        bit_b = (b & mask) >> n
        sum, carry = adder(bit_a, bit_b, carry)
        result = result | (sum << n)
    return result


if __name__ == '__main__':
    assert add_two_numbers(2, 3) == 5
    assert add_two_numbers(57, 23) == 80

    for a in range(10):
        for b in range(10):
            result = add_two_numbers(a, b)
            print "%d + %d == %d" % (a, b, result)
            assert result == a + b

Answer 8

Not mine, but cute

int a = 42;
int b = 17;
char *ptr = (char*)a;
int result = (int)&ptr[b];

Answer 9

This version has a restriction on the number range:

(((int64_t)a << 32) | ((int64_t)b & INT64_C(0xFFFFFFFF)) % 0xFFFFFFFF

This also counts under the "letter of the rules" category.

Answer 10

If we're obeying the letter of the rules:

a += b;

Otherwise http://www.geekinterview.com/question_details/67647 has a pretty complete list.

Answer 11

Using bitwise logic:

int sum = 0;
int carry = 0;

while (n1 > 0 || n2 > 0) {
  int b1 = n1 % 2;
  int b2 = n2 % 2;

  int sumBits = b1 ^ b2 ^ carry;
  sum = (sum << 1) | sumBits;
  carry = (b1 & b2) | (b1 & carry) | (b2 & carry);
  n1 /= 2;
  n2 /= 2;
}

Answer 12

Using Bitwise operations just like Adder Circuits

Answer 13

Since ++ and -- are not + and - operators:

int add(int lhs, int rhs) {
    if (lhs < 0)
        while (lhs++) --rhs;
    else
        while (lhs--) ++rhs;
    return rhs;
}