Subtraction
Talk0this wiki
Most processors can do subtraction of numbers. We use the - sign to show subtraction of the second number from the first number:
first - second
The order is important, because first - second and second - first are not equal. In fact second - first is the negation of first - second, and vice versa.
Contents |
Binary subtraction 
Edit
Subtraction is similar to but more difficult than addition. Our first new problem is that the only binary digits are 0 and 1, so we have no binary digit to answer 0 - 1.
first - second => answer
- 0 - 0 => 0
- 0 - 1 => what answer?
- 1 - 0 => 1
- 1 - 1 => 0
To solve the problem, we introduce a borrow flag. We borrow a 1 from the next place to compute 10 - 1, or borrow a 0 otherwise.
first - second => answer
- 00 - 0 => 0, borrow the 0
- 10 - 1 => 1, borrow the 1
- 01 - 0 => 1, borrow the 0
- 01 - 1 => 0, borrow the 0
This is how to subtract if the previous place borrowed from this place:
-borrow + first - second => answer
- -0 + 00 - 0 => 0, borrow the 0
- -0 + 10 - 1 => 1, borrow the 1
- -0 + 01 - 0 => 1, borrow the 0
- -0 + 01 - 1 => 0, borrow the 0
- -1 + 10 - 0 => 1, borrow the 1
- -1 + 10 - 1 => 0, borrow the 1
- -1 + 01 - 0 => 0, borrow the 0
- -1 + 11 - 1 => 1, borrow the 1
Subtraction of unsigned integers Edit
To subtract from a first integer of a second integer, to compute first - second, we work from the least significant bit to the most significant bit. We borrow and we subtract the bits in each place.
To compute 27 - 13 => 14 like an 8-bit processor, we write 27 as %00011011 and 13 as %00001101, then we subtract.
(borrow) 00001100
(first) 00011011 27
(second) - 00001101 - 13
========== ====
00001110 14
0 => borrow flag
The last borrow flag is zero if the answer is correct, or one if the answer has overflowed. (Some processors use an inverted flag: one if the answer is correct, or zero if the answer has overflowed.) Unsigned overflow happens when the correct answer would be negative.
Subtraction of signed integers Edit
The subtraction procedure for twos-complement signed integers is the same as the procedure for unsigned integers.
(borrow) 11110010 unsigned signed
(first) 00001101 13 13
(second) - 00011011 - 27 - 27
========== ===== =====
11110010 242 -14
1 => borrow flag
0 => signed overflow flag
An 8-bit processor might compute 13 - 27 => %11110010. We can interpret %11110010 as the unsigned value 242 or the signed value -14, but the correct answer is -14. This is a case of unsigned overflow but not signed overflow. Thus the borrow flag is one (for unsigned overflow), but the signed overflow flag is zero.
Overflow Edit
There are cases the signed answer is wrong but the unsigned answer is correct.
(borrow) 01111110 unsigned signed
(first) 10000101 133 -123
(second) - 00011110 - 30 - 30
========== ===== =====
01100111 103 103
0 => borrow flag
1 => signed overflow flag
The unsigned computation 133 - 30 => 103 is correct, but the signed computation -123 - 30 => 103 is wrong. The correct signed answer would be -153, which is outside the -128..127 range of a signed 8-bit value. So the signed overflow flag is one, but the borrow flag is zero (for lack of unsigned overflow).
There are cases where both answers are wrong.
(borrow) 10000000 unsigned signed
(first) 01111111 127 127
(second) - 10000000 - 128 - -128
========== ===== ======
11111111 255 -1
1 => borrow flag
1 => signed overflow flag
The unsigned computation 127 - 128 => 255 is wrong, but the signed computation 127 - -128 => -1 is also wrong. So the borrow flag and the signed overflow flag are both one. The correct signed answer is 255, which is outside the -128..127 range of a signed 8-bit value. A 16-bit computation would produce the correct signed answer.
(borrow) 1111111111000000 unsigned signed
(first) 0000000001111111 127 127
(second) - 1111111110000000 - 128 - -128
================== ===== ======
0000000011111111 255 255
1 => borrow flag
0 => signed overflow flag
Signed overflow Edit
The previous section has examples of signed overflow, but does not answer how to set the signed overflow flag.
The wiki page for addition enumerated the eight possible cases, and concluded with a rule to check the last two carry bits. We now repeat the analysis with subtraction, and find the same answer.
There are two ways for subtraction to cause signed overflow.
- A positive number minus a negative number yields a negative number. (The correct answer is positive.)
- A negative number minus a positive number yields a positive or zero answer. (The correct answer is negative.)
These are the eight possible cases, including the two cases that cause signed overflow. (Pretend that zero is also "positive" during these cases.) These use the eight possible permutations of the second-last borrow bit and the two sign bits (of the two operands of subtraction).
(borrow) 00 (borrow) 10
(first) 0nnn positive (first) 0nnn positive
(second) - 0nnn positive (second) - 1nnn negative
=============== ===============
0nnn positive 1nnn negative
0 => borrow 1 => borrow
0 => signed overflow 1 => signed overflow
(borrow) 00 (borrow) 00
(first) 1nnn negative (first) 1nnn negative
(second) - 0nnn positive (second) - 1nnn negative
=============== ===============
1nnn negative 0nnn positive
0 => borrow 0 => borrow
0 => signed overflow 0 => signed overflow
(borrow) 11 (borrow) 11
(first) 0nnn positive (first) 0nnn positive
(second) - 0nnn positive (second) - 1nnn negative
=============== ===============
1nnn negative 0nnn positive
1 => borrow 1 => borrow
0 => signed overflow 0 => signed overflow
(borrow) 01 (borrow) 11
(first) 1nnn negative (first) 1nnn negative
(second) - 0nnn positive (second) - 1nnn negative
=============== ===============
0nnn positive 1nnn negative
0 => borrow 1 => borrow
1 => signed overflow 0 => signed overflow
Notice that when the last two borrow bits are equal, then signed overflow never happens; but when the last two borrow bits are not equal, then signed overflow always happens. The processors must follow this rule (or an equivalent rule) to to set or clear the signed overflow flag.
