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

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.

Comments