Sunny - 4 days ago 5
Java Question

# Why this code for addition(using bitwise operation) works in java

``````public int add(int a, int b){
while (b != 0){
int carry = (a & b) ;

a = a ^ b;

b = carry << 1;
}
return a;
}
``````

This is the code to calculate sum of two integers using bitwise operation.

If i calculate manually/programmatically, i see it works for every integer.
But i am not able to figure out any relation between intermediate value of
`a`
and
`carry`
.
and why carry is multiplied by 2 to assign to
`b`
?

PS: I found the one answer here
Bitwise Multiply and Add in Java
but this is for multiplication and not for addition.

First recall addition in primary school. e.g. 26 + 147 = 173. You start by 6+7=13, so you put 3 in the sum, and carry the one, and so forth - that is: you add two digits and carry a one if necessary.

``````carry:  1
a:      26
b:     147
-----------------
sum:   173
``````

The code does almost the same thing on binary numbers, but with a small tweak. Instead of taking one digit position at a time, it takes all in one go. Instead of including the carry from position i-1 in i (i.e. including 1 when adding 2 and 4), the code add all caries in a second iteration. So what it does is: `026+147 = 163 + 010 = 173 + 000`

For the binary numbers a=6=00110 and b=7=00111 you get

First you find the carries; that is all positions where both `a` and `b` has its bit set: `int carry = (a & b) ;`

Then id does the addition of digits, ignoring the carry, and stores it in `a`: `a = a ^ b;` This will respond to `6+7=3` in the example.

The last part shifts the carry to the next digit position, i.e. ensuring the 1-carry in the example is "moved" from the 1's to the 10's: `carry << 1;`

The while loop continues as long as there are carries that has not been included in the sum.