How to Add Two Numbers Without Using A Plus Symbol?

This is a very common algorithm problem, which seems very easy to understand at first but as different cases and a set of all integers(both positive and negative) is included the kick starts and things start to become a little more complicated than we think it is.

Let us first understand how do computers represent the negative numbers in their memory. Understanding this will essentially make our life and this algorithm easier.

Computers represent negative numbers in the form of 2’s Compliment. Now 2’s complement is defined as the complement of the number concerning 2**n (this is read as 2 to the power n, I have used the python representation of exponent because later on the code I will provide will be in python and ‘^’ operator in python means the bitwise xor (exclusive or) and not exponent) , where n is the number of bits that the numbers are defined in. And mathematically for a number say x which is represented in n bits and its 2’s complement is y,

x + y = 2 ** n
or, y(2’s compliment of x) = 2 ** n - y

For example, let's say I have a number 5 and I have used 4 bits to represent the number in the computer's memory than the 2’s complement of 5 would be,

2’s compliment of 5 is,
2 ** 4 - 5
or, 16 - 5
or, 11

But Computers don’t understand the decimal number system, they talk in binary. So let’s understand it in the “0 1 way”.

Let’s consider our previous example of 5,

In Binary, 5 would look something like 101 and if we are using a 4-bit representation then it would take the form of 0101. 16 would look like 10000. Of Course, you can do the operation,

10000(base 2) — 0101(base2) = 1011(base2)

But do computers really understand the language of ‘-’ (minus)? The answer is a big NO. So, how do we do it then?

Needless to say, there is a very easy way to convert a binary number to its 2’s complement form.

Step 1 - Invert all the bits that is 0 becomes 1 and 1 becomes 0
Step 2 - Add 1 to the inverted number

So, if our number is 0101 (5 in decimal),

Step 1 - We invert all the bits, so 0101 becomes 1010
Step 2 - We add 1 to it. Hence 1010 becomes 1011 (which is indeed the 2’s compliment of 0101 as we have seen it in the decimal way above).

Note: You may think now how come we are using ‘+’(plus) to avoid the ‘-’(minus) operation. Don’t get confused. Computers do not understand ‘+’ as well. And we will see how to replace ‘+’ in a while. But for now, let’s take ‘+’ for granted like we have done our entire life.

Why 2’s Compliment?

Now you may think why do we use 2’s compliment at all? Like I said earlier, ‘+’ and ‘-’ are mere human symbols that make no sense to a computer at all. -5 means something to us but for a computer it means nothing. So, we must convert all negative numbers to something positive to help the computer compute them internally.

2’s complement can be considered as a convention used to make life easy for us and enabling computers to understand the language of negative numbers.

Suppose we make a new number system where we define that all the numbers will essentially be between -99 and 99. Now, let’s take 100 as our new complementing element. So, whenever we encounter a negative number we just add to 100. The positive numbers will always be between 1 and 99 and the negative numbers now can be represented in a complimented form that is, x + our compliment of x = 100. This will make the handling of negative numbers a lot easier.

Suppose, in my method of complementing by 100, I have two numbers 23 and -45 and I want to add them.

So,

23 remains 23 but 45 becomes,
100 - 45 = 55.

Initially, I wanted to add 23 and -45 but my computer will represent -45 as 55 and add,

So, my addition becomes,

23 + 55 = 78 (But this is the addition in the complemented form)

So, I will get my actual answer that is the answer for,

23 - 45

By again complementing my previous answer.

So, 78 becomes,

78 - 100 (100 is subtracted because 78 is the complemented form not the original number)
= -22

Which is our desired result. This entire hustle will enable the computer to represent negative numbers very easily.

(This is undoubtedly a tiny effort on my part to explain “Why things happen, How things happen”. More detailed discussions will divert us from our main problem statement.)

How does summation happen?

From our childhood we are taught to add two numbers in the conventional way that is, start from the rightmost digits, the result of the addition is more than a digit carry forward the extra digit to the next set of digits and hence the process continues until there are no digits to get added.

Now let’s take two numbers say 2345 and 5679.

When I add these two numbers in the conventional way something like this happens,

 2    3    4    5
 5    6    7    9
 1(c) 1(c)  1(c)
--------------------
 8    0    2    4

#1(c) represents the carry.

What happens if I just add and forget to carry?

1) 2 3 4 5 + 5 6 7 9 = 7 9 1 4 (Adding without carrying) 

What if now I just carry?

2) 2 3 4 5 + 5 6 7 9 = 0 1 1 0 (Only Carrying not adding)

Now if I recursively, continue step 1 and step 2 until there is 0 carry then,

1) 7 9 1 4 + 0 1 1 0 = 7 0 2 4 (Adding without carrying)
2) 7 9 1 4 + 0 1 1 0 = 1 0 0 0 (Only Carrying not adding)
Again,
1) 7 0 2 4 + 1 0 0 0 = 8 0 2 4 (Adding without carrying)
2) 7 0 2 4 + 1 0 0 0 = 0 0 0 0 (Only Carrying not adding)

Note, that the time when our carry becomes 0 we get our answer!

Let’s Do it in the Binary Way

In Binary,

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 1 0

If we just add without any carry, then we need to have a 1 when the bits getting added are not the same, that i.e 0, 1 will give 1 and 1, 0 will give 1 the rest two situations will have that is 1, 1 and 0, 0 will have 0 as the outcome. This is nothing but the xor (exclusive or) operation!

Now, If we just carry and not add then we need 1 right-shifted by one position when there are two 1’s together. The rest of the cases will give zero. This is nothing but a bitwise & operation that is right-shifted by 1!

So, as we build up our logic we can say that,

add_without_carry = number1 ^ number2
only_carry = (number1 & number2) << 1

This is mathematically sound and the logic is going to work fine as long as we are using positive numbers.

If we want to add just positive numbers, our code should look something like this,

def addPositveNumbers(number1: int, number2: int) -> int:
    if number2 == 0:
        return number1
    return addPositiveNumbers(number1 ^ number2, (number1 & number2) << 1)

All good so far, but the real kick comes in when we start dealing with the negative numbers.

So The Negative Begins

For convenience and to avoid unnecessary typing I am going to use a 5-bit representation of numbers. You can simply convert this into a 32 bit or 64-bit representation as per your need.

Let us assume a 5-bit representation of numbers where the leftmost bit represents the sign (whether it is positive or negative, and we will see in a while why the leftmost bit is considered for the sign) of the number.

0 in the leftmost bit represents a positive number
1 in the leftmost bit represents a negative number

So, in our 5-bit representation, the rightmost 4 bit represents our number and the one leftmost bit represents the sign of the number, that is,

4  will be represented as 0 0100
-4 will be represented as 1 0100

But negative numbers are represented in the computer’s memory in 2’s complement form. So, if we consider 5 bits all the 5 bits will be inverted and then 1 will be added to the rightmost bit. Now, if we use a 5-bit representation where we always use only the last 4 bits to represent the number and the rightmost bit as only the sign determining bit, the number when will be converted into 2’s complement will always have the leftmost bit as 1. This is the reason why the leftmost bit is used for determining the sign of the number.

Now in our 5-bit representation where just the 4 bits are used for actual number representation, the maximum number that can be represented is,

0 1111 (base 2)

Any number that will eventually come out to be greater than this is sure to be a negative number, as any number greater than this will have 1 in the left-most bit which is essentially making the sign determining bit 1, meaning negative.

Now, we logically understand the fact we are using a 5-bit representation where our leftmost bit is determining the sign of the number. But will the computer understand it? NO!

So, What now?

So, now we will use the concept of bit masking to always consider the last 5 bits of the numbers (note that, considering the last 5 bits is a constraint I am enforcing, as I mentioned earlier, that will fix the minimum and maximum element. You can enforce your own constraint.)

For always extracting the last 5 bits of the number we will do a bitwise & with 11111 (five 1’s). This will help us know all the positions of 0 and 1 in the last 5 bits of the number. (0 & 1 will give 0, 1 & 1 will give 1).

Now, the work is almost done, and before jumping into the python code I will give a little technical overview of a python element.

The ‘~’ sign,

~ in python gives 2’s complement of any number. Let’s make it more clear, the ~ operator in python will take a number add one to it, and then flip its sign. That is,

~2  = -3
~45 = -46 
.
.
and so on.

Before the actual code let's write a step-by-step algorithm.

Let's define the base case for the recursion first, 
1) If the carry is 0 and the number is less than the maximum (as I said earlier the maximum number is now fixed) then we return the number we got by recursively adding till now.
2) Else, we know our answer is negative so we will flip the bits(that is do a xor with our maximum number (four 1’s for this case) and then add one and put a negative sign in the beginning of the number(which will be done by the ~ operator)
Now, the old technique we learnt!
3) We will keep calling our function recursively on our sum and carry until the base case is hit and the function returns the result.

Finally The Code!

The python code will look something like this when we consider only 5 bits of signed representation.

def add(number1: int, number2: int) -> int:
    maximum = 0b01111
    mask = 0b11111
    if number2 == 0:
        return number1 if number1 <= maximum else ~(number1 ^ mask)
    return ((number1 ^ number2) & mask, ((number1 & number2) << 1) & mask)

Note: Writing 0b before a number is a pythonic representation of binary numbers. You can also write those two numbers in decimal, I have written the numbers in binary to make the algorithm more clear.

I hope this explanation is of some use to you and gives you a more detailed insight into this problem. I thank, Kshitiz Miglani, for his awesome video on the same which helped me understand this algorithm a lot better and of course come up with this blog. I have linked the video below, you can go and check that out. (I have timestamped the video at 38: 41, where this question starts).

Leetcode, 371. Sum of two Integers (Click here for the video)