adds two numbers without using + or any arithmetic

Question

Here is the reference implementation I got, the confusion is, I think there is no need for recursion. I post both code and my thought below here, any insights are appreciated. Please feel free to correct me if I am wrong.

BTW, for the two implementation differences, refer to line 5th. Thanks.

The question is, whether recursive is needed? Thanks.

Reference implementation,

1 int add_no_arithm(int a, int b) {
2 if (b == 0) return a;
3 int sum = a ^ b; // add without carrying
4 int carry = (a & b) << 1; // carry, but don’t add
5 return add_no_arithm(sum, carry); // recurse
6 }

Another implementation in my thought,

1 int add_no_arithm(int a, int b) {
2 if (b == 0) return a;
3 int sum = a ^ b; // add without carrying
4 int carry = (a & b) << 1; // carry, but don’t add
5 return sum ^ carry;
6 }

BTW, tried 8+8 works for me in Python,

a = 8
b = 8
sum = a ^ b
carry = (a & b) << 1

print sum^carry #16

thanks in advance, Lin

Answer 1

The bitwise XOR operator ^ is only equivalent to the addition operator + if there is no binary carrying in the sums. If there is binary carrying, then they are not equivalent. For example, 8 + 7 equals 8 ^ 7 equals 15, but 8 + 8 is 16 while 8 ^ 8 is 0.

Even if you have calculated the sum-no-carry and the carry-no-sum correctly, what if those two numbers, when added, would produce a binary carry? Then your ^ operator at the end would be incorrect. Without the + operator, the only option I see is to recurse, to add those numbers. This will recur until one of the numbers is 0.

Example:

add(no_arithm(18, 6))

1. sum = a^b 18 ^ 6 is 20.
2. carry = (a & b) << 1 18 & 6 is 2, bit shift left 1 is 4.
3. return sum ^ carry 20 ^ 4 is 16, incorrect (18 + 6 = 24).

Answer 2

The second approach doesn't work with 1 + 3.

Here are the steps

                 a == 01
                 b == 11
         sum = a^b == 10
carry = (a&b) << 1 == 10
       sum ^ carry == 00  // wrong answer! 1 + 3 == 4

Just doing ^ at the last step is not enough, as there may be a carry in that sum.

Answer 3

The question is, whether recursive is needed?

Yes, it is. You can see this for yourself by experimenting with other numbers, instead of just 8 + 8. For example, try 21 and 15, without recursion this gives output of 26.