CSC
133  Discrete Mathematical Structures 
Complements can be used to simplify the subtraction process. Consider the following decimal (radix 10) subtraction
950
897
+053
Clearly the solution is +53. But the process of subtracting 897 from 950 step by step is tedious. First the 7 can't be subtracted from the 0 so we borrow ten from the 5 and subtract 7 from 10 to get 3. Next, the 9 can't be subtracted from the 4 so we borrow ten from the 9 to get 14 and take away 9 to get 5. Next we subtract 8 from 8 and get 0. Now we must decide whether our solution is positive or negative. We do this by determining the larger of the minuend or subtrahend and use the sign of the larger in our solution.
An alternative way of subtracting is to translate the subtrahend into its r's complement form and add the two numbers. The advantages of using r's complement include:
The r's complement of a is defined as r^{n}  a.
To convert a number to its r's complement we use the definition, the complement of a is defined as r^{n}  a. For decimal numbers r = 10 and for this example let's have n be 3 so, complement of 897 is obtained by subtracting from 10^{3} or 1,000, which gives us 103.
The r's complement of 897 is then 103. Consider again the subtraction problem, this time applying r's complement to the subtrahend and adding instead of subtracting:
950
+103
1053
The final carry is discarded and the result is the 3 digit answer we expected.
Now consider the radix 2. We have 1's and 2's complements. First we must specify the length of the word to be used. In Java for example, the byte data type uses 8 bits and the integer uses 32 bits. The high order bit indicates the sign, 1 is negative, 0 is positive. If a number is negative, we apply 2's complement to read the positive value and assign a negative sign. When adding or subtracting two numbers the solution always gets the correct sign in 2's complement form. To subtract, just apply 2's complement to the subtrahend and add.
Consider the byte 1010 1100, this is a negative number since its high order bit is 1. To determine its numerical value we apply 2's complement to read the positive value and assign a negative sign. To get the 2's complement we copy from the least bit up to and include the first 1 bit then invert the rest which gives us 0101 0100 = 2^{6} + 2^{4} + 2^{2} = 84. But 1010 1100 is negative, we have 84.
A fast algorithm for applying 2's complement is to copy every digit from the low order bit up to and including the first 1, then invert all the rest of the bits including the high order bit. Using this fast conversion, 1010 1100 can be converted by copying down the first three digits and inverting the rest. We have 0101 0100, as before. Note how addition using 2's complement works for various combinations of 6 and 12 below, where negative numbers are given in 2's complement form and if the answer is negative it is again given in 2's complement. Also note that in each case the operation performed is addition and that in the event of a high order bit carryout, this carry is discarded.
+6 
0000 0110 

6 
1111 1010 
+12 
0000 1100 

+12 
0000 1100 
+18 
0001 0010 

+6 






+6 
0000 0110 

6 
1111 1010 
12 
1111 0100 

12 
1111 0100 
6 
1111 1010 

18 

The carryin carryout rule: In order to determine whether or not an overflow condition has occurred we check the carryin to the high order bit against the carryout of the high order bit. Using 2's complement, there has not been an overflow if when there is a carryin to the high order bit there is also a carryout and if there is no carryin to the high order bit there can be no carryout. An overflow condition has occurred when the final answer is in error due to the size of the resultant being too large to represent with the available bits (including the sign bit).
Number Systems  Base Conversion  
Primitive Data Types:  Integers  Reals  Practice 