3

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

Lin Ma
  • 9,059
  • 29
  • 91
  • 166
  • 1
    what is the question? – sve Oct 05 '15 at 22:47
  • @svs, good catch, the question is, whether recursive is needed? Thanks. :) – Lin Ma Oct 05 '15 at 22:48
  • 1
    Possible duplicate of http://stackoverflow.com/q/4068033/5008845 – Miki Oct 05 '15 at 23:38
  • 1
    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
  • 1
    @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

3 Answers3

3

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.

Paul Boddington
  • 36,189
  • 10
  • 61
  • 114
  • 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
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.

DaveyDaveDave
  • 8,579
  • 11
  • 62
  • 73
matias
  • 21
  • 1
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).
rgettman
  • 172,063
  • 28
  • 262
  • 343
  • 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