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:
To convert a number to its r's complement, first convert it to its (r  1)'s complement, then add 1. Given a number a in radix r having n digits, the (r  1)'s complement of a is defined as (r^{n}  1)  a. For decimal numbers r = 10 and r  1 = 9. The 9's complement of 897 is obtained by subtracting each digit from 9, which gives us 102.
The r's complement of a is defined as r^{n}  a. Looking closely at the definition of (r  1)'s complement we see that to obtain the r's complement we need only add 1 to the (r  1)'s complement. The r's complement of 897 is then 102 + 1 = 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 as 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 java 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. In the previous example we first converted the number to its (r  1)'s complement then added 1 to get its r's complement. We can repeat that process here, we get 1's complement by inverting all bits. The 1's complement of 1010 1100 is then 0101 0011, adding 1 to get the 2's complement we have 0101 0011 + 1 = 0101 0100 = 2^{6} + 2^{4} + 2^{2} = 84. But 1010 1100 is negative, we have 84.
A much faster 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  Euclid's Division Algorithm  Base Conversion  
Java Primitive Data Types:  Integers  Reals  Homework 