Sunny - 4 days ago 5

Java Question

`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`

`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.

Answer

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.

Source (Stackoverflow)

Comments