跳转至

Chap 2: Representing and Manipulating Information

约 2622 个字 8 行代码 2 张图片 预计阅读时间 13 分钟

1. Base

通俗地来讲，进制就是“满几进一”的“几”．对于一个在 \(m\) 进制下有 \(w\) 位的数 \(x\)，我们可以把这个数的各位看作位向量

\[ \vec{x} =[x_{w-1},x_{w-2},\cdots, x_0] \]

而在 \(m\) 进制下，其表示的无符号数为 \(x_m=\sum_{i=0}^{m-1}x_im^i\)．

常见进制

十进制（Decimal）：人类最广泛使用的进制．无特殊说明，数字默认都是十进制．

二进制（Binary）：由于晶体管的物理特性，二进制是计算机科学中最广泛的进制．所有的数据存储都是基于二进制的．

二进制数的表示：只有 \(0\) 和 \(1\)；以0b开头，0b1101．

十六进制（Hexadecimal）：常用于内存地址，代替较长的二进制数．

十六进制数的表示：\(A\sim F\) 分别表示 \(10\sim 15\)；以0x开头，如0x3f．

进制转换

可以套用公式 \(x_m=\sum_{i=0}^{m-1}x_im^i\)，直接计算得到十进制数．

  • \(1101_2 = 1\times 2^3+1\times 2^2+1\times 2^0=13\)．
  • \(\text{0x3f}=3\times 16^1 + 15 \times 16^0 = 63\)．

除基取余，逆序排列．

原理：不妨设十进制数 \(x\) 在 \(m\) 进制下可以表示为 \(x = a_nm^n+a_{n-1}m^{n-1}+\cdots +a_1m_1+a_0m_0\)，变形得到 \(x=m\cdot(a_nm^{n-1}+\cdots+a_1)+a_0\)．此时对 \(m\) 取模，得到的就是该数在 \(m\) 进制下的最低位；对 \(m\) 整除，变成了递归的子问题，重复即可．

由于 \(16=2^4\)，因此每4个二进制位表示一个十六进制位．从低位往高位数，如果总位数不是4的倍数就补前导零，接着四个一组转化成十六进制数．

将每一个十六进制位转化为4个二进制位即可．

2. Integer Representations

由于计算机中数据是由bit位（二进制位）组成的，接下来的讨论基于二进制．

2.1 Unsigned Integer

进制 \(m=2\) 时的情况．我们将之前的公式用函数 \(B2U_w\)（Binary to Unsigned）来表示：

\[ B2U_w(\vec{x})\doteq\ \sum_{i=0}^{w-1}x_i2^i \]

对于一个 \(w\) 位的二进制数，其可以表示介于 \(0\sim2^w-1\) 的所有整数；并且由于函数 \(B2U_w\) 是一个双射，所以对于任意 \(0\sim2^w-1\) 的整数，有且仅有一个 \(w\) 位的无符号编码．

说明

符号 \(\doteq\) 表示左边被定义为等于右边．

2.2 Signed Integer

如果我们想通过最小的修改来使无符号整数的编码可以表示负数，由于 \(2^k>\sum_{i=0}^{k-1}2^i\)，只要我们将 \(w\) 位编码的最高位系数设置成 \(-1\)，最后得到的结果就一定为负数．将该函数定义为 \(B2T_w\)（Binary to Two's-complement），我们有

\[ B2T_w(\vec{x})\doteq\ -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i \]

该表示方法成为补码．当最高位为 \(0\) 时，其表示正数；最高位为 \(1\) 时表示负数．其能表示的最小值为位向量 \([10\cdots0]\)，其数值为 \(TMin_w=-2^{w-1}\)；最大值为位向量 \([011\cdots1]\)，对应数值 \(TMax_w=2^{w-1}-1\)；表示范围为 \([TMin_w,TMax_w]\)．与无符号整数的表示一样，由于函数 \(B2T_w\) 是双射，在取值范围内的每一个整数都有唯一对应的补码编码．

补码的计算

由上述定义我们发现，非负数补码与无符号编码形式一样，而负数补码较为复杂．实际上，负数补码可由其对应正数推出．

我们已知

\[ B2T_w(\vec{x})=\ -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i \]

将位向量按位取反，得到 \(\sim \vec{x}=[1-x_{w-1},1-x_{w-2},\cdots,1-x_0]\)，带入补码公式得到

\[ \begin{aligned} B2T_w(\sim\vec{x})&=-(1-x_{w-1})2^{w-1}+\sum_{i=0}^{w-2}(1-x_i)2^i \\ &=-(-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i)-2^{w-1}+\sum_{i=0}^{w-2}2^i\\ &=-x-1 \end{aligned} \]

因此 \(-x=B2T_w(\sim x) + 1\)，该结论对于正数负数的补码均成立．

例：在4bit下，\(3\) 的补码表示为 \(0011\)，因此 \(-3\) 的补码表示为 \(\sim(0011) +1=1101\)；同理，再通过“取反加一”运算可以将 \(-3\) 补码转化为 \(3\)：\(\sim(1101)+1=0011\)．

3. Integer Arithmetic

3.1 Unsigned Integer

无符号加减乘都是在位运算得到结果后强制截断到 \(w\) 位，即 \([0,2^{w}-1]\) 的范围内．

执行乘法时，一般使用移位优化，如

  • x << 5: (x << 2) + x
  • x << 31：(x << 5) - x

移 \(K\) 位时，可以通过比较 \(K\) 二进制表示中 \(0\) 数量 +1 和 \(1\) 数量来决定使用加 / 减．

3.2 Signed Integer

有符号数执行 \(2^{k}\) 除法时，直接使用移位 >>= k 会舍去末尾 1，即无论正负均执行向下取整．

但实际常用向零取整，解决方法是让负数向上取整，即加上 \(2^{k}-1\) 的 bias：

\[ \left\lceil \dfrac{x}{2^{k}} \right\rceil = \left\lfloor \dfrac{x+2^{k}-1}{2^{k}} \right\rfloor \]

4. Floating Point

4.1 Fractional Binary Numbers

二进制也可以用于表示小数，小数点后的权重为 \(2\) 的负数次方；如 \(1.011\) 表示 \(2^0+2^{-2}+2^{-3}= 1.375\)．

产生的问题：如果小数太小会造成极大的浪费，如 \(0.1640625\) 的二进制表示为 \(0.0010101\)．类比科学计数法，其可以写成 \(2^{3}\times 1.0101\) 的形式．我们将小数点浮动到其二进制表示的第一个 \(1\) 后方，这也就是浮点数的名字来源．

4.2 IEEE Floating-Point Representation

\(\text{IEEE}\) 浮点标准用 \(V=(-1)^s\times M \times 2^E\) 来表示一个浮点数．后文以32位浮点数为例介绍该标准．

  • 符号（sign）：占最高位（第31位），\(s=1\) 表示负数，\(s=0\) 表示正数．
  • 阶码（exponent）： 占8位（第23-30位），对浮点数加权，权重是 \(E=\text{exponent-bias}\) ．其中 \(\text{bias}=2^{n-1}-1\)，32位浮点数中 \(n=8\)，因此 \(\text{bias}=127\)，即权重为 \(2^{\text{exponent-127}}\)．阶码的位数决定了浮点数的范围．
  • 尾数（significand）：占23位（第0-22位），\(M\) 为二进制小数．由于之前的约定，我们将小数点浮动到第一个 \(1\) 后方，那么所有规格化的表示都是 \(1.xxx\)，因此我们可以省略开头的 \(1\) 从而更大程度利用空间．对于规格化的数，其尾数实际值为 \(1.M\)．尾数的位数决定了浮点数的精度．

实际上，虽然阶码的取值范围为 \([0,255]\)，对应 \(E\) 的取值范围是 \([-127,128]\)，但只有 \([1,254]\) 是用于表示规格化数的．对于非规格化的数与特殊值的表达，见下图：

image-20260528111927346

零：当阶码与尾数全为 \(0\) 时，规定此时表达的是 \(0\)．由于此时没有限定符号位，实际上存在 \(+0\) 与 \(-0\) 两种表达．

无穷：当阶码全为 \(1\) 而尾数全为 \(0\) 时，规定此时表达的是无穷，正负由符号位决定．无穷的特点是可以当作 \(\max/\min\) 函数的单位元，即任意数字与 \(-\infty\) 取大、与 \(+\infty\) 取小的结果都是其本身．

NaN：表示”不是一个数”，例如出现了 \(\dfrac{0}{0}\)、\(\sqrt{-4}\) 等数学上不合法的情况．NaN具有污染的性质，即NaN与任何数字进行任何运算操作的结果均为NaN．

非规格化数：当阶码为 \(0\) 而尾数不为 \(0\) 时，此时表达非规格化的数．非规格化数的特点是其尾数的实际值为 \(0.M\) 而不是 \(1.M\)，所以实际上 \(0\) 的表示也属于非规格化数．

为什么需要非规格化数

非规格化数的提出是为了解决靠近 \(0\) 时跨度不均匀的问题：

如果没有非规格化数，最小的正数 \(a=(1.00\cdots00)_2 \times 2^{-126}\)，而第二小的正数为 \(b=(1.00\cdots01)_2 \times 2^{-126}=(1+2^{-23})\times 2^{-126}=2^{-126}\times 2^{-149}\)．可以看到，\(0\sim a\) 的距离大约是 \(a\sim b\) 距离的 \(2^{23}\) 倍．

为了解决这个问题，规定阶码为 \(0\) 时尾数的实际值为 \(0.M\)．需要注意的是， 虽然阶码为 \(0\)，但此时的 \(E\neq 0-127=-127\)．实际上此时 \(E=1-\text{bias}(=-126)\)，也就是与规格化的最小权重一样，目的是与规格化数衔接更顺．

模拟从 \(0\) 开始增大的过程：最开始是非规格化的数，每一次尾数+1的步长是 \(2^{-126}\times 2^{-23}=2^{-149}\)．当尾数全为 \(1\) 并进位后，此时阶码变为 \(1\) 而尾数变为 \(0\)，进入规格化数；此时表达的数和非规格化的最大值相差一个步长（\(2^{-149}\)）．由于 \(E\) 均为 \(-126\)，故此时步长仍为 \(2^{-149}\)．当尾数再次进位到阶码时，步长翻倍成为 \(2^{-148}\)．每一次进位都会有步长翻倍．当阶码为 \(150\) 时 \(E=23\)，此时步长变为 \(2^{23}\times 2^{-23}=1\)；当继续增加时，后续的步长将会越来越大，导致浮点数在表示较大数字时会出现无法表达出所有整数的情况．

对于正浮点数，我们观察发现比大小时完全可以当作无符号编码来比较．

4.3 Rounding

向正无穷舍入：即向上舍入．

向负无穷舍入：即向下舍入．

向零舍入：正数向下舍入，负数向上舍入．

向偶数舍入：当恰好位于两个可能的舍入结果中间时，可以使用向偶数舍入．这样做的好处是对于分布均匀的数据，向上舍入和向下舍入的占比接近 1：1，尽可能减小平均值的改变．

例

在十进制中，若 \(1.5\) 与 \(2.5\) 要保留整数，则均舍入为 \(2\)．在二进制中，\(1.1\) 舍入为 \(10\)，\(0.1\) 舍入为 \(0\)．

下图演示了更多例子．

image-20260528165714983

形式化地，若目前数字为 \(1.BBGRXXX\)，其中 \(G\)（Guard bit）为保留的最后一位，\(R\)（Round bit）为被舍去的第一位，\(S\)（Sticky bit）为后面所有位的或．

  • 若 \(R=0\)，则被舍去部分小于 0.5，直接舍去；
  • 若 \(R=1\) 且 \(S=1\)，则大于 0.5，进位；
  • 若 \(R=1\) 且 \(S=0\)，则等于 0.5，当 \(G=0\) 时舍去，\(G=1\) 时进位．

按照上述分析，最终是否进位取决于 \(R\land (G \lor S)\)．

4.4 Computation

由于浮点数在较大时步长也大，因此可能不满足一些基本数学定律．

如浮点加法和浮点乘法均满足交换律，但不满足结合律：

  • \((-1.5\times 10^{38}+1.5\times 10^{38})+1.0=1.0\)，\(-1.5\times 10^{38}+(1.5\times 10^{38}+1.0)=0\)．
  • \(10^{20}\times 10^{20} \times 10^{-20}=\inf\)，\(10^{20}\times( 10^{20} \times 10^{-20})=10^{20}\)．

4.5 Type Conversion

由于 float 尾数为 23 位，double 为 52 位，前者少于 int 的 32 位而后者多于；位数少转多不会丢失精度，多转少可能会丢失．

1
2
3
4
5
6
7
8
int x;
float f;
double d;

(float)(int) f != f
(int)(float) x != x
(double)(int) d != d
(int)(double) x == x