371. Sum of Two Integers

Description

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

Example 1:

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

Example 2:

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

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
let getSum = function (a, b) {
  //keep left shifting until there are no more digit sums to carry
  while (a != 0) {
    //carries occur at positions where both bits are 1
    let carryDigits = a & b;
    //'add' together bits
    b = a ^ b;
    //actually 'carry over' the carry digits by shifting left
    a = carryDigits << 1;
  }

  return b;
};

Analysis

This was actually kind of difficult despite it being marked as an easy problem. I feel like I had a vague idea about how to go about this one only because of a similar problem I had to do back in college. If I had never done that problem I don't think I could have come up with a solution for this.

I tried an example with 11 and 3 so I could think about how to 'transform' the summands into what their sum should be.

  1011
+ 0011
= 1110

If we start to add the two number together like you normally would, we would start with the rightmost bits and do 1+1=10. Another way to think about it is 1+1=0 and we have to carry the 1. How would we actually carry that 1? We just shift it left just like if you were calculating the sum by hand.

  1
+ 1
= (carry 1)0
= 10

So how do we know which bits will result in a carry? If we look at the example again it's easy to see we will need to do carrying for the 3rd and 4th bits.

  1011
+ 0011
= 10(carry 1 + (1+1))0
= 1(carry 1)10
= 1110

When both bits to be summed are 1 it will result in a carry. We could use & the bitwise AND operation to locate these bits.

  1011
& 0011
= 0011

Then to actually 'do' the carrying, we simply shift the bits left.

  0011 << 1
= 0110

But this isn't exactly what we want. It's close but not quite. The leftmost digit is still wrong. If we think about how we add the bits by hand again, we notice that 1+0=1 and 1+1=(carry 1)0. This looks similar to a bitwise operation, in particular bitwise XOR ^.

  1011
^ 0011
= 1000

The first leftmost bit is correct but the second two aren't. We will need to combine XOR and AND and shifting to get the result we want.

So to summarize this so far since I'm really bad at explaining things, when we add two bits together they result in either 1 or 0 without needing to carry or 0 and needing to carry. When at least one bit is 0, there will be no carry and we can compute that sum by using ^ XOR. To locate the bits where carrying occurs, we can use & AND. To actually 'do' the carrying, we << shift the bits left by 1 position.

So for the example of 11 and 3,

So what do we do with these resulting numbers? We add them again. Why? We are adding the result of adding the numbers together without carrying and the results of just carrying.

There are no bits left to carry so we're done. Also observe that we got the right answer, 14.