我们要证明的核心命题是： 同一个二进制加法电路（即模 \(2^n\) 加法），既实现了无符号数加法，也实现了补码加法。
我们将分为三个步骤进行证明： 1. 定义 (Definition)：严格定义位向量、无符号数值和补码数值。 2. 引理 (Lemma)：证明无符号值和补码值在模 \(2^n\) 下同余。 3. 定理 (Theorem)：证明加法闭环。
第一步：定义 (Definitions)
设 \(X\) 为一个 \(n\) 位的二进制向量，其位序列为 \(x_{n-1}x_{n-2}\dots x_0\)，其中 \(x_i \in \{0, 1\}\)。
1. 无符号数的值函数 \(U(X)\)
无符号数将所有位都视为正权重： \[U(X) = \sum_{i=0}^{n-1} x_i 2^i = x_{n-1}2^{n-1} + \sum_{i=0}^{n-2} x_i 2^i\] 取值范围：\([0, 2^n - 1]\)。
2. 补码的值函数 \(T(X)\)
补码将最高位（符号位）视为负权重，其余位为正权重： \[T(X) = -x_{n-1}2^{n-1} + \sum_{i=0}^{n-2} x_i 2^i\] 取值范围：\([-2^{n-1}, 2^{n-1} - 1]\)。
3. 硬件加法器的行为函数 \(Hardware_{Add}(X, Y)\)
硬件加法器是一个逻辑电路，它输入两个 \(n\) 位向量 \(X, Y\)，输出一个 \(n\) 位向量 \(S\)。 其物理行为严格等价于无符号数的模 \(2^n\) 加法（因为超过 \(n\) 位的进位会被物理截断）： \[U(S) = (U(X) + U(Y)) \pmod{2^n}\] 即： \[U(S) \equiv U(X) + U(Y) \pmod{2^n}\]
第二步：引理 (Fundamental Lemma)
引理： 对于任意 \(n\) 位二进制向量 \(X\)，其无符号值 \(U(X)\) 与补码值 \(T(X)\) 模 \(2^n\) 同余。 \[U(X) \equiv T(X) \pmod{2^n}\]
证明： 我们将两者的定义式相减： \[ \begin{aligned} U(X) - T(X) &= \left( x_{n-1}2^{n-1} + \sum_{i=0}^{n-2} x_i 2^i \right) - \left( -x_{n-1}2^{n-1} + \sum_{i=0}^{n-2} x_i 2^i \right) \\ &= x_{n-1}2^{n-1} - (-x_{n-1}2^{n-1}) \\ &= 2 \cdot (x_{n-1}2^{n-1}) \\ &= x_{n-1} \cdot 2^n \end{aligned} \]
分析结果： * \(x_{n-1}\) 是最高位，只能取 0 或 1。 * 因此，\(U(X) - T(X)\) 要么是 0，要么是 \(2^n\)。 * 在模 \(2^n\) 算术中，\(k \cdot 2^n \equiv 0 \pmod{2^n}\)。
结论： \[U(X) - T(X) \equiv 0 \pmod{2^n} \implies U(X) \equiv T(X) \pmod{2^n}\] (证明完毕)
物理意义解释：这一步证明了，虽然数学上数值不同，但在计算机的 \(n\) 位存储空间里，它们属于同一个同余类。这是后续所有推导的基石。
第三步：定理证明 (The Main Proof)
定理： 设 \(X, Y\) 为两个 \(n\) 位补码数，设 \(S\) 为硬件加法器产生的二进制结果。则 \(S\) 的补码值 \(T(S)\) 模 \(2^n\) 同余于 \(T(X) + T(Y)\)。
证明过程：
根据硬件定义（参见第一步第3点），加法器生成的结果 \(S\) 满足： \[U(S) \equiv U(X) + U(Y) \pmod{2^n} \quad \text{------ (式1)}\]
利用引理（参见第二步），我们可以将式1右边的无符号项 \(U(X)\) 和 \(U(Y)\) 替换为补码项： 因为 \(U(X) \equiv T(X) \pmod{2^n}\) 且 \(U(Y) \equiv T(Y) \pmod{2^n}\)，根据模运算加法性质，代入式1得： \[U(S) \equiv T(X) + T(Y) \pmod{2^n} \quad \text{------ (式2)}\]
再次利用引理，将式2左边的无符号结果 \(U(S)\) 替换为补码结果 \(T(S)\)： 因为对于任意向量（包括 \(S\)）都有 \(U(S) \equiv T(S) \pmod{2^n}\)，代入式2得： \[T(S) \equiv T(X) + T(Y) \pmod{2^n} \quad \text{------ (式3)}\]
结论： \[T(S) \equiv T(X) + T(Y) \pmod{2^n}\]
详细解释与最终结论
我们得到了最终公式： \[T(S) = T(X) + T(Y) + k \cdot 2^n \quad (k \in \mathbb{Z})\]
这说明了什么？
运算的正确性： 虽然硬件是按照无符号逻辑（模 \(2^n\)）运行的，但生成的结果 \(S\) 的补码值 \(T(S)\)，与我们期望的数学结果 \(T(X) + T(Y)\) 只相差 \(2^n\) 的整数倍。
为什么这就足够了？
- 在 \(n\) 位补码系统中，能够表示的数值范围是有限的：\([-2^{n-1}, 2^{n-1}-1]\)。
- 在这个范围内，任何两个不同的数，其差值绝对不可能等于 \(2^n\) 的倍数（因为范围跨度本身就是 \(2^n\)）。
- 这意味着： 在模 \(2^n\) 的剩余系中，只要结果没有溢出（Overflow），能够落入这个合法范围的解是唯一的。
溢出判断 (Overflow)：
- 如果 \(T(X) + T(Y)\) 的真实结果超出了补码的表示范围，那么硬件计算出的 \(T(S)\) 会因为模 \(2^n\) 的作用“回绕”到范围的另一头（例如正数加成负数）。
- 这就是为什么我们需要一个额外的 \(Overflow\) 标志位。
- 只要 \(Overflow = 0\)，则 \(k=0\)，此时严格成立： \[T(S) = T(X) + T(Y)\]
最终陈述： 该数学证明展示了补码系统与模算术系统的同构性。正是因为 \(T(X)\) 和 \(U(X)\) 在模 \(2^n\) 下是等价的，所以我们不需要设计两套加法电路。一套模 \(2^n\) 的电路（即普通的二进制加法器）就足以同时处理这两种数学模型，唯一的区别在于我们如何解读结果（位级模式）以及如何检测溢出。