Why Every Integer Has a Unique Binary Representation

Every non-negative integer maps to exactly one representation in the standard positional binary (base-2) system. This fundamental property of computer science and mathematics rests on two mathematical guarantees: existence, which ensures every non-negative integer can be expressed as a sum of distinct powers of two, and uniqueness, which ensures that no two different bit sequences represent the same number. Together, these principles allow modern computing systems to reliably store, process, and retrieve numerical data without ambiguity.

Understanding the Positional Binary System

In a positional numeral system with base \(b = 2\), any number is represented by a sequence of digits (bits) \(d_k d_{k-1} \dots d_1 d_0\), where each digit \(d_i \in \{0, 1\}\).

The mathematical value \(N\) of this sequence is defined as:

\[N = \sum_{i=0}^{k} d_i \cdot 2^i = d_k 2^k + d_{k-1} 2^{k-1} + \dots + d_1 2^1 + d_0 2^0\]

To establish that this system works for all non-negative integers without ambiguity, we must prove both existence and uniqueness.

Existence: Why Every Integer Can Be Represented

The existence of a binary representation for any non-negative integer is guaranteed by the Division Algorithm.

For the base case, the integer \(0\) is simply represented as \(0\) (or an empty sum of powers).

For any positive integer \(N\), dividing by \(2\) produces an integer quotient \(Q_0\) and a remainder \(R_0\):

\[N = 2 \cdot Q_0 + R_0, \quad \text{where } R_0 \in \{0, 1\}\]

The remainder \(R_0\) determines the least significant bit (\(d_0\)). Repeating this process with the quotient \(Q_0\):

\[Q_0 = 2 \cdot Q_1 + R_1, \quad \text{where } R_1 \in \{0, 1\}\]

Because each quotient is strictly smaller than the previous one (\(N > Q_0 > Q_1 > \dots\)), the sequence of quotients must eventually reach \(0\). When \(Q_k = 0\), the process terminates, yielding a finite sequence of binary digits \((R_k, R_{k-1}, \dots, R_1, R_0)\) such that:

\[N = R_k 2^k + R_{k-1} 2^{k-1} + \dots + R_1 2^1 + R_0 2^0\]

Because the Division Algorithm works for any positive integer, every non-negative integer is guaranteed to have a binary representation.

Uniqueness: Why Only One Representation Exists

To understand why no integer has two distinct binary representations (ignoring leading zeros), we look at the geometric sum property of powers of two.

The sum of all powers of two from \(2^0\) up to \(2^{k-1}\) is strictly less than the next power of two, \(2^k\):

\[\sum_{i=0}^{k-1} 2^i = 2^0 + 2^1 + 2^2 + \dots + 2^{k-1} = 2^k - 1 < 2^k\]

This property prevents two different combinations of bits from equaling the same integer:

  1. Higher Bits Cannot Be Replaced by Lower Bits: Even if all bits below position \(k\) are set to \(1\), their combined sum (\(2^k - 1\)) cannot reach the value of setting bit \(k\) to \(1\) (\(2^k\)).
  2. Mathematical Contradiction: Suppose an integer \(N\) has two different representations, \(A\) and \(B\). Let \(k\) be the highest bit position where \(A\) and \(B\) differ. Without loss of generality, assume bit \(k\) is \(1\) in \(A\) and \(0\) in \(B\).
    • The value contributed by the remaining bits in \(B\) (from position \(k-1\) down to \(0\)) cannot exceed \(2^k - 1\).
    • However, representation \(A\) has at least \(2^k\) at position \(k\), plus non-negative values from lower bits.
    • Therefore, \(A > B\), which contradicts the assumption that \(A\) and \(B\) represent the same integer \(N\).

Since assuming two different representations leads to a contradiction, the representation must be unique.

Summary

Every non-negative integer has an exact and unique binary representation because: - The Division Algorithm guarantees a terminating procedure to find a binary form for any number (existence). - The geometric property \(\sum_{i=0}^{k-1} 2^i < 2^k\) guarantees that smaller powers of two cannot combine to duplicate or replace a higher power of two (uniqueness).