DEV Community

Bernice Waweru
Bernice Waweru

Posted on • Updated on

Sum of Two Integers without Arithmetic operators

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
Enter fullscreen mode Exit fullscreen mode

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:

XOR AND <<

Python Implementation

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

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
Enter fullscreen mode Exit fullscreen mode

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)= n therefore,

  • log 2 (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)))
Enter fullscreen mode Exit fullscreen mode

Useful Links

Mask
Mask

Top comments (4)

Collapse
 
matthewsalerno profile image
matthew-salerno

A friend of mine and I tried writing some simple functions in python without using any arithmetic operators or numeric literals. It was pretty fun, mostly boiled down to taking the length of lists of empty lists and other objectively cursed things. It was still a fun exercise though and definitely worth trying. I like your approach of using logic operators, although it still seems a little too close to normal addition to me. The log method was really neat and definitely not something I would have thought of.

Collapse
 
sarveshprajapati profile image
Sarvesh Prajapati

try to make a catchy title, to gain traffic:
instead of Sum of Two Integers,
try this:
Sum of Two Integers ( without + operator )

Collapse
 
curiousdev profile image
CuriousDev

Yes, the title is kinda misleading (if it makes you think it is just simply adding numbers). This could be made more interesting.

Collapse
 
wanguiwaweru profile image
Bernice Waweru

Thanks for the suggestion.