Diminished Radix and One’s Complement Explained

This article explores how the mathematical framework of the diminished radix complement establishes the operational mechanics of one’s complement in binary arithmetic. It covers the core mathematical definition, explains why bit inversion occurs naturally within the binary base, and examines key arithmetic behaviors such as the end-around carry and the dual representation of zero.

Mathematical Definition of Diminished Radix Complement

In number theory, the diminished radix complement of an \(n\)-digit integer \(N\) in a base (radix) \(r\) is defined by the formula:

\[\text{Complement}(N) = (r^n - 1) - N\]

In the binary system, the base is \(r = 2\). Consequently, the diminished radix is \(r - 1 = 2 - 1 = 1\), which gives the system its common name: one’s complement. For an \(n\)-bit binary number, the formula simplifies to:

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

The Origin of Bit Inversion

The term \((2^n - 1)\) represents the maximum unsigned value that can be stored in \(n\) bits, which always equates to a string of \(n\) ones (\(111\dots1_2\)).

When computing \((2^n - 1) - N\), each individual bit \(b_i\) of \(N\) is subtracted from \(1\): - If \(b_i = 0\), then \(1 - 0 = 1\). - If \(b_i = 1\), then \(1 - 1 = 0\).

Because there is never a need to borrow across columns, this subtraction operates independently on each bit position. As a direct consequence of the diminished radix formula, the mathematical complement of a binary number is identical to the logical bitwise NOT operation.

End-Around Carry Mechanics

The diminished radix framework operates under modulo \((2^n - 1)\) arithmetic rather than modulo \(2^n\). When two numbers are added and generate a carry-out from the most significant bit (MSB), that carry represents a value of \(2^n\).

In standard modular arithmetic base \((2^n - 1)\):

\[2^n \equiv 1 \pmod{2^n - 1}\]

Because the carry-out value of \(2^n\) is congruent to \(1\), the discarded overflow bit must be added back to the least significant bit (LSB) of the intermediate sum. This requirement is known as the end-around carry, and it ensures that the arithmetic result remains consistent with the underlying diminished radix modulus.

Representation of Negative Numbers and Dual Zero

Using one’s complement allows signed numbers to be manipulated using standard adder circuits. A positive number begins with a sign bit of 0, while its negative counterpart is formed by taking its diminished radix complement, changing the sign bit to 1.

A notable byproduct of the \((2^n - 1) - N\) formula is the existence of two representations for zero: - Positive Zero (\(+0\)): Represented as all zeros (\(000\dots0_2\)). - Negative Zero (\(-0\)): Represented as all ones (\(111\dots1_2\)), which is \((2^n - 1) - 0\).

Both values satisfy the definition of zero within the diminished radix structure, reflecting the symmetrical range of \(- (2^{n-1} - 1)\) to \(+ (2^{n-1} - 1)\).