Sum of Two Integers

Patrick Leaton
Published: March 16, 2021, 12:37 a.m.
Problem 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

 

The description was taken from https://leetcode.com/problems/sum-of-two-integers/.

Problem Solution

#O(1) Time, O(1) Space
class Solution:
    def getSum(self, a: int, b: int) -> int:
        x, y = abs(a), abs(b)
        if x < y:
            return self.getSum(b, a)
 
        if a > 0:
            sign = 1
        else:
            sign = -1
           
        if a * b >= 0:
            while y is not 0:
                x, y = x ^ y, (x & y) << 1
        else:
            while y is not 0:
                x, y = x ^ y, (~x & y) << 1
        return x * sign

Problem Explanation

If we are given a problem and are asked to perform a specific operation without using its operator, that is usually an indication that bit manipulation will be required.

Inherently, there are a lot of use cases when summing both positive and negative numbers because a and b could be lesser or greater than the other, one could be negative, both could be negative, both could be positive, so we want to reduce the number of use cases to two. 

We can simplify this to strictly dealing with the sum or the difference of two positive numbers.  It will either be x plus y where x is greater or x minus y where x is greater. 

We’ll start by converting the two integers a and b to their absolute values and copying them to x and y.

        x, y = abs(a), abs(b)

 

Both of the two use cases that we're focusing on require x to be the greater, so we’ll check if that is the case and if not, we’ll re-run our function with the inputs switched.

        if x < y:
            return self.getSum(b, a)

 

Next, let's check our initial a value and see if it’s negative or positive so that we’ll know what sign our result integer should have.

        if a > 0:
            sign = 1
        else:
            sign = -1

 

Next, we’ll see if the product of our two input integers is positive.

If it is positive then we know we’re adding two positive integers.  If it is negative then we know we’re taking the difference of two positive integers instead.

        if a * b >= 0:

 

For both our computations, we’ll use a loop that will run while there are still values to carry.

            while y is not 0:

 

The addition computation will consist of setting x equal to the result of x XOR y, so that we can isolate the bits that aren't both one within each number and won't need to be carried when summed.

After isolating the bits that won't need to be carried when summed into x, let's now isolate the ones that do into y.  We'll shift them to the left and carry them so that we can continue summing them with the more significant bits within the next iteration.

This is similar to how we would add two numbers on paper.

                x, y = x ^ y, (x & y) << 1

 

For the difference computation, where the product is a negative result, the only difference from the addition computation is we’ll be using the negation of x due to our second use case. 

                x, y = x ^ y, (~x & y) << 1

 

Once we have our final result, we will want to multiply it by our sign before returning so that we return a negative or positive value based on what a was originally.

        return x * sign

 

The solution has a constant time and space complexity because we are only dealing with two 32-bit integers so we will at most have thirty-two iterations.