数字的表示和处理 ¶

整数表示法 ¶

无符号整型 ¶

无符号整型一般直接使用其二进制（原码）来表
比如有一个 \(w\) 位的比特序列 \(\overrightarrow{x}=[x_{w-1}, x_{w-2}, \dots, x_0]\)，则将其转化为无符号整数：

可以知道 B2U 是一个双射

同时也容易知道无符号整型可表示的最大值为 \(UMax_{w}=\displaystyle\sum_{i=0}^{w-1}2^i=2^w-1\)

有符号整型补码表示 ¶

最常用的表示有符号整型的方法是补码（Two's-Complement）
对于比特序列 \(\overrightarrow{x}=[x_{w-1}, x_{w-2}, \dots, x_0]\)，将其视为补码转换为有符号整数：

它的最高位（MSB）是符号位，如果是 1 则表示是负数，0 则是正数

并且对于正数，它对应的比特序列就是其二进制
而对于负数，则使用补码，即 \(-x = \sim x + 1 (x > 0)\)

从另一个角度来看，它实际上就是改变了 MSB 的权重，从 \(2^{w-1}\) 改为了 \(-2^{w-1}\)

同时也可以计算出补码可以表示的范围 \(TMin_w=-2^{w-1}\)，\(TMax_w=2^{w-1}-1\)

有符号整型反码表示 ¶

反码（Ones' complement）也是表示有符号整型的一种方法，但是并不常用
对于比特序列 \(\overrightarrow{x}=[x_{w-1}, x_{w-2}, \dots, x_0]\)，将其视为反码转换为有符号整数：

相较于补码，它们在正数上是一样的
但是对于负数，反码表示下是 \(-x = \sim x (x > 0)\)

在另一个角度，它的 MSB 的权重是 \(2^{w-1}-1\)

它的缺点是 0 有两种表示，即 +0 [00...0] 和 -0 [11...1]

无符号与有符号转换 ¶

C 语言中强制转换有符号和无符号整型并不改变比特序列，而是改变读取的方式
即从有符号转为无符号就是通过原码来解读原来补码的二进制
从无符号转为有符号就是通过补码解读原来原码的二进制

并且可以发现原码和补码只差了 MSB 的权重从正到负，所以 \(T2U_w(x) = x + x_{w-1}2^w\)，也就是：

对于无符号转有符号：

同时：

整数运算 ¶

无符号整型加法 ¶

对于两个无符号整型 \(x, y\in[0, 2^w)\)，它们做加法后的结果在 \(w+1\) 位下才能完全表示出来
但是结果一定还要表示在 \(w\) 位下表示，这时就要对溢出部分截断，即直接去掉最高位

即：

无符号整型减法 ¶

减法即加上减数取负，所以只要知道如何取负即可

对于 0，取负后一定也为 0
而对于非 0 数，因为取负后加上原数为 0（\(2^w\) 截断后），所以取负即用 \(2^w\) 减去原数：

补码表示中加法 ¶

使用补码表示有符号整型进行加法时，会遇到两种特殊情况：

• 加法后的结果太大，超过 \(2^{w-1} - 1\)，正溢出（Positive overflow）
• 加法后的结果太小，小于 \(-2^{w-1}\)，负溢出（Negative overflow）

所以也需要对结果进行截断处理：

从比特序列角度来看，也就是直接视为二进制序列相加，再转回补码表示的值：

补码表示中的减法 ¶

同样，也是只考虑取负即可

但是和原码不同，它本身就带正负，所以取负则可以直接进行（即取反加一）
但有一个特殊，也就是最小的 \(-2^{w-1}\)，负的它 \(2^{w-1}\) 并不在补码的范围中

而 \(TMin_w+_w^\mathrm{t}TMin_w=-2^{w-1}-2^{w-1}=-2^w\)，截断后恰好为 0
所以 \(-TMin_w = TMin_w\)，即：

乘法 ¶

整型的乘法均是直接将原码 / 补码的二进制相乘，然后直接截断至 \(w\) 位

并且乘以常数可以通过移位来进行，比如：

除以二的幂次 ¶

Unsigned¶

无符号整型除以二的幂次则直接进行右移：

并且是向下取整

Signed¶

补码表示的有符号整型除以二的幂次，进行数值右移，但是直接右移进行的是向下取整
而对于有符号整型除法一般要向 0 取整，所以对于负数要向上取整

向上取整要先加上一个 bias 然后再右移，bias = 2^k - 1，即 x / 2 ^k 向上取整要进行 (x + (1 << k) - 1) >> k

所以向 0 取整：

浮点数表示法 ¶

前面的整型都是一种定点数（fixed point），即小数点的位置是固定的（固定在末尾），它的缺点是范围固定

而浮点数（floating point）的小数点位置则不是固定的，它使用 \(x*2^y\) 的形式来表示一个数
也因此可以表示很大或者很小的数

常用的浮点数表示方法是由 IEEE 754 标准指定的

IEEE 浮点数表示法都通过 \(V=(-1)^s\times M\times 2^E\) 的形式来表示，其中：

• \(s\)：符号（sign），1 则表示是负数，0 则表示是正数
• \(M\)：尾数（mantissa）或称有效数字（significand）
• \(E\)：指数（exponent）

它们的存储方式是：

• 最高位比特表示 \(s\)
• 后接 \(k\) 比特 \([e_{k-1}\cdots e_1e_0]\) 指数部分（也称为阶码）编码了 \(E\)
• 最后是 \(n\) 个比特 \([f_{n-1}\cdots f_1f_0]\) 分数部分，编码了 \(M\)

并且有两种最常见的格式，即：

• 单精度（single-precision floating-point），\(k=8\)，\(n=23\)，32 位（4 字节）存储
• 双精度（double-precision floating-point），\(k=11\)，\(n=52\)，64 位（8 字节）存储

IEEE 浮点数值还有三种形式，下面分别描述

规约形式 ¶

这种形式下的阶码不全为 0 也不全为 1，是最常见的形式
这种形式下的 \(s\) 直接表示正负，而 \(E\)、\(M\) 的规则：

• \(E\) 通过移码（biased）表示成阶码 \([e_{k-1}\cdots e_1e_0]\)，移位 \(Bias = 2^{k-1}-1\)，\(E = e - Bias\)（其中 \(e\) 为将阶码转为无符号整型的值），这可以使阶码部分范围从 \([1, 2^k-2]\) 变为 \([-2^{k-1}+2, 2^{k-1}-1]\)
• \(M = 1+f\)，其中 \(f = 0.f_{n-1}\cdots f_1f_0\in[0, 1)\)，因此 \(M=1.f_{n-1}\cdots f_1f_0\in[1, 2)\)

计算后再通过 \(V = (-1)^s\times M\times 2^E\) 即可计算出所表示的值

规约形式可以表示的所有数的间距是不一致的，且越接近 0 越密集

在规约形式下可以表示的数的范围：

• 单精度
  • 最小正（0 0...01 0...00）\(1\times 2^{-126}\)（\(1.2\times 10^{-38}\)）
  • 最大正（0 1...10 1...11）\((2-2^{-23})\times 2^{127}\)（\(3.4\times 10^{38}\)）
• 双精度
  • 最小正（0 0...01 0...00）\(1\times 2^{-1022}\)（\(2.2\times 10^{-308}\)）
  • 最大正（0 1...10 1...11）\((2-2^{-52})\times 2^{1023}\)（\(1.8\times 10^{308}\)）

非规约形式 ¶

在这种形式下阶码全为 0，这种形式的目的是表示 0 以及接近 0 的值
同样 \(s\) 直接表示正负，\(E\)、\(M\)：

• \(E = 1 - Bias = -2^{k-1} + 2\)
• \(M = f = 0.f_{n-1}\cdots f_1f_0\)

而在浮点数表示法下，0 有两种，即 \(s=0\) 且后面全为 0 的 +0.0，以及 \(s=1\) 且后面全为 0 的 -0.0
它们有时视为相等，但也有时会视为不相等

非规约形式表示的所有数的间距是一致的，它们的间距也就是用非规约形式可表示的最小正数 \(2^{-n}\times 2^{-2^{k-1}+2}\)

非规约形式可表示的数的范围：

• 单精度
  • 最小正（0 0...00 0...01）\(2^{-23}\times 2^{-126}\)（\(1.4\times 10^{-45}\)）
  • 最大正（0 0...00 1...11）\((1-2^{-23})\times 2^{126}\)（\(1.2\times 10^{38}\)）
• 双精度
  • 最小正（0 0...00 0...01）\(2^{-52}\times 2^{-1022}\)（\(4.9\times 10^{-324}\)）
  • 最大正（0 0...00 1...11）\((1-2^{-52})\times 2^{1022}\)（\(2.2\times 10^{-308}\)）

特殊值 ¶

浮点数也可以用来表示一些特殊值，即 \(+\infty\)、\(-\infty\) 以及 NaN（not a number）
在这种情况下阶码全为 1，具体三种情况：

• 分数部分全为 0，且 \(s=0\)，表示 \(+\infty\)
• 分数部分全为 0，且 \(s=1\)，表示 \(-\infty\)
• 分数部分不全为 0，表示 NaN

舍入 ¶

舍入（rounding）有四种：向偶舍入（round-to-even）、向 0 舍入（round-toward-zero）、向下舍入（round-down）、向上舍入（round-up）
默认是 round-to-even

如果有一个二进制小数：X...XX.Y...Yabcd...，要舍入到 a 的位置

• 如果 bcd 小于 100 ₂，则直接舍去 bcd
• 如果 bcd 大于 100 ₂，则向 a 进一位
• 如果 bcd 等于 100 ₂
  • 如果 a 为 0（偶），则舍去 bcd
  • 如果 a 为 1（奇），则向 a 进一位

浮点数加法 ¶

会存在舍入问题

是阿贝尔群，满足交换律，但不满足结合律