Instructions

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Approach

We cannot use arithmetic operators, so we have to use bit manipulation to achieve addition.
The XOR operator is useful for bit manipulation where its output is shown below.

1^1=0
0^0=0
0^1=1

From the code above we observe that 1^1=0 which is not equal to 1+1. We can use the AND(&) operator to handle carry to calculate the correct answer. We shift the carry to the left and repeat the operations until we get a result of 0 meaning there are no more carries.

Here is an example:

Python Implementation

def getSum(self, a: int, b: int) -> int:
        while (b != 0):
            carry = a & b
            a = a ^ b
            b = carry << 1
        return a

The time complexity is 0(n).
The solution is sufficient for most scenarios but we can improve it by consider that the range of bits for representing a value is not 32 in Python.
Therefore, we have to use a 32 bit mask of 1's represented by 0xfffffff.
The mask expands a number into a 32 bit / unsigned integer.
Our solution becomes:

def getSum(self, a: int, b: int) -> int:    
        mask = 0xffffffff
        while (b & mask) > 0:
            carry = (a & b) << 1
            a = (a ^ b)
            b = carry
        return (a & mask) if b > 0 else a

Approach 2

We can use logarithms to achieve the same result.
From our knowledge of logarithms, we know that

• 2 ^a x 2 ^b = 2 ^a+b and

• log _a (a ⁿ)= n therefore,

• log ₂ (2 ^a+b)= a+b

  Python Implementation

def getSum(self, a: int, b: int) -> int: 
    return int(math.log2(pow(2,a)*pow(2,b)))

Useful Links

Mask
Mask