补码

Posted on In

引言

在查看int与unsigned long的内存时，发现对补码的规则已经模糊不清了，又从头看了一遍，有了更深的理解，故记录。

负数的表示

在数字设计中，一个二进制数的最高位（MBS）被称作符号位。MBS为0，表示为正数；MBS为1，表示为负数。基于此，有两种常见的负数表示方法：

  • 补码：负数 = 正数原码逐位取反+1，例如$011_2 = 3_{10}，101_2 = (-3)_{10}$
  • 反码：负数 = 正数原码逐位取反，例如$010_2 = 2_{10}，101_2 = (-2)_{10}$

但是补码为什么要按如此规则设计呢，我将对此在下文给出自己的理解。

Motivation：加法实现减法

在计算机中，负数多采用补码表示，这是因为补码能用加法实现减法。

表针的例子

表盘上的表针，就是加法实现减法的一个例子。表针在表盘上按顺时针轮回转动，起初指向3，后面会重新指向0。这并不是靠按逆时针方向转动实现的，而是靠继续顺时针转过9格，实现了归0。

如果用数学语言描述上述过程，可以得到如下的两个“等式”：

$$3 - 3 = 0$$
$$3 + 9 = 0$$

在表盘上，对于表针来说$3 + 9 = 12$并不成立，这是因为表盘刻度的范围是：0～11。而12，溢出了表盘的范围。

Key idea：溢出

受到表针例子的启发，不难想到：可以利用二进制数的溢出特性达到加法实现减法的效果。

考虑3bit的二进制数，从000开始依次加1，可以枚举出所有的可能：

    -->
000 001 010 011 
 |           |
111 110 101 100
    <--

从枚举的结果不难看出，无论从哪个数开始（假设从$X$开始），沿着顺时针方向前进8（$2^3 = 7+1$）步，就会回到原点，用数学语言描述该过程为：
$$X + 8 - 8 = X$$
$-8$代表着溢出。

如果要实现减法（$-Y$），那只需沿着顺时针方向少走$Y$步，即（$8-Y$）步。用数学语言描述：
$$X - Y = X + (8 - Y) - 8$$
在上式中，令$\tilde{Y} = (8 - Y)$，则可以将上式改写为：
$$X - Y = X + \tilde{Y} - 8$$
在计算机中，溢出发生后会自动抛弃多的进位，也就是说$-8$是溢出后必然带来的结果。基于此，上式可以继续简写为：
$$X - Y = X + \tilde{Y} $$

至此，我们完成了：加法实现减法。

补码规则

现在，我们可以来分析补码为什么会定义如此的规则了：正数原码逐位取反+1。

首先，我们要对$\tilde{Y}$进行拆解重组：
$$\tilde{Y} = 8 - Y = 1 + (7 - Y)$$

在上式中，令$\hat{Y} = 7 - Y$。需要注意的是，我们现在考虑的是3bit的二进制数，$7_{10} = 111_2$。因此，可以得到：
$$\hat{Y} = 7 \oplus Y$$
异或的效果正是对Y逐位取反。最后：
$$\tilde{Y} = 1 + \hat{Y}$$
所以还有一个加一。

现在，我们应该可以更好地理解补码的定义了。

总结

之所以需要补码，是为了用加法实现减法，而这又需要靠溢出的特性实现，因此才有了相关的规则。