Radix Complement and Twos Complement in Binary

This article explains how the mathematical framework of the radix complement generalizes to establish the two’s complement system in digital computing. By defining complement arithmetic in an arbitrary base \(b\), we demonstrate how setting the base to 2 naturally yields the standard two’s complement representation, enabling seamless arithmetic operations and negative number representation in binary hardware.

The Mathematical Definition of Radix Complement

In positional numeral systems, the radix complement provides a method to represent negative numbers and perform subtraction using only addition circuitry. For an \(n\)-digit number \(N\) in base (radix) \(b\), the radix complement is mathematically defined as:

\[\text{Radix Complement}(N) = b^n - N\]

This operation relies on modular arithmetic. In an \(n\)-digit fixed-width register, values wrap around at modulo \(b^n\). Subtracting a number \(N\) from another number \(M\) can be rewritten as adding the complement of \(N\):

\[M - N \equiv M + (b^n - N) \pmod{b^n}\]

When the sum exceeds \(b^n - 1\), the carry-out value of \(b^n\) is naturally discarded by the fixed-width register, leaving the exact result of \(M - N\).

Specializing to Binary: Deriving Two’s Complement

Two’s complement is the specific instance of the radix complement where the base is binary (\(b = 2\)). For an \(n\)-bit binary integer \(N\), the radix complement formula becomes:

\[\text{Two's Complement}(N) = 2^n - N\]

In an 8-bit system (\(n = 8\)), the base power is \(2^8 = 256\). The two’s complement of a number \(N\) is therefore \(256 - N\). If \(N = 6\) (00000110 in binary), its two’s complement is \(256 - 6 = 250\) (11111010 in binary), which represents \(-6\) in signed 8-bit arithmetic.

Relationship with Diminished Radix Complement

Calculating \(b^n - N\) directly requires borrowing across multiple digits. To simplify this, the radix complement can be rewritten using the diminished radix complement:

\[b^n - N = ((b^n - 1) - N) + 1\]

In any base, \((b^n - 1)\) consists of \(n\) repetitions of the largest digit in that base (\(b - 1\)). In base 2: 1. \((2^n - 1)\) produces a sequence of \(n\) ones (e.g., 11111111 for \(n=8\)). 2. Subtracting any binary number \(N\) from all ones reverses every bit (\(1 - 0 = 1\) and \(1 - 1 = 0\)). This step is the diminished radix complement, commonly known as the one’s complement or bitwise NOT (\(\sim N\)). 3. Adding \(1\) to the result completes the radix complement calculation:

\[\text{Two's Complement}(N) = (\sim N) + 1\]

This formulation eliminates the need for multi-digit subtraction, allowing hardware to compute the radix complement by applying a simple bitwise NOT gate followed by an increment by one.

Architectural Advantages in Binary Systems

Generalizing the radix complement to base 2 provides distinct operational advantages for digital systems:

• Unified Arithmetic: Addition and subtraction use the same physical adder circuits, as negation is handled by complementation.
• Single Zero Representation: Unlike one’s complement (which has both \(+0\) and \(-0\)), two’s complement produces a single unique representation for zero (\(2^n \pmod{2^n} = 0\)).
• Sign Identification: The most significant bit (MSB) automatically acts as the sign bit, where 0 denotes positive values and 1 denotes negative values.