Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).
Sum of two bits can be obtained by performing XOR (^) of the two bits. Carry bit can be obtained by performing AND (&) of two bits.
Above is simple Half Adder logic that can be used to add 2 single bits. We can extend this logic for integers. If x and y don’t have set bits at same position(s), then bitwise XOR (^) of x and y gives the sum of x and y. To incorporate common set bits also, bitwise AND (&) is used. Bitwise AND of x and y gives all carry bits. We calculate (x & y) << 1 and add it to x ^ y to get the required result.
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0Aint%20Add(int%20x%2C%20int%20y)%0A%7B%0A%20%20%20%20%2F%2F%20Iterate%20till%20there%20is%20no%20carry%20%20%0A%20%20%20%20while%20(y%20!%3D%200)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20carry%20now%20contains%20common%20set%20bits%20of%20x%20and%20y%0A%20%20%20%20%20%20%20%20int%20carry%20%3D%20x%20%26%20y%3B%20%20%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Sum%20of%20bits%20of%20x%20and%20y%20where%20at%20least%20one%20of%20the%20bits%20is%20not%20set%0A%20%20%20%20%20%20%20%20x%20%3D%20x%20%5E%20y%3B%20%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Carry%20is%20shifted%20by%20one%20so%20that%20adding%20it%20to%20x%20gives%20the%20required%20sum%0A%20%20%20%20%20%20%20%20y%20%3D%20carry%20%3C%3C%201%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20x%3B%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20printf(%22%25d%22%2C%20Add(15%2C%2032))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]
Following is recursive implementation for the same approach.
int Add(int x, int y)
{
if (y == 0)
return x;
else
return Add( x ^ y, (x & y) << 1);
}
[ad type=”banner”]