intuitive explanation for bitwise addition code

Question

I understand bitwise addition, and I understand bitwise operations, but I'm having a hard time understanding why this code effectively adds two integers.

def Add(x, y):

    while (y != 0):

        carry = x & y
        x = x ^ y
        y = carry << 1

    return x

Is there someone that can please provide an intuitive explanation for exactly why this works? I can follow the logic for the right most bit initially. I..e, it makes sense that the carry item should be the result of and operation between x and y on the right most bit. Then, we use the left shift to make that carry computed at the first iteration on the right most bit now apply to the second right most bit on the second iteration. Around this point that I start getting quite confused (i.e., because the new "y" on iterations > 1 are the result of the previous carry operation, etc).

If someone who understands this in depth can break it down, I'd appreciate it.

If you google for "add with bitwise operations" or "add without + operator"... you'll see tons of explanations for this: [Adding two numbers without + operator (Clarification)](https://stackoverflow.com/q/9070937/995714) https://stackoverflow.com/q/4895173/995714 https://stackoverflow.com/q/4068033/995714 https://stackoverflow.com/q/15327169/995714 — phuclv, Jan 13 '18 at 11:29
Possible duplicate of [Why this code for addition(using bitwise operation) works in java](https://stackoverflow.com/questions/17342042/why-this-code-for-additionusing-bitwise-operation-works-in-java) — phuclv, Jan 13 '18 at 11:30

L. Meyer · Answer 1 · 2018-01-13T08:57:58.717

To understand how it works, you have to remember how to add two numbers. Let's take an example, if we add 9 and 5 in bit representation, we have:

carry    1
    9  1001
  + 5  0101
-----------
   14  1110

We can decompose into two steps:

first we just add the numbers without the carry
the carry is added to the result

In bitwise operation, this is:

  9  1001
^ 5  0101
---------
 12  1100

And the carry is get by the & operation with a shift on the left <<. Here we have:

  9  1001
& 5  0101
---------
     0001

and 0001 << 1 = 0010

The instruction

 carry = x & y
 x = x ^ y
 y = carry << 1

only adds x and y without the carry. Hence, we replace x by the result and y by the carry until y equals 0.

intuitive explanation for bitwise addition code

1 Answers1