As a human being, we can do a lot of mathematic calculation in our mind. But for the computer, they like the thing to be as easy as possible. So, this chapter will talk about how the computer to the mathematic like addition and subtraction.

Question

Before we begin the topic, let's consider a question:

how to calculate the sum of two integer without using + and - ?

Note: the answer can be find in the Answer section.

Let's begin here.

We both konw that, computer just know 0 and 1. If a computer want to calculate 1+3, it will do as follow:

1. change 1 to binary system which look like 0000 0001(let assue the computer is 8-bit in this article)
2. change 3 to binary system, so it will be 0000 0011
3. add this two number together, if meet 2 then carry 1 and place 0 in the original position. So, we get 0000 0100 which represent 4 in decimal system.

What's more, for a computer, the highest bit is used for storing the symbol of this number, 0 means positive and 1 means negative. This kind of representative measure called "sign and magnitude".

So, +1 will be 0000 0001 and -1 will become 1000 0001.

The addition is finished here, but how about subtraction? From math class, we know that subtraction can be seem as addition. For example:

2 - 1 = 2 + (-1)

With this idea, the computer scientists want to find a way that can use the same hardware system to deal with the subtraction just like the addition. Here is the ones' complement. Let's give the definition of this guy,

for a positive number, its one's complement is itself; for a negative number, its one's complement number is inverting all the bits in the binary representation of the number except the symbol bit.

For example,

• +1, its one's complement is 0000 0001
• -1, its one's complement is 1111 1110

Computer scientists say thar with the one's complement we can almost treat subtraction as addition , let's test whether it can do subtraction like addition or not. If I have a -3 and a 6, the step of the calculation should as follow:

1. -3 ---> 1000 0011 and 6 ---> 0000 0110
2. take their ones' complement respectively, so we get 1111 1100 and 0000 0110
3. add them together:

 1111 1100
 0000 0110
----------
10000 0010 (overflow) = 0000 0011 = 3 (decimal)

From the steps above, the one's complement worked! But, we need to know the rule of overflow. If we get an overflow, we have to remove the highest-bit and add one to the lowest-bit.

Actually, the one's complement worked at most time, except some cases whose answer is 0. For exmaple, 1 + (-1) = 0:

 0000 0001
 1111 1110
----------
 1111 1111[ones' complement] = 1000 0000[sign and magnitude] = -0

In this case, we get a minus zero. What is -0, as human being, we treat -0 = 0. But if we need to make the computer know they are the same, it will waste some resources. The computer scientists believe that there will another way just need the computer to know zero.

Luckily, they created something called

"two's complement" to solve this problem. The definition of two's complement as follow:

for positive number, the two's complement is itself; for negative number, the two's complement is its ones' complement plus one.

Let check, can it fix the minus zeor problem. Take the same example, 1 + (-1) = 0:

 0000 0001
 1111 1111
----------
10000 0000(overflow) = 0000 0000 = 0(demical)

Unfortunately, we got an overflow again. But when we using two's complement for calculation, we do not need do to other job for the overflow, just ignore it.

That is how the computer do addition and subtraction. Every number you input in a computer, it will change it into its two's complement then do the calculation. In the way, we can know that the computer treat subtraction as addition. Only a set of hardware can finish the job.

Answer

With the knowledge above, we almost reach the answer. Of course, we need to figure out this question like a computer which mean we need to think in binary way. But please don't try to use if...else... to do the math, in that way, you need to write a lot of codes and need to separate additoin and subtraction.

Do you remember these two kinds of bit operation:

& operation
A    B     A&B
0    0      0
0    1      0
1    0      0
1    1      1
----------------
^ operation
A    B     A^B
0    0      0
0    1      1
1    0      1
1    1      0

We know the computer will treat the subtraction as the addition, so we just need to figure out the how the addition work then the subtraction will be done. For addition, we always need to check whether there is a carry or not. We notice that:

• just consider the carry, the answer is same as & operation
• just consider the addition(without carry), the answer is same as ^ operation

So, we can do find out where the carry is by & operation and do the addition by ^ operation.

I will implement it in java, the code as follow:

// using loop
public int GetSum(int a, int b){
    while (b != 0) {    
        int c = a & b;
        a = a ^ b;
        b = c << 1;
    }
    return a;
}

// using recursion
public int GetSum(int a, int b){
    (b != 0) ? GetSum(a ^ b, (a & b) << 1 ) : return a;
}

Sept. 28, 2016 Montreal
Eric Lai