Add unsigned numbers without using '+' or '++'

Question

I need to add 2 unsigned numbers 'a' and 'b' .

I found the following Code , using bit operations

unsigned int add (unsigned int a,unsigned int b)
{
    unsigned int carry, sum;
    if (b == 0)
    {
        return a;
    }

    sum = a ^ b; // xor takes sum
    carry = a & b; // collect carry;
    carry = carry << 1;
    return ( add (sum, carry) );
}

I cant figure out how is this code adding two numbers .

Any help/direction people .

Answer 1

The logic: The code implements a series of half-adders and propagates the carry from one of them to the next one via recursion. See the dry-run for an example on how this works.

Consider these two values a=0011 and b=0101. In base 10 they are a=3 and b=5 respectively.

Now, a^b=0110 (1 only when a single bit is 1) while a&b=0001 (1 only when both bits is one, the single case where you can have a carry).

Then, you need to move the carry to the next bit, that's why you have the <<1 operation, making carry=0010.

Now you need to add 0110 and 0010 using the above algorithm. This will turn into adding 0100 and 0100. Which will result in adding 0000 with 1000 which will result in adding 1000 with 0000 which will end via the base case (b == 0).

In tabular form:

|   a  |   b  | a^b  |  a&b | carry|
------------------------------------
| 0011 | 0101 | 0110 | 0001 | 0010 |
| 0110 | 0010 | 0100 | 0010 | 0100 |
| 0100 | 0100 | 0000 | 0100 | 1000 |
| 0000 | 1000 | 1000 | 0000 | 0000 |
| 1000 | 0000 | ---- | ---- | ---- |

Last row is base case.