反码和补码的数学原理

本文介绍了使用反码和补码的加法代替减法，并分析了这样做背后的数学原理

本文公式较多，建议使用电脑或平板阅读

反码与补码的表示

原码的表示方法：
符号位加上它的绝对值，即用第一位表示符号，其余位表示值。如果是 $8$ 位二进制：
$$ \begin{array}{l} [+1] = [00000001]_原 \\ [-1] = [10000001]_原 \end{array} $$
反码的表示方法：
正数的反码是其本身
负数的反码是在其原码的基础上，符号位不变，其余各个位取反.
$$ \begin{array}{l} [+1] = [00000001]_原 = [00000001]_反 \\ [-1] = [10000001]_原 = [11111110]_反 \end{array} $$
补码的表示方法：
正数的补码就是其本身
负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后 $+1$. (即在反码的基础上 $+1$)
$$ \begin{array}{l} [+1] = [00000001]_原 = [00000001]_反 = [00000001]_补 \\ [-1] = [10000001]_原 = [11111110]_反 = [11111111]_补 \end{array} $$

反码和补码的意义

对于计算机来说加减是最基础的运算要设计的尽量简单，而减法相当于加上一个负数，所以完全可以使用加法来代替减法。但是这就出现了如何处理符号位的问题，short、int、long 的位数不同符号位自然也不同，为了避免运算前还需要判断符号位的位置，前人提出了将符号位也引入计算的机制，也就是补码。

确切的说，用反码就可以实现加法来代替减法，其中唯一特殊的是 $0$：

$$ \begin{split} &1 - 1 \\ &= 1 + (-1) \\ &= [0000 0001]_原 + [1000 0001]_原 \\ &= [0000 0001]_反 + [1111 1110]_反 \\ &= [1111 1111]_反 \\ &= [1000 0000]_原 \\ &-0 \end{split} $$

这样算出来的结果是 $-0$，然而对于 $0$ 来说正负号是无意义的，并且 $-0$ 的表示方法使得 $0$ 出现了两个编码
此外，用反码加法代替减法需要循环进位：

$$ \begin{split} &4 - 2 \\ &= 4 + (-2) \\ &= [0000 0100]_原 + [1000 0010]_原 \\ &= [0000 0100]_反 + [1111 1101]_反 \\ \end{split} $$

这里如果按正常的二进制加法计算 $0000 0100 + 1111 1101$ 会得出 $0000 0001$ 即 $1$ 的错误结果。正确的做法是将溢出的进位再加到最低位上，得到正确结果 $0000 0010$ 即 $2$

为了解决 $0$ 有两个编码并且需要循环进位的问题，出现了补码:
补码用 $[00000000]_补$ 表示 0，而 $[10000000]_补$ 表示 $-128$，这样就消除了歧义

$$ \begin{split} &1 - 1 \\ &= 1 + (-1) \\ &= [0000 0001]_原 + [1000 0001]_原 \\ &= [0000 0001]_补 + [1111 1111]_补 \\ &= [0000 0000]_补 \\ &= [0000 0000]_原 \\ &= 0 \end{split} $$

综上所述反码和补码的意义在于可以让符号位参与计算，从而可以用加法代替减法的数学原理。接下来我们接下来我们探讨一下可以这样做背后的数学原理

用反码和补码的加法代替减法的数学原理

首先我们来介绍两个数学概念：

取模运算

取模运算公式：

$$ x \bmod y = x - y \lfloor x / y \rfloor $$

以 $ -3 \bmod 2 $ 为例:

$$ \begin{split} &-3 \bmod 2 \\ &= -3 - 2 \times \lfloor -3/2 \rfloor \\ &= -3 - 2 \times \lfloor -1.5 \rfloor \\ &= -3 - 2 \times (-2) \\ &= -3 + 4 \\ &= 1 \end{split} $$

这里给出一个取模的算法实现：

public int mod(int a, int b) {
    return (a % b + b) % b;
}

同余

两个整数 a，b，若它们除以整数 m 所得的余数相等，则称 a，b 对于模 m 同余

记作 $ a \equiv b \pmod m $，读作 a 与 b 关于模 m 同余

$$ \begin{split} \left. \begin{gathered} 4 \bmod 12 &= 4 \\ 16 \bmod 12 &= 4 \end{gathered} \right\} \implies 4 \equiv 16 \pmod{12} \end{split} $$

同余具有的性质：

自反性，对称性，传递性

$$ \begin{align} &a \equiv a \pmod m \\ &a \equiv b \pmod m \iff b \equiv a \pmod m \\ &a \equiv b \pmod m \text{ 且 } b \equiv c \pmod m \implies a \equiv c \pmod m \\ \end{align} $$

线性运算

$$ \begin{split} a \equiv b \pmod m \text{ 且 } c \equiv d \pmod m \implies \left\{ \begin{gathered} a \pm c &\equiv b \pm d \pmod m \\ a \times c &\equiv b \times d \pmod m \end{gathered} \right. \end{split} $$

同余的除法的性质与加减乘法不同：
$$ a \equiv b \pmod m \quad 且 \quad c \equiv d \pmod m \implies a \equiv b\left(\bmod \frac{m}{\operatorname{gcd}(c, m)}\right) $$

幂运算
$$ a \equiv b \pmod m \implies a^{n} \equiv b^{n} \pmod m $$

证明

我们还是以 $ 4 - 2 $ 为例，根据同余数的性质我们很容易得出这样的结论：

$$ \begin{split} \left. \begin{gathered} 4 &\equiv 4 \pmod{7} \\ -2 &\equiv 5 \pmod{7} \\ \end{gathered} \right\} \implies 4 - 2 \equiv 4 + 5 \pmod{7} \end{split} $$

也就是说我们计算 $ 4 - 2 $ 就相当于计算 $ (4 + 5) \bmod 7 $
如果我们将 $-2$ 和 $5$ 换成二进制会发现 $-2$ 的反码的数值部分正好等于 $5$，也就是说补码的计算实际上是求其模数为当前数制的上限（这个例子中为 $7$）的同余数

$$ \begin{split} -2 &= [1010]_原 = [1101]_反 \\ 5 &= [0101]_原 = [0101]_反 \end{split} $$

这样循环进位就相当于溢出的数对当前数制的上限（这个例子中为 $7$）取模后再与原结果相加

$$ (4 + 5) \bmod 7 = 8 \bmod 7 + 1 = 2 $$

这里的 $8$ 相当于进位

而补码的计算相比于反码只不过是增加了模的值：这时我们计算 $ 4 - 2 $ 就相当于计算 $ (4 + 6) \bmod 8 $

$$ (4 + 6) \bmod 8 = 8 \bmod 8 + 2 = 2 $$

因为进位 $ 8 \bmod 8 = 0 $ 所以不需要循环进位

另一种数学推导可以看这篇文章：反码与补码加法的理解