In basic computer architecture class, the instructor may only tell you how to calculate the two's compliment of a number: complement all the bits except for the sign bit, and then plus one. Do you know why? In this ariticle, I'll show why we need it, and how it works in computer architecture.
Basic Review on Von Neumann Architecture
Von Neumann Architecture, architecture of modern computers, is an implementation of Turing machine. There're three basic parts in Von Neumann Architecture: Arithmetic/Logica Unit (ALU), Control Unit and Memory. In this article, we'll focus on ALU. Basic arithmetic operations are add sub mul and div. Theorically, we need four unique modules, but there's only add module in ALU, no sub module. How to calculate substraction operation? The answer is simple: 5-2 turns to 5+(-2). Then the question comes: why we need two's complement?
Why We Need two's compliment
If we use true form to represent numbers. For the example above:
0101 (5)
+ 1010 (-2)
-------------
1111 (-7)
Obviously, the result is not correct in true form. Let's think about using two's complement:
0101 (5)
+ 1110 (-2)
------------
1 0011 (3) MSB carry out, discarding the overflow bit
The result is correct using two's complemnet representing numbers and using add to perform substraction. Now the next question comes: How two's complement comes, and why it is correct?
Before answering this question, let's look at a daily example: considering a clock, 12 numbers on it in a cycle. Assuming the current hour on the clock is 2, and you want to change it to 5. What will you do? There're two ways to do it:
1. moving the clock forward by 3 clockwise.
2. moving the clock backward by 9 anti-clockwise.
Now, let me introduce the modulo operator MOD. MOD means the remainder of a division. For example: 5 (mod 2) = 1. The definition of MOD in math is that:
x mod y = x - y⌊x/y⌋ (y ≠ 0)For a positive integer n, two integers a and b are said to be congruent modulo m:
a ≡ b (mod m)To be further:
if a ≡ b (mod m), c ≡ d (mod m), then a+c ≡ b+d (mod m)In the clock problem: 3 ≡ -9 (mod 12). Thus, 2+3 (mod 12) ≡ 2-9 (mod 12)
Now, back to the two's complement, the basic priciples is the same. Consider two signed char variable:
char a = 127, b = -2;
printf("%d\n", a+b);Here's the details:
a = (0)111 1111 b = (1)111 1110
a + b: (0)111 1111 + (1)111 1110 = (0)111 1101 = 125The range of signed char is from -128 to 127. So the modulo is 256. According to the congruent modulo theorem: -2 ≡ 254 (mod 256), thus 127-2 (mod 256) ≡ 127+254 (mod 256) = 125. If we look into the two's complement of -2, it equals to the value of 254 if we don't care about the sign bit. That is to say, the two's complement of a negative number equals to a positive number that has congruent modulo with range of variable type.
Carry out From MSB and Overflow
Before looking at the rest of this section, a clarification need to be put forward first. An Overflow means in arithmetic caculation between fix point numbers, the result exceeds the range of this data type could represent. For example, when adding two signed char variables, both 127 + 1 and -128 + (-1) mean overflow. An Underflow means in float point number calculations, the result exceeds the smallist number that data type could represent.
No Overflow
Let's recall the previous case:
char a = 127, b = -2;
printf("%d\n", a+b); 0111 1111 (127)
+ 1111 1110 ( -2)
------------------
1 0111 1101 (125) MSB carry out, discarding the overflow bit
When they adds, the Most Significant Bit (sign bit) carries out. In this case, bit carry into MSB was 1 and bit carry out from MSB was also 1. Thus, there's no overflow in this case.
Overflow
Now let's see what happens to MSB when there's an overflow:
char a = 127, b = 1;
printf("%d\n", a+b); 0111 1111 ( 127)
+ 0000 0001 ( 1)
------------------
1000 0000 (-128) no MSB carry out
When they adds, Most Significant Bit (sign bit) doesn't carry out. In this case, bit carry into MSB was 1 and bit carry out from MSB was 0. Thus, there's an overflow in this case. Note that in this case, according to the congruent formula I just illustrated, -128 ≡ 128 (mod 256). So the result is -128 instead of 128.
Let's see another example when there's an overflow:
char a = -128, b = -1;
printf("%d\n", a+b); 1000 0000 (-128)
+ 1111 1111 ( -1)
------------------
1 0111 1111 ( 127) MSB carry out, discarding the overflow bit
When they adds, Most Significant Bit (sign bit) carries out. In this case, bit carry into MSB was 0 and bit carry out from MSB was 1. Thus, there's an overflow in this case. Similarly, -129 ≡ 127 (mod 256). So the result is 127 instead of -129.