Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: UNCW Home

Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: UNCW Home

 CSC 133 - Discrete Mathematical Structures

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:

The r's complement of a is defined as rn - a.

To convert a number to its r's complement we use the definition, the complement of a is defined as rn  - 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 103 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 = 26 + 24 + 22 = 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 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
Base Conversion
Primitive Data Types:  Integers Reals Practice

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