Addition of natural numbers represented as double or double plus one

Question

Firstly, this is about a homework problem.

I've got a data structure representing a natural number as:

NUM = zero
      double(NUM)
      double_plus_one(NUM)

Eg, 6 = double(double_plus_one(double_plus_one(zero))). I've got the algorithm to convert a number into or from this representation fine. But now I'm expected to come up with algorithms to add and subtract two numbers in this format. I'm not seeing any patterns in how this can be done (and I can only assume that I'm not supposed to convert it to a regular number, add that, and convert back to this form).

Any advice?

Answer 1

Your format is just reversed binary. Every time you have double plus one it is a $1$ and every time you have double you have a $0$. The outer operator is the ones bit, the next one in is the twos, and so on. You need to write bitwise add, carry, subtract and borrow as operations on the text of your format.

Answer 2

You can define addition recursively through

1. n + zero = zero + n = n

2. double(n) + double(m) = double(n+m),

3. double_plus_one(n) + double_plus_one(m) = double((n+m) + 1)

4. double_plus_one(n) + double(m) = double_plus_one(n+m).

These aren't necessarily the most efficient, but they should work.