Add two numbers without using + or any arithmetic operators

Question

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

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 in Python - worked for me:
Is the recursion needed?

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

print(sum^carry)  # 16

@svs, good catch, the question is, whether recursive is needed? Thanks. :) — Lin Ma, Oct 05 '15 at 22:48
Possible duplicate of http://stackoverflow.com/q/4068033/5008845 — Miki, Oct 05 '15 at 23:38
Possible duplicate of [What is the best way to add two numbers without using the + operator?](http://stackoverflow.com/questions/365522/what-is-the-best-way-to-add-two-numbers-without-using-the-operator) — Gene, Oct 05 '15 at 23:49
@Miki, good catch. Thanks. Read through the thread you referred, but it never answers why carry part will decrease to zero. If you have any good thoughts, please share with us. :) — Lin Ma, Oct 06 '15 at 01:02
@Gene, good catch. Thanks. Read through the thread you referred, but it never answers why carry part will decrease to zero. If you have any good thoughts, please share with us. :) — Lin Ma, Oct 06 '15 at 01:03
@LinMa When you add binary numbers by hand and the carried ones ripple to the left, why do they always eventually stop rippling and go to zero? The answer is the same. — Gene, Oct 06 '15 at 01:56

score 4 · Accepted Answer · answered Oct 05 '15 at 22:54

4

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.

answered Oct 05 '15 at 22:54

Paul Boddington

37,127
10
65
116

Nice catch Paul, and why recursive could resolve this issue? I mean how do we prove recursively, carry will reduce to zero? – Lin Ma Oct 05 '15 at 22:59
@LinMa You can prove it works because the second argument you pass to the method always has an extra `0` at the right each time, due to the shift. Since the whole thing only involves a fixed number of bits (at most one more than the longest number you started with) you must eventually reach `b==0`. – Paul Boddington Oct 05 '15 at 23:03
1

@LinMa formally, you can prove that at each `add_no_arithm` the sum of the arguments is always the same ( `=a+b`) and `b`'s lat bits slowly become `0`s – sve Oct 05 '15 at 23:05
@svs, I understand the sum is the same, but confused how do you conclude b is decreasing. More insights are appreciated. :) – Lin Ma Oct 05 '15 at 23:07
1

@LinMa Yes a complete proof is a combination of mine and svs's comments. `b` is not decreasing. The number of zeros at the right is increasing, so it must hit zero. – Paul Boddington Oct 05 '15 at 23:09
1

@LinMa You can print out the values of `b` and see what you get. They're not decreasing. When you do `1 + 3` the `b` values are `3`, `2`, `4`, `0`. In binary these are `011`, `010`, `100`, `000`. These end in `0`, `1`, `2`, `3` zeros respectively. Since the number of `0`s at the right in step `i` is always at least `i - 1` (and the number of bits involved is fixed) you must reach zero. – Paul Boddington Oct 05 '15 at 23:13
@PaulBoddington, good catch, why number of zero must increasing? – Lin Ma Oct 06 '15 at 00:28
1

@LinMa Suppose `b` ends in `t` zeros. Then `a&b` will end in `t` zeros too because `0 & anything == 0`. It follows that `(a&b)<<1` must end in `t + 1` zeros because you already had `t` zeros and you shifted to the left creating one more. So the thing you pass in as the next `b` has more zeros at the right than the original `b`. Continuing in this way, `b` will eventually be `0`. – Paul Boddington Oct 06 '15 at 00:32
@PaulBoddington, smart catch! You provide there will be more and more trailing zeros and how do you know if the non-zero part is decreasing as well which finally makes b as zero value? Thanks. – Lin Ma Oct 06 '15 at 00:55

score 2 · Answer 2 · edited May 23 '18 at 05:41

2

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.

edited May 23 '18 at 05:41

DaveyDaveDave

9,821
11
64
77

answered May 23 '18 at 03:21

matias

21
1

rgettman · Answer 3 · 2015-10-05T23:03:44.353

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

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

edited Oct 05 '15 at 23:03

answered Oct 05 '15 at 22:49

rgettman

176,041
30
275
357

Thanks rgettman, could you point out a test case to show the issue in my code? – Lin Ma Oct 05 '15 at 22:51
1

8 and 8 happens to work because the carry bits (`16`) and the sum bits (`0`) would not carry when added, so `^` happens to work here. – rgettman Oct 05 '15 at 22:56
Nice catch rgettman, and why recursive could resolve this issue? I mean how do we prove recursively, carry will reduce to zero? – Lin Ma Oct 05 '15 at 22:59

score 0 · Answer 4 · edited Jul 07 '22 at 06:43

0

Will this work?

import java.util.*;

public class Solution {

    public static int sumOfTwoNumbers(int a, int b) {

        if (b<0){
            for(int j = 1; j<=-b;j++)
            --a;
        }
        
        if(b>0){
        
        for (int i = 1; i <= b; i++){
            a++;
        }
        }
            return a;
    }

edited Jul 07 '22 at 06:43

Procrastinator

2,526
30
27
36

answered Jul 02 '22 at 08:08

VeralevelCoder

1

This does not answer *Is recursion necessary to take care of carries*? – greybeard Jul 07 '22 at 07:13

Add two numbers without using + or any arithmetic operators

4 Answers4

Linked