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 allowed to use the operator + and -.

Note: Be careful of the negative cases.

Example: 

1
2
3
4
5
Input: a = 1, b = 2
Output: 3

Input: a = -2, b = 3
Output: 1

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
2
3
4
5
int i = 0;
while (a != 0 || b != 0 || carry > 0) {
  if (i >= 32) break;
  // ...
}

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
2
3
4
5
6
7
Example: (say 8-bit range to simplify)
a  1111 1111  -1
b  1111 1111  -1
   1111 1110  -2 the result should be -2
If we did not stop when #bits > 8, we would have:
  10000 0000  Unfortunately, it is 1 instead of 0.
  Thus, it would have made the result to be -1.

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
2
3
4
5
6
7
Example: (say 3-bit range to simplify)
a  0 0 1
b  1 0 1
       0  (other bits are 0)
     1
   1      combine each by left-shifting and ^ operation
   1 1 0

How to Calculate the Carry?

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

1
2
3
4
5
6
// For simplicity, a is the current bit of a, ...
a b c    new carry
1 0 1 -> 1  // a ^ b = 1
0 1 1 -> 1
1 1 0 -> 1  // a & b = 1
1 1 1 -> 1

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
2
3
4
5
6
// carry = (a & 1) & (b & 1); // when a = 1, b = 1
// It is buggy, because it does not consider carry.
int abAND = (a & 1) & (b & 1);
int abOR = (a & 1) | (b & 1);
if (abAND == 1 || (abOR == 1 && carry == 1)) carry = 1;
else carry = 0;

Here is the complete code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int getSum(int a, int b) {
  int result = 0;
  int carry = 0;
  int i = 0;
  while (a != 0 || b != 0 || carry > 0) {
    if (i >= 32) break;
    int sum = (a & 1) ^ (b & 1) ^ carry;
    int abAND = (a & 1) & (b & 1);
    int abOR = (a & 1) | (b & 1);
    if (abAND == 1 || (abOR == 1 && carry == 1)) carry = 1;
    else carry = 0;
    // update
    result ^= (sum << i);
    a = a >>> 1; // logical right shift
    b = b >>> 1;
    ++i;
  }
  return result;
}

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
2
3
4
5
6
7
8
9
public int getSum(int a, int b) {
  int noCarryBits = a ^ b;  // where 1 ^ 0, 0 ^ 1, and 0 ^ 0
  int carryBits = a & b;    // where 1 ^ 1
  if (carryBits == 0) { // no carry created
    return noCarryBits;
  } else {
    return getSum(noCarryBits, carryBits << 1); // think about it
  }
}

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