整数表示

系列 - CSAPP 笔记
注意
本文最后更新于 2022-02-24,文中内容可能已过时。

众所周知, 数据在计算机里是由二进制存储的, 所以在表示整数, 尤其是负数的时候, 需要编码Encoding, 因为计算机不能直接写一个负号. 编码可以理解为一个可逆函数, 输入是数学定义下的数字(也叫 真值), 输出是该数字在计算机中的表示.

无符号编码Unsigned Encodings很简单, 就是二进制表示, 然后存在计算机中. 因为没有负号, 只能表示非负数.

$\vec x$ 表示 $w$ 位的机器码 0-1 向量, $\vec x_i \in {0, 1}$ 表示其二进制第 $i$ 位上的取值, $x$ 表示真值, 那么:

$$x = \sum_{i=0}^{w-1} \vec x_i \cdot 2^i$$

吐嘈
中文翻译和英文也差得太远了吧…

原码Sign-magnitude 把最高位当成符号位, 正数的最高位为 0, 负数的最高位为 1. 然后就出现了 $0$ 有两种表示, 为区别, 称为 $+0$ 和 $-0$.

技巧
以前老是忘记原码是个啥, 直到今天看到了英文, 直译 符号量编码

$$x = (-1)^{\vec x_{w-1}} \sum_{i=0}^{w-2} \vec x_i \cdot 2^i$$

补码Two’s-Complement Encodings 类似于取模的操作, 比如在模 $2^{32}$ 意义下, $-1 \equiv 2^{32} - 1 \equiv (\overbrace{111\dots1}^{31\text{个}1})_2 \mod 2^{32}$. 这样的好处是减法统一到了加法, 不用去处理符号位. 这也是大部分机器对整数表示方式.

$$x = -2^{w-1} \cdot x_{w-1} + \sum_{i=0}^{w-2} \vec x_{i} \cdot 2^i$$

从上面这个式子可以看出, 最高位的 “权值” 为 $-2^{w-1}$, 而不是 $2^{w-1}$

反码Ones’-Complement Encodings 大概率是中文意译过来的. 他对负数的编码是这样的: 最高位为符号位, (负数)设为 1, 然后他的绝对值 $|x|$ 按照二进制存在其他位上, 然后把这些位都取反.

$$x = -(2^{w-1}-1) \cdot 2^{w-1} + \sum_{i=0}^{w-2} \vec x_{i} \cdot 2^i$$

可以看到, 最高位的 “权值” 为 $-(2^{w-1}-1)$, 而不是 $-2^{w-1}$

技巧
若 $x \ge 0$, 那么 $-x$ 经过补码编码后, 存在计算机里的二进制数为 $2^w - x$; 经过反码编码后, 存在计算机里的二进制数为 $(\overbrace{111 \dots 1}^{w-2\text{个}1})_2 - x$. 这也是 Two’s 和 ones’ 的来历.