recursive add binary numbers

Question

i need following algorithm let say we have 5 //101 and 7 //111 numbers are arbitrary i need to add these numbers using the recursive method and at the same time using bitwise methods such that result should be

101
+
111
 110 0 

or 12 can anybody help me?

Answer 1

In pseudocode:

bint a, b, result;
// from back to front
bit carry = 0;
for(ix = 0; ix < sizeof(bint); ix++) {
    result[ix] = a[ix] ^ b[ix] ^ carry;
    carry = (carry & (a[ix] | b[ix])) | (a[ix] & b[ix]);
}

Answer 2

I believe something like this is what you're looking for:

static int add(int num1, int num2) {
    if (num1 == 0 && num2 == 0) {
        return 0;
    } else {
        return (num1 & 1) + (num2 & 1)
            + (add(num1 >>> 1, num2 >>> 1) << 1);
    }
}
public static void main(String[] args) {
    System.out.println(add(5, 7));   // prints "12"
    System.out.println(add(-3, -4)); // prints "-7"
}

This works by:

• adding the LSBs of num1 and num2
  • (num1 & 1) + (num2 & 1)
• and then recursively adding the rest of the bits, with proper shifting involved
  • add(num1 >>> 1, num2 >>> 1)
    • calls add with the numbers shifted to the right
    • >>> unsigned right shift is important here!
  • then shift the result back to the left << 1

We stop when both numbers are 0 (which will happen eventually after enough unsigned right shifts).

Carries will be automatically taken care of, and it works with negatives.

That said, this isn't really the best algorithm to pick to learn about recursion.

---

An absolutely no + solution

This solution is even more convoluted for learning purposes, but it is recursive, and it uses no +.

static int add(int num1, int num2, int carry) {
    if (num1 == 0 && num2 == 0) {
        return carry;
    } else {
        int lsb1 = (num1 & 1);
        int lsb2 = (num2 & 1);
        int thisBit = lsb1 ^ lsb2 ^ carry;
        int nextCarry =
            (lsb1 == 0 && lsb2 == 1 && carry == 1) ||
            (lsb1 == 1 && lsb2 == 0 && carry == 1) ||
            (lsb1 == 1 && lsb2 == 1 && carry == 0) ||
            (lsb1 == 1 && lsb2 == 1 && carry == 1)
            ? 1 : 0;
        return thisBit | (add(num1 >>> 1, num2 >>> 1, nextCarry) << 1);
    }
}
public static void main(String[] args) {
    System.out.println(add(5, 7, 0));   // prints "12"
    System.out.println(add(-3, -4, 0)); // prints "-7"
}

See also

• Wikipedia/Bitwise operation

Answer 3

There's always the classic "bitwise operations, recurse as little as possible":

int add (int a , int b)
{
   if (a&b) { /* At least one bit in common */
      return add(a^b, (a&b) << 1); /* Return addition of "no-carry" and "carry" bits */
   } else { /* No bits in common */
      return a|b;
   }
}

This will, I believe, lead to the smallest number of recursive calls.