码制
不同的 码制 即对 位模式
做出不同的解释。
| 原码 | 反码 | 补码 |
|---|---|---|
| 最高位作为符号位 | \(-2^{w - 1} - 1\) | \(-2^w\) |
| 符号位取反 | $2^w - 1 - x $ | $2^w - x $ |
第二行是不同码制对最高位的解释，第三行是已知 x 如何求
-x 的表示
原码
为了区分正数和负数，用最高位当作符号位。这样符合人类的直觉，但对计算机计算很不友好。比如:
计算 \(1 + (-1)\)
- 原码表示
0001+1001 - 如果是纯加法电路会得到
0001+1001=1010(结果为-2)，计算有误。
这意味着，如果用原码来表示数字，CPU的计算单元(ALU)必须设计的十分复杂。他必须先判断符号位:
- 如果符号相同做加法
- 如果符号不相同，比较绝对值的大小，用大的减小的，最后决定结果的符号。
为了解决这一问题，就有了反码
反码
要了解反码，就要了解反码是怎么来的
反码的来源
早在机械计算器时代（比如 17 世纪帕斯卡的加法机），人们就在思考：“怎样把该死的减法变成加法？” 因为制造一个能倒着转、能处理“借位”的齿轮装置，比制造一个只管顺着转、只管“进位”的装置要复杂得多。
比如有个只能处理 0~99 的机器，我们要计算
56 - 13，但是我们不想让其倒着转(减法)，我们可以通过让
56 加上 13 的反码
99 - 13 = 86，让机器一直顺着转(加法)，即可。最后得到的结果为
\[ 56 + 86 = 142\]
与正确结果有误差，我们只用把进位 1 加上即可
42 + 1 = 43
二进制中的反码
根据上述的故事，我们就可以定义反码了:
\[-x_反 = 2^w - 1 - x_反\] 即用
11111...11 -
x，这在电路中非常容易实现，只需用一个
反相器(NOT GATE) 即可。
根据这个定义，我们就可以推导出最高位的数值为 \(2^{w-1} - 1\)
处理溢出
计算 \(A - B\)
A > B \[ \begin{aligned} A + (2^w - 1 - B) &= 2^w + (A - B - 1) \\ &= A - B - 1 \end{aligned} \] 最后得到的结果比实际的结果少1
A < B \[ \begin{aligned} A + (2^w - 1 - B) &= 2^w - 1 - (B - A) \end{aligned} \] 最后得到
B - A的反码表示，与结果符合(因为B - A的反码的值就是-(B - A)=A - B)
补码
为了解决反码中溢出的问题，我们定义:
\[ -x_补 = 2^w - x_补\]
通过该定义也可以推导出，补码最高位的数值为\(-2^{w-1}\)
补码与反码的关系
\[ -x_补 = -x_反 + 1 \]
推导如下:
\[ \begin{aligned} -x_补 &= 2^w - x_补 \\ &= (2^w - 1 - x_补) + 1 \\ &= -x_反 + 1 \end{aligned} \]
有符号和无符号之间的转化
设 x 为一个位向量，其位模式可以表示为 \([x_{w - 1}, x_{w - 2}, x_{w - 3} ... ,
x_0]\)
定义如下函数:
B2U(x) = \(\sum_{i=0}^{w-1}2^{i}x_i\)
B2T(x) = \(-x_{w-1}2^{w-1} +
\sum_{i=0}^{w-2}2^{i}x_i\)
根据以上定义，我们可以得到同一个 位模式
，不同的解释方式(补码或者无符号)得到的值有如下的关系:
\[ \begin{aligned} B2U(x) - B2T(x) &= x_{w-1}2^{w} \\ B2T(x) &= B2U(x) - x_{w-1}2^{w}\\ \end{aligned} \]
整数运算
无符号加法和补码加法
计算中用同一个加法器去处理无符号加法和补码加法
x 和 y: 都为位宽为 w 的位向量。
\(x_{u}、y_{u}、x_{s}、y_{s}\)为x和y的无符号和补码表示。
因为我们限制了结果只能用 w
位表示，所以值上有如下关系:
无符号加法: \[ x_{u} + y_{u} = (x_{u} + y_{u})(mod\ 2^w) \]
补码加法: \[ \begin{aligned} x_{t} + y_{t} = U2T(x_{u} + y_{u}) \end{aligned} \]
具体溢出等情况可以参考CSAPP中的内容(P60)