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

Improve this question
6
  • Do you have any knowledge about the bit-wise addition? Commented Jun 27, 2013 at 11:38
  • 1
    The carry of a digit is added to the next digit, of course. This algorithm just carries out "addition as you know it from school" but a bit mixed up instead of carefully digit by digit - it does an addition without carries first (the xor), then adds the caries separately (again in the same way) until there are no more carries (so it adds the carries-generated-by-adding-carries, then the carries generated by that addition and so forth). This must terminate because carries only go "to the left" - so at least one bit is "fixed" after every iteration. Commented Jun 27, 2013 at 11:39
  • @smsnheck yes, i have, what is your point anyway? Commented Jun 27, 2013 at 11:54
  • @harold thanks a lot..actually i was finding it hard to believe how carry over next bit works in binary as it is not happening bit by bit from starting.. Commented Jun 27, 2013 at 11:54
  • @Sunny i wanted to explain how it works and wanted to know on what level you are. So it would have been easier to me to explain (and not write stuff you already know). Commented Jun 27, 2013 at 12:44

5 Answers 5

Reset to default
20

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

thanks for the answer...can you think of any case where while loop will run 3 times or more? i guess carry will always be settled in 1 or 2 times..
@Sunny if you add 1 to 0xFFFFFFFF (aka -1), it will step all the way through bit by bit in 32 steps (or some number sufficiently close to 32, I often make off-by-one errors)
oh thanks both..picture is very much clear in my mind now..now i can move to complex parts with satisfaction..:)
How is 7 in binary = 00101? Shouldnt it be 00111
@Tobber cool.. but I still dont understand it right. If we just take an example 6 + 7. In bitwise op, 6 & 7 = 6 so how come the carry variable gets initialized to 6?
|
2

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

Improve this answer

Comments

2

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.

Improve this answer

Comments

1

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.
Improve this answer

Comments

0

Yes, like many answers here, it works like rudimentary school math for adding two numbers. But in Binary way.

  1. What does a&b give us? It gives ones at all places which will trigger a carry forward. For examples, adding 1101 and 0101, only the 0th and 2nd position from right triggers carry forward. So only that will be 0101 which is obtained by a&b. But when doing carry in normal addition, we move one position left. That is why in 3rd statement of code, the carry is moved one position left. So carry becomes 01010.

  2. What does a^b give us? Any bit that is not counted above is included. In the above step, we included impact of 0th and 2nd bit. Now we need to include other bits which have 1. That will be 3rd from right giving is 1000. The value assigned to a becomes 1000.

Now all we have to do is add these again, using the same steps above.

  1. Adding 01010 and 01000. Only common one is 3rd position, so a&b gives 01000 and carry eventually becomes 10000 after the shift.

  2. To count the remaining bits, a^b becomes 00010 and gets assigned to a.

Loop continues. As carry above is not zero yet.

  1. Adding 10000 and 00010. No common 1's bit. So carry becomes 0.

  2. a^b becomes 10010 and gets assigned to a.

  3. As carry is zero, whatever in a, which is 10010 becomes the answer!

Much better to understand with examples, smaller examples.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.