371. Sum of Two Integers

Reference: LeetCode
Difficulty: Easy

Problem

Calculate the sum of two integers $a$ and $b$, but you are not allowed to use the operator + and -.

Note: Be careful of the negative cases.

Example:

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:

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

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.

How to Calculate the Carry?

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

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:

Here is the complete code:

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.

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

Comment
Junhao Wang
a software engineering cat