Binary Arithmetic -- Negative numbers and Subtraction
Binary Mathematics Binary Addition: this is performed using the same rules as decimal except all numbers are limited to combinations of zeros (0) and ones (1). Using 8-bit numbers
1 11
0000 11102 which is 1410 + 0000 01102 which is + 610 -----------------------------0001 01002 2010
Not all integers are positive.
What about negative numbers? What if we wanted to do: So, : 1410 + ( - 210) = 1210 1410 - ( + 210) = 1210
1410 + ( - 210) = 1210
1410 - 210 -----1210
This example is a deceptively easy because while there no need to borrow. Lets look at another example:
1 13
1 2 310 - 1 910
------------
1 0 410
If we are using a paper and pencil, binary subtraction can be done using the same principles as decimal subtraction. Binary Subtraction: Use standard mathematical rules: 0000 11102 which is which is 1410
- 0000 01102
0000 10002 ----------------810
- 610
-----------
This is rather straightforward. In fact no borrowing was even required in this example.
Try this example:
1 0 10 10 10
0 0 0 1 1 0 0 12 2510 - 0 0 0 0 1 1 1 02 - 1410 -------------------- ----------0 0 0 0 1 0 1 12 1110
THIS WAS PAINFUL!
When so much borrowing is involved the problem is very error prone. Not only was the example above complex because of all the borrowing required but computers have additional problems with signed or negative numbers. Given the nature of the machine itself, how do we represent a negative number? What makes this even worse is that computers are fixed-length or finite-precision machines. There are two common ways to represent negative numbers within the computer. Remember, the minus sign does not exist. The computer world is made up entirely of zeros (0) and ones (1). These two techniques are called signed magnitude representation and twos complement. Lets explore sign-magnitude representation first. In the sign-magnitude number system, the most significant bit, the leftmost bit, holds the sign (positive or negative). A zero (0) in that leftmost bit means the number is positive. A one (1) in that leftmost bit means the number is negative. Step 1: Decide how many bits the computer has available for your operations. Remember computers are fixed-length (or finite-precision) machines. For example: if we use 4-bits, the leftmost bit is the sign bit and all the rest are used to hold the binary numbers. In a 4-bit computer world, this leaves only 3 bits to hold the number. This limits our numbers to only very small ones. A 4-bit number would look like XXXX the left-most bit is considered the sign bit | This is the sign bit Using four bits, these are the ONLY binary numbers a computer could represent. 0 1 2 3 4 5 6 7 0000 0001 0010 0011 0100 0101 0110 0111
-1 -2 -3 -4 -5 -6 -7
1001 1010 1011 1100 1101 1110 1111
If we were using 8-bits the left-most bit will contain the sign. This would leave 7 bits to hold the number. XXXX XXXX | This is the sign bit
This sign bit is reserved and is no longer one of the digits that make up the binary number. Remember if the sign bit is zero (0) the binary number following it is positive. If the sign bit is one (1) the binary number following it is negative. Using the sign-magnitude system the largest positive number that can be stored by an 8-bit computer is:
Sign
(64) (32) (16)
(8)
(4)
(2)
(1)
+ 12710
This is: 64 + 32 + 16 + 8 + 4 + 2 + 1 = 12710 If there were a one (1) in the first bit, the number would be equal to - 12710
Sign
(64) (32) (16)
(8)
(4)
(2)
(1)
- 12710
Over time it has become obvious that a system that even further reduces the number of available bits while meaningful, is not especially useful. Then of course there is still the problem of how to deal with these positive and negative numbers. While this representation is simple, arithmetic is suddenly impossible. The standard rules of arithmetic dont apply. Creating a whole new way to perform arithmetic isnt overly realistic. Fortunately another technique is available.
Twos Complement
Twos complement is an alternative way of representing negative binary numbers. This alternative coding system also has the unique property that subtraction (or the addition of a negative number) can be performed using addition hardware. Architects of early computers were thus able to build arithmetic and logic units that performed operations of addition and subtraction using only adder hardware. (As it turns out since multiplication is just successive addition and division is just successive subtraction it was possible to use simple adder hardware to perform all of these operations. Lets look at an example:
1410 - 610 = 1410 + (- 610) = 810
Well first need to figure out how to write numbers in the 2s complement form? An 8-bit positive number in 2s complement form,
Sign (64) (32) (16)
(8)
(4)
(2)
(1)
An 8-bit negative numbers in 2s complement form,
Sign (?)
(?)
(?)
(?)
(?)
(?)
(?)
O.K. Then, 1410 is: 0 0 0 0 1 1 1 0, but what about -610?
Negative numbers in the 2s complement form need to be obtained by: (1) Finding its corresponding positive number (+6 is: 0 0 0 0 0 1 1 0) (2) Flip all digits (10, 01):
00000110 11111001
(3) Add 1 to the flipped number:
11111001 +) 0 0 0 0 0 0 0 1 --------------------------1 1 1 1 1 0 1 0 this is the 2s complement representation for -610
Therefore, since
1410 - 610 = 1410 + (- 610)
we simply do:
1 1 1 1 1 1
0 0 0 0 1 1 1 02 +)1 1 1 1 1 0 1 02 --------------------------1 0 0 0 0 1 0 0 02 |
th
1410 +) -610 ---------810
Overflow (9 bit in our 8-bit system), IGNORE! It is always a good habit to examine if the answer we obtained (000010002) is correct. We do so by converting it back to decimal numbers and check if its indeed 810.
Example 1: 1210 - 910 = 310 Or 1210 + (-910) = 310
Step 1: Determine the 2s complement form for the numbers:
1210 = 000011002
Finding -910 would require the following three steps: (1) Finding -910s corresponding positive number (+910 is: 0 0 0 0 1 0 0 1) (2) Flip all digits (10, 01):
00001001 11110110
(3) Add 1 to the flipped number:
11110110 +) 0 0 0 0 0 0 0 1 --------------------------1 1 1 1 0 1 1 1 this is the 2s complement form for -910
Step 2: Add the numbers together.
11 1 1
1210 + (-910) -------------310
| IGNORE Overflow
0000 11002 + 1111 01112 -----------------------1 0000 00112 this is the positive number 3
IT Worked! Example 2: 2510 - 1410 = 1110
Or
2510 + (-1410) = 1110
Step 1: Determine the 2s complement form for the numbers:
2510 = 000110012
Finding -1410 would require the following three steps: (1) Finding -1410s corresponding positive number (+1410 is: 0 0 0 0 1 1 1 0) (2) Flip all digits (10, 01):
00001110 11110001
(3) Add 1 to the flipped number:
11110001 +) 0 0 0 0 0 0 0 1 --------------------------1 1 1 1 0 0 1 0 this is the 2s complement form for -1410
Step 2: Add the numbers together.
111
2510 + (-1410) -------------1110
| IGNORE Overflow
0001 10012 + 1111 00102 -----------------------1 0000 10112 this is the positive number 11
IT Worked!
Example 3: 910 - 1410 Or 910 + (-1410)
Step 1: Determine the 2s complement form for the numbers:
910 = 000010012
Finding -1410 would require the following three steps: (1) Finding -1410s corresponding positive number (+1410 is: 0 0 0 0 1 1 1 0) (2) Flip all digits (10, 01):
00001110 11110001
(3) Add 1 to the flipped number:
11110001 +) 0 0 0 0 0 0 0 1 --------------------------1 1 1 1 0 0 1 0 this is the 2s complement form for -1410
Step 2: Add the numbers together.
910 + (-1410) --------------510
0000 10012 + 1111 00102 -----------------------1111 10112
Ugh Since the answer starts with a 1 in its sign bit, it is a negative number. However, since there is no direct meaning for each digit for a negative 2s complement number, well need to find its corresponding positive number in order to find out: (Note that we do the flipping/adding 1 thing to convert any positive 2s complement number to its corresponding negative number and vice versa):
1111 10112 flip all digits: 0000 01002 add 1 +) 0000 00012 --------------------0000 01012
this is +510 indeed, therefore 1111 10112 = -510
Example 5: -25 + 18
Step 1: Determine the 2s complement form for the numbers:
1810 = 000100102
Finding -2510 would require the following three steps: (1) Finding -2510s corresponding positive number (+2510 is: 0 0 0 1 1 0 0 1) (2) Flip all digits (10, 01):
00011001 11100110
(3) Add 1 to the flipped number:
11100110 +) 0 0 0 0 0 0 0 1 --------------------------1 1 1 0 0 1 1 1 this is the 2s complement form for -2510
Step 2: Add the numbers together.
11
(-2510) + 1810) --------------710
1110 01112 + 0001 00102 -----------------------1111 10012
Ugh Since the answer starts with a 1 in its sign bit, it is a negative number. However, since there is no direct meaning for each digit for a negative 2s complement number, well need to find its corresponding positive number in order to find out: (Note that we do the flipping/adding 1 thing to convert any positive 2s complement number to its corresponding negative number and vice versa):
1111 10012 flip all digits: 0000 01102 add 1 +) 0000 00012 --------------------0000 01112
this is +710 indeed, therefore 1111 10012 = -710