Lecture Notes: Complement Systems for Numbers

Introduction

• Complement systems are a method of representing numbers within a fixed numerical range.
• The system divides the range into positive and negative numbers, simplifying subtraction and operations with negative numbers.
• Complements work similarly to an odometer, rolling over when decreasing through zero.

Basics of Complement Systems

• A fixed range of digits is necessary (e.g., 3-digit, 5-digit numbers).
• Key formula: Base^digits - n, where:
  • Base is the numerical base (10 for decimal, 2 for binary).
  • Digits are the fixed number of digits.
  • n is the number to represent negatively.

Example in Base 10

• Given 3-digit numbers, find the complement of 370:
  • Calculate 10^3 = 1000.
  • Subtract n (370) from this base: 1000 - 370 = 630.
  • Thus, 630 represents -370 in this system.
• Numbers cross over to negative halfway through the range, e.g., 500 is positive, 501 is negative.

Benefits of Complement Systems

• Simplify subtraction by allowing addition operations instead.
• Example: 450 - 370 using complements:
  • 450 + (-370) becomes adding 450 + 630.
  • Result is 1080, discard overflow digit, final result is 80.

Binary Complement Systems

• Works similarly in binary (base 2).
• Use a word size, such as 6 bits.
• Example: negative 8 in 6-bit system:
  • Positive 8 = 001000.
  • Calculate 2^6 = 64.
  • Subtract to find complement: 64 - 8.
  • Alternatively, flip bits and add 1 for simplicity.

Two's Complement System

• Solves algorithmic complexity by using existing addition circuitry.
• Flip bits and add 1 to find the complement.
• Ensures no negative zero by defining zero's complement as zero.

Overflow in Complement Systems

• Occurs when addition results exceed the representable range.
• Example: adding two large numbers like 500 + 500 results in overflow to zero.
• Overflow can cause security vulnerabilities.

Conclusion

• Complement systems simplify operations with negative numbers, especially in digital circuits.
• Binary systems (e.g., Two's Complement) offer efficient ways to handle negative values without additional circuitry.
• Overflow is a crucial consideration in designing systems using complement representations.