Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 57 ยท Digital Foundations

Complement Arithmetic: 1's Complement, BCD and Excess-3 Addition

Subtract with complements and an end-around carry, then add and subtract decimal digits in BCD and excess-3 with runnable Python models of the correction logic.

Computers rarely contain a dedicated subtractor. They subtract by adding a complement, which lets one adder circuit serve both jobs. You have already met two's complement, the winner of that design contest, and you have seen that BCD and excess-3 store decimal digits in four bits. This lesson goes one level deeper. It explains the general idea behind every complement system, shows how 1's complement subtraction works with its quirky end-around carry, and then applies the same trick to decimal digits, which is how a hardware BCD or excess-3 calculator works.

Understanding these old-fashioned schemes is not only history. Decimal arithmetic is still used in financial hardware and in pocket calculators, and the "add a correction, then fix the carry" pattern appears again and again in digital design.

The complement idea

For a number system with base r and n digits, there are two natural complements of a number N:

  • The (r-1)'s complement: (r^n - 1) - N. In binary that is the 1's complement, in decimal the 9's complement. Every digit is replaced by (r-1) minus that digit, so no carries are needed at all.
  • The r's complement: r^n - N, which is the (r-1)'s complement plus 1. In binary that is the 2's complement, in decimal the 10's complement.

Subtraction A - B becomes A + complement(B) plus a small fix-up. The fix-up differs between the two kinds of complement, and that is what makes them behave differently.

(r-1)'s complement (1's, 9's) r's complement (2's, 10's)
Making it Flip every digit, no carries Flip every digit, then add 1
Carry out of the top digit Add it back at the bottom (end-around carry) Throw it away
Zeros Two (all zeros and all r-1) One
Negative result Complement of the sum, no carry out Complement of the sum plus 1

1's complement subtraction

To compute A - B in n bits, add the 1's complement of B to A. Look at the carry that leaves the top bit:

  • Carry out = 1: the answer is positive. Add that carry back into the lowest bit. This is the end-around carry.
  • Carry out = 0: the answer is negative. Its magnitude is the 1's complement of the sum.

Why does it work? The 1's complement of B is (2^n - 1) - B, which is one less than the true negative of B in a modulo 2^n world. Adding A gives A - B + 2^n - 1. When A >= B, the carry out removes 2^n and leaves A - B - 1, so you add the carry back to fix the missing 1. When A < B, there is no carry and the sum is 2^n - 1 - (B - A), which is exactly the 1's complement of the magnitude B - A.

flowchart LR
    A["A and B"] --> N["Invert B bit by bit"]
    N --> S["Binary adder: A + (not B)"]
    S --> C{"Carry out?"}
    C -- "1" --> E["Add the carry back (end-around). Result is positive"]
    C -- "0" --> F["Invert the sum. Result is negative"]

The decision after the adder is the only difference from two's complement.

The end-around carry is a second addition, so hardware needs either a second pass through the adder or a feedback wire into the carry input. This extra cost, plus the two zeros, is why two's complement replaced 1's complement in almost every machine.

Python Subtracting with a 1's complement adder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The case 5 - 5 shows the oddity. The sum is 1111, which is "negative zero". The program turns it into the integer 0, but real hardware sees two different patterns, so it must treat 0000 and 1111 as equal when comparing.

Decimal subtraction with 9's complement

The same method works in decimal, and it is how mechanical adding machines subtracted. Compute 7314 - 2859:

  1. 9's complement of 2859: replace each digit d by 9 - d, giving 7140.
  2. Add: 7314 + 7140 = 14454. There is a carry out of the fourth digit.
  3. End-around carry: 4454 + 1 = 4455. That is the correct answer.

If the carry were 0, the answer would be negative and you would take the 9's complement of the sum. A decimal calculator needs a decimal adder and a way to produce the 9's complement of a digit. The code you choose for the digit decides how hard that second part is.

BCD addition, once more with feeling

BCD stores each decimal digit as its plain binary value, 0000 to 1001. A 4-bit binary adder sums two digits plus a carry-in. The raw sum can be 0 to 19. If it is above 9, or if the adder produced a carry, the nibble is not a valid digit and you add 0110 (6) to skip the six unused codes and generate the decimal carry. The correction condition is carry OR (S3 AND S2) OR (S3 AND S1), because every nibble from 1010 to 1111 has bit 3 set together with bit 2 or bit 1.

The 9's complement of a BCD digit is 9 - d, which has no simple bit pattern (0 -> 1001, 1 -> 1000, 2 -> 0111...). A BCD subtractor needs a small logic block for it. This is the weakness that excess-3 solves.

Excess-3: the self-complementing code

Excess-3 stores each digit d as d + 3. The digit 0 is 0011 and the digit 9 is 1100. The codes 0000, 0001, 0010, 1101, 1110 and 1111 are unused. Excess-3 is self-complementing: the 9's complement of a digit is found by inverting its four bits. Check: the digit 2 is 0101, and inverted it is 1010, which is the digit 7, and 9 - 2 = 7. In general (9 - d) + 3 = 15 - (d + 3), which is the bitwise inverse of d + 3 in 4 bits.

Excess-3 addition also has a very simple correction. The raw binary sum of two codes is a + b + 6, because each code carries a surplus of 3.

  • If the digit sum a + b is 10 or more, the raw sum is 16 or more, so the adder produces a carry and the low nibble is a + b - 10. That nibble is short of excess-3 form by 3, so add 3 to it.
  • Otherwise the raw nibble is a + b + 6, which is 3 too large, so subtract 3 from it.

The carry out of the adder selects the correction, and adding 3 or subtracting 3 is a second small adder with the constant 0011 or 1101.

Python Excess-3 digit adder and a decimal subtractor

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The subtractor never needs a lookup table for the 9's complement. It only inverts bits, exactly what a handful of NOT gates can do. That is the practical beauty of excess-3.

Modern CPUs do not use any of these decimal codes in their ALU. They compute in two's complement and treat decimal as a software or library problem. Decimal hardware survives in calculators, in some financial processors, and in the decimal floating-point formats of the IEEE 754 standard.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In 1's complement subtraction, the adder produces a carry out of the top bit. What do you do?

    A carry out means the result is positive, and the end-around carry corrects the missing 1 caused by using (2^n - 1) - B instead of 2^n - B.
  2. 2. Compute 6 - 2 in 4-bit 1's complement. What is the pattern after the end-around carry?

    6 is 0110 and the complement of 2 (0010) is 1101. The sum is 1 0011. Adding the carry back gives 0011 + 1 = 0100, which is 4.
  3. 3. Why is excess-3 convenient for decimal subtraction?

    Excess-3 is self-complementing: (9 - d) + 3 equals 15 - (d + 3), the bitwise inverse of d + 3.
  4. 4. Two excess-3 digits are added and the 4-bit adder produces a carry out. What correction is applied to the low nibble?

    A carry means the digit sum was 10 or more. The low nibble then equals the sum minus 10, which is 3 short of excess-3 form, so 3 is added.

Summary

  • A (r-1)'s complement (1's, 9's) is made digit by digit with no carries. An r's complement (2's, 10's) is that plus 1.
  • 1's complement subtraction adds the inverted subtrahend. A carry out is added back at the bottom (end-around carry) and means a positive result. No carry means a negative result, the complement of the sum.
  • 1's complement has two zeros and needs the end-around step, which is why two's complement won.
  • BCD addition corrects any nibble above 9 (or with a carry) by adding 6.
  • Excess-3 is self-complementing, so decimal subtraction needs only inverters, and its adder correction is "add 3 if there was a carry, otherwise subtract 3".

Next, start building circuits with the basic logic gates.