Bitwise operation for add

Question

Could you please help me figure out why the following expression is true: x + y = x ^ y + (x & y) << 1 I am looking for some rules from the bitwise logic to explain this mathematical equivalent.

Accepted Answer

It's like solving an ordinary base 10 addition problem `955 + 445`, by first adding all the columns individually and throwing away carried `1`s:

```
    955
    445
  -----
    390
```

Then finding all the columns where there should be a carried `1`:

```
    955
    445
  -----
    101
```

Shifting this and adding it to the original result:

```
   390
+ 1010
------
  1400
```

So basically you're doing addition but ignoring all the carried `1`s, and then adding in the carried ones after, as a separate step.

In base 2, XOR (`^`) correctly performs addition when either of the bits is a `0`. When both bits are `1`, it performs addition without carry, just like we did in the first step above.

`x ^ y` correctly adds all the bits where `x` and `y` are not both `1`:

```
   1110111011
^  0110111101
-------------
   1000000110      (x ^ y)
```

`x & y` gives us a `1` in all the columns where both bits are a 1. These are exactly the columns where we missed a carry:

```
   1110111011
&  0110111101
-------------
   0110111001      (x & y)
```

Of course when you carry a `1` when doing addition you shift it left one place, just like when you add in base 10.

```
   1000000110      (x ^ y)
+ 01101110010    + (x & y) << 1
-------------
  10101111000
```

Bitwise operation for add

Solution

Problem