Reference: LeetCode

Difficulty: Easy

My Post: Java Solution Bitwise Simulation (Illustrate with Examples)

## Problem

Calculate the sum of two integers $a$ and $b$, but you are

not allowedto use the operator`+`

and`-`

.

**Note:** Be careful of the negative cases.

**Example:**

1 | Input: a = 1, b = 2 |

## Analysis

### Simulation

We can apply the idea in Add Two Numbers, although this oe is tricky. Let’s analyze each line of code to see why it is written that way.

**Negative Cases:**

1 | int i = 0; |

Notice that we apply the same method for negative numbers too, but we must not process the bits that are out of 32-bit range (`if (i >= 32) break;`

).

1 | Example: (say 8-bit range to simplify) |

Also, the condition is `a != 0 || b != 0`

rather than `a > 0 || b > 0`

because we don’t expect to stop for negative numbers.

**How to Store Result?**

Since each time we process one rightmost bit, by using an index `i`

we remember its corresponding position in the result.

1 | Example: (say 3-bit range to simplify) |

**How to Calculate the Carry?**

It is not obvious. We think there should be a better approach. Here is mine.

1 | // For simplicity, a is the current bit of a, ... |

We want to express the idea that if there are at least two one-bits among `a`

, `b`

and `c`

. By the last two rows, we know that:

- If
`a & b`

is $1$ (`1 1`

case), the new carry must be $1$ no matter what`c`

value is. - If
`a | b`

is $1$ (`1 0`

or`0 1`

case), the new carry can be $1$ only if`c`

is also $1$.

Translating into code, we have:

1 | // carry = (a & 1) & (b & 1); // when a = 1, b = 1 |

**Here is the complete code:**

1 | public int getSum(int a, int b) { |

**Time:** $O(1)$ since it takes at most 32 iterations.**Space:** $O(1)$

### Recursion (clever)

Reference: 详细思路和代码(Detail explanation and code) by KevinYao7167

The basic idea is to create two parts (bits that don’t create carry and bits that create carry) and recursively construct the result.

1 | public int getSum(int a, int b) { |

**Time:** $O(1)$**Space:** $O(1)$