Sum of Two Integers

Examples

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

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

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

Constraints

• -1000 <= a, b <= 1000

Approach

Every bit position in binary addition works the same way ordinary decimal addition does: adding two bits produces a result digit, and sometimes a carry into the next position over. XOR of two bits happens to match exactly the digit you'd get from adding them without any carry (1+0 or 0+1 gives 1, 0+0 and 1+1 both give 0 - which is exactly what a carry-free addition would look like at that position). AND of two bits is 1 exactly when both bits are 1, which is exactly when a real addition would carry into the next position.

That gives a way to add two numbers using no + or - at all: XOR a and b to get their sum ignoring every carry, and separately compute where the carries need to go (AND of a and b, shifted one position to the left, since a carry always lands one bit higher). Then add that carry back in - using the exact same XOR/AND process again on the partial sum and the carry - and keep repeating until there's no carry left to add. Because there are only 32 bits to carry through at most, this always finishes quickly.

Solutions

Brute Force - Step One Unit at a Time

Increment a, one unit at a time, b times (or decrement it, if b is negative). This technically avoids the + and - operators, but it does as much work as the size of b, and doesn't reflect how addition is actually meant to be done here.

function getSum(a, b) {
  if (b >= 0) {
    for (let i = 0; i < b; i++) a++;
  } else {
    for (let i = 0; i < -b; i++) a--;
  }
  return a;
}

Time: O(|b|) · Space: O(1)

Optimal - Bitwise XOR for Sum, AND for Carry

Repeatedly compute a 'carry-free sum' with XOR, and the carry itself with AND shifted left by one bit. Feed the carry back in and repeat until there's no carry left - at that point, the running value is the true sum.

function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

Time: O(1) - bounded by the fixed 32-bit width of the numbers · Space: O(1)