I found this code online. But, I am unable to get the logic behind the following code:
public static int add(int a, int b) {
if (b == 0) return a;
int sum = a ^ b; // add without carrying
System.out.println("sum is : "+sum);
int carry = (a & b) << 1; // carry, but don’t add
return add(sum, carry); // recurse
}
Let's look at an example (using 8 bits for simplicity)
a = 10010110
b = 00111101
a^b is the xor, which gives 1 for places where there is a 1 in one number and 0 in the other. In our example:
a^b = 10101011
Since 0 + 0 = 0, 0 + 1 = 1 and 1 + 0 = 1, the only columns left to deal with are the ones that have a 1 in both of the numbers. In our example, a^b is short by whatever the answer to
00010100
+ 00010100
is. In binary, 1 + 1 = 10, so the answer to the above sum is
00101000
or (a & b) << 1. Therefore the sum of a^b and (a & b) << 1 is the same as a + b.
So, assuming the process is guaranteed to terminate, the answer will be correct. But the process will terminate because each time we call sum recursively the second parameter has at least one more 0 at the end, due to the bit shift <<. Therefore, we are guaranteed to eventually end up with the second argument consisting entirely of 0s, so that the line if (b == 0) return a; can end the process and give us an answer.
We are adding converting the integers to bits and using bitwise operators .
EXOR i.e ^ : 0 ^0 and 1 ^1 =0 , other cases give 1.
AND i.e & 1^1 =1 , ..other cases give 0.
<< or left shift . i.e shift left and append a 0 bit : 0010 becomes 0100
eg.
add(2,3)
2= 0010
3=0011
exor both : to get initial sum : 0001
carry : a &b = 0010
Left shift by 1 bit : 0100 i.e 4
add(1,4)
exor both : 0001 0100 and u get 0101 i.e 5
carry = 0000 <<1 i.e 0000 ..
since carry is 0 , it stops addition and returns previous sum
Consider, as an example, 5+7:
5 = 101 (Base 2)
7 = 111 (Base 2)
Now consider adding the two (base 2) digits:
0+0 = 0 = 0 carry 0
1+0 = 1 = 1 carry 0
0+1 = 1 = 1 carry 0
1+1 = 10 = 0 carry 1
The sum (without carrying) of A+B is A^B and the carry is A&B; and when you carry a number it is shifted one digit to the left (hence (A&B)<<1).
So:
5 = 101 (Base 2)
7 = 111 (Base 2)
5^7 = 010 (sum without carrying)
5&7 = 101 (the carry shifted left)
Then we can recurse to add the carry:
A = 010
B = 1010
A^B = 1000 (sum without carrying)
A&B = 0010 (the carry shifted left)
Then we can recurse again as we still have more to carry:
A' = 1000
B' = 100 (without the leading zeros)
A'^B' = 1100 (sum without carrying)
A'&B' = 0000 (the carry shifted left)
Now there is nothing to carry - so we can stop and the answer is 1100 (base 2) = 12 (base 10).
The algorithm is just implementing decimal addition as (longhand) binary addition using the ors to add and the bitshifted ands to find the carry and will recurse until there is nothing more to carry (which will always occur as the bitshift appends another zero to the carry each time so with each recursion at least one more bit will not generate a carry value each time).
This is the table for addition:
+ 0 1
-- --
0 | 0 1
1 | 1 10
▲
If you ignore the carry bit ▲ you'll see that it's the same as the XOR table:
^ 0 1
-- --
0 | 0 1
1 | 1 0
So if you combine two numbers with bitwise XOR you get bit-by-bit addition without carry.
Now, what is the carry? It's a bit that's only there when both inputs are 1.
You can get that with AND:
& 0 1
-- --
0 | 0 0
1 | 0 1
But it needs to be added to the sum after being shifted one position to the left, because it's "carried" over, hence the (a & b) << 1
So you can compute the addition without carry and the carry itself. How do you add them together without using addition? Simple! By recursing on this very definition of addition!
See @pbabcdefp's answer on why the recursion always terminates.
