Add two numbers without using + and - operators

Suppose you have two numbers, both signed integers, and you want to sum the开发者_Go百科m 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

Not mine, but cute

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

Using Bitwise operations just like Adder Circuits

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.

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

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

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

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.

If we're obeying the letter of the rules:

a += b;

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

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.

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

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.

Not very creative, I know, but in Python:

sum([a,b])

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)

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