Complements in Digital Computers

Complements are essential in digital computers for simplifying subtraction operations and performing logical manipulations. In any base $r$ system, there are two types of complements: the $r$'s complement and the $(r-1)$'s complement. These complements play a significant role in computer arithmetic.

9's Complement and 1's Complement

Definition

Given a number $N$ in base $r$ with $n$ digits, the $(r-1)$'s complement of $N$ is defined as:

$(r^n - 1) - N$

For decimal numbers, $r = 10$ and $r-1 = 9$, so the 9's complement of $N$ is:

$10^n - 1 - N$

Here, $10^n$ represents a number that consists of a single 1 followed by $n$ zeros. For example, with $n = 4$, $10^4 = 10000$ and $10^4 - 1 = 9999$. Therefore, the 9's complement of a decimal number is obtained by subtracting each digit from 9.

Example

• The 9's complement of 5467 is:

  $9999 - 5467 = 4532$

• The 9's complement of 12389 is:

  $99999 - 12389 = 87610$

Generalization to Other Bases

For octal (base 8) and hexadecimal (base 16) numbers, the $(r-1)$'s complement is obtained by subtracting each digit from 7 or 15 (F in hexadecimal), respectively.

10's Complement and 2's Complement

Definition

The $r$'s complement of an $n$-digit number $N$ in base $r$ is defined as:

$r^n - N \text{ for } N \neq 0$ $0 \text{ for } N = 0$

This can be viewed as adding 1 to the $(r-1)$'s complement:

$r^n - N = [(r^n - 1) - N] + 1$

Thus, the 10's complement of the decimal number 2389 is:

$7610 + 1 = 7611$

Similarly, the 2's complement of the binary number 1010 is:

$0101 + 1 = 0110$

Alternative Formation

For forming the $r$'s complement of $N$, you can leave all the least significant zeros unchanged, subtract the first non-zero least significant digit from $r$, and then subtract all higher significant digits from $r-1$.

Example

• The 10's complement of 246700 is obtained by leaving the two zeros unchanged, subtracting 7 from 10, and subtracting the other three digits from 9:

  $753300$

• The 2's complement of the binary number 11001100 is obtained by leaving the two low-order 0's and the first 1 unchanged, then flipping the other bits:

  $00110100$

Subtraction Using Complements

General Procedure

To subtract two $n$-digit unsigned numbers $M$ and $N$ in base $r$:

1. Add the minuend $M$ to the $r$'s complement of the subtrahend $N$:

   $M + (r^n - N) = M - N + r^n$

2. Discard the end carry $r^n$:

   • If $M \geq N$, the sum will produce an end carry $r^n$, which is discarded, and the result is $M - N$.

   • If $M < N$, the sum does not produce an end carry. The result is $r^n - (N - M)$, which is the $r$'s complement of $N - M$. To obtain the answer in a familiar form, take the $r$'s complement of the sum and place a negative sign in front.

Example

• Subtraction with $M \geq N$:

  $72532 - 13250$

  • 10's complement of 13250 is 86750.

  • Add:

    $72532 + 86750 = 159282$

  • Discard the end carry:

    $159282 - 100000 = 59282$

• Subtraction with $M < N$:

  $13250 - 72532$

  • 10's complement of 72532 is 27468.

  • Add:

    $13250 + 27468 = 40718$

  • Result is negative since there is no end carry. The 10's complement of 40718 is 59282:

    $\text{Answer: } -59282$

Binary Subtraction

Using 2's complement for binary subtraction follows the same principles:

• Example: $X - Y$ and $Y - X$

  • Let $X = 1010100$ and $Y = 1000011$.

  • 2's complement of $Y$ is $0111101$.

  • Add:

    $1010100 + 0111101 = 10010001$

  • Discard the end carry:

    $0010001 \text{ (No end carry, result is positive)}$

  • For $Y - X$:

    • 2's complement of $X$ is $0101100$.

    • Add:

      $1000011 + 0101100 = 1101111$

    • No end carry, result is negative. The 2's complement of 1101111 is 0010001:

      $\text{Answer: } -0010001$

Handling Radix Points

When numbers contain a radix point, temporarily remove it to form the $r$'s or $(r-1)$'s complement. Restore the radix point in the complemented number at the same relative position.

Complement of the Complement

The complement of the complement restores the original number. The $r$'s complement of $N$ is $r^n - N$. The complement of the complement is:

$r^n - (r^n - N) = N$

Subtraction of Unsigned Numbers

The direct method of subtraction using the borrow concept is less efficient in digital hardware compared to using complements. By adding the minuend $M$ to the $r$'s complement of the subtrahend $N$, we can simplify subtraction significantly.

Procedure Summary

1. Add $M$ to the $r$'s complement of $N$.
2. Discard the end carry if present.
3. If no end carry, the result is the $r$'s complement of the difference, with a negative sign.

This method is highly efficient and preferred for binary arithmetic in digital systems.