Department of Computer Science         Complements in Radix r

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 (rn - 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 rn - 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 = 26 + 24 + 22 = 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 carry-out, this carry is discarded.

+6

0000 0110

 

-6

  1111 1010

+12

0000 1100

 

+12

  0000 1100

+18

0001 0010

 

+6

10000 0110

 

 

 

 

 

+6

0000 0110

 

-6

  1111 1010

-12

1111 0100

 

-12

  1111 0100

-6

1111 1010

 

-18

11110 1110

The carry-in carry-out rule: In order to determine whether or not an overflow condition has occurred we check the carry-in to the high order bit against the carry-out of the high order bit. Using 2's complement, there has not been an overflow if when there is a carry-in to the high order bit there is also a carry-out and if there is no carry-in to the high order bit there can be no carry-out. 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

Back by J. A. Tompkins tompkinsj@uncw.edu