Why this code for addition(using bitwise operation) works in 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 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 1

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.

Answer 2

It relies on the fact that 1+1=10 (bitwise), i.e. "if an addition implies a carry bit, then sum current's digit column must be zero". Think of the "<<" operator as "carry the bits to the left" instead of thinking "multiply an int by 2"

Here's a prosaic description of the code.

carry = Ignore those bits that will produce carry bits (because their sum in the current "column"  will be 0), but collect the carry bits. 
a = Add those bits of a and b that won't produce a carry bit (i.e. use XOR)
b = Carry the carry bits one column left.

Answer 3

The variables b and carry are used for "carrying" extra digits. For example, in binary, 1+1 = 10, but 10 is a two-digit number. The 1 in 10 must be placed in the next digit to the left. That's what the while() loop does in your program. Wherever there are 1 digits in the same place (a & b), carry is set to the XOR of b (a ^ b). this gives each digit the value of 1 only if either a or b, but not both, has the value of 2. (When doing binary arithmetic, that's exactly what happens; 1+1 = 10, so since two 1s are being added together, the ones place is 0). After that, carry << 1 (carry*2 or carry shifted left by one) is assigned to b. The loop then repeats, using the new values of a and b until b is zero (which means carry is also zero).

Answer 4

Definately think of all numbers in here in binary system.

What You would usually like to find out in such code is a "loop invariant". In this case, You would like to see that a + b is constant after every iteration. Thus if b becomes 0 and we leave the loop, a must be equal to the sum of original a and b. The next step is to make sure that the loop will eventually terminate. We'll come back to this later, first let's figure out the invariant part, which in this case is using the equality:

a + b = (a ^ b) + 2 * (a & b)

where in the loop new a will be equal to old a ^ b and new b will be 2 * (a & b), which is the same as (a & b) << 1. That's the essense of Your problem - figuring out this equality. It's exactly how You do the addition.

I'll present two solutions. In both I'll use a simple fact that:

x + y = x ^ y

Whenever x and y have no common bits set.

The short way to see this formally is to note that:

a + b = a + b - 2(a & b) + 2(a & b)
= (a - (a & b)) + (b - (a & b)) + 2(a & b)
= (a - (a & b)) ^ (b - (a & b)) + 2(a & b)
= (a ^ (a & b)) ^ (b ^ (a & b)) + 2(a & b)
= a ^ b + 2(a & b)

The lengthy solution uses mathematical induction as follows (this might be considered an overkill by some, but in my option it's worth to know it):

First make sure it works with a and b both equal to zero (You might also try for one bit numbers which explain a lot of how this algorithm works). Never forget about this step when using mathematical induction.

Next, assume this works for n-1 bit numbers, we've got to show that it works for n bit ones too. Now write a = 2a' + a'' = 2a' ^ a'' and b = 2b' + b'' = 2b' ^ b'' where a'', b'' are in set {0, 1} (then 2a' and a'' have no common bits set!). Then:

(a ^ b) + 2(a & b) = (2a' ^ a'' ^ 2b' ^ b'') + 2((2a'' ^ a') & (2b'' ^ b')) =
(2a' ^ 2b') ^ (a'' ^ b'') + 2((2a'' & 2b'') ^ (a'' & b'')) = 
(2a' ^ 2b') + (a'' ^ b'') + 2((2a'' & 2b'') + (a'' & b'')) =
(2a' ^ 2b') + 2((2a'' & 2b'') + (a'' ^ b'') + (a'' & b'')) =
2a' + 2b' + a'' + b'' = a + b

Now the last thing to check is that this loop really terminates. to see this use the fact that at each step both a and b are non-negative, and that this remains true after each iteration.

Therefore we've got that b <= a + b. Next note that after n steps b has to be ending with n zeroes. Thus we cannot do more than log_2(a+b) steps since we'd get either b = 0 or b = k * 2*n >= 2*n > 2**log_2(a+b) = a+b contradicting assumption. Here ** denotes exponentiation of course.

In Java this algorithm would also work on negative integers. This is because of how negative integers are stored in Java and in most programming languages Here, the addition and subtraction of signed and unsigned numbers works identically on bits, therefore code that works for unsigned numbers will also work for signed.