数的表示与计算
约 2295 个字 预计阅读时间 8 分钟
1. 进制
通俗地来讲，进制就是“满几进一”的“几”．对于一个在 \(m\) 进制下有 \(w\) 位的数 \(x\)，我们可以把这个数的各位看作位向量
而在 \(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. 整数编码
由于计算机中数据是由bit位（二进制位）组成的，接下来的讨论基于二进制．
2.1 无符号整数
进制 \(m=2\) 时的情况．我们将之前的公式用函数 \(B2U_w\)（Binary to Unsigned）来表示：
对于一个 \(w\) 位的二进制数，其可以表示介于 \(0\sim2^w-1\) 的所有整数；并且由于函数 \(B2U_w\) 是一个双射，所以对于任意 \(0\sim2^w-1\) 的整数，有且仅有一个 \(w\) 位的无符号编码．
说明
符号 \(\doteq\) 表示左边被定义为等于右边．
2.2 有符号整数
如果我们想通过最小的修改来使无符号整数的编码可以表示负数，由于 \(2^k>\sum_{i=0}^{k-1}2^i\)，只要我们将 \(w\) 位编码的最高位系数设置成 \(-1\)，最后得到的结果就一定为负数．将该函数定义为 \(B2T_w\)（Binary to Two's-complement），我们有
该表示方法成为补码．当最高位为 \(0\) 时，其表示正数；最高位为 \(1\) 时表示负数．其能表示的最小值为位向量 \([10\cdots0]\)，其数值为 \(TMin_w=-2^{w-1}\)；最大值为位向量 \([011\cdots1]\)，对应数值 \(TMax_w=2^{w-1}-1\)；表示范围为 \([TMin_w,TMax_w]\)．与无符号整数的表示一样，由于函数 \(B2T_w\) 是双射，在取值范围内的每一个整数都有唯一对应的补码编码．
补码的计算
由上述定义我们发现，非负数补码与无符号编码形式一样，而负数补码较为复杂．实际上，负数补码可由其对应正数推出．
我们已知
将位向量按位取反，得到 \(\sim \vec{x}=[1-x_{w-1},1-x_{w-2},\cdots,1-x_0]\)，带入补码公式得到
因此 \(-x=B2T_w(\sim x) + 1\)，该结论对于正数负数的补码均成立．
例：在4bit下，\(3\) 的补码表示为 \(0011\)，因此 \(-3\) 的补码表示为 \(\sim(0011) +1=1101\)；同理，再通过“取反加一”运算可以将 \(-3\) 补码转化为 \(3\)：\(\sim(1101)+1=0011\)．
3. 浮点数编码
3.1 二进制小数
二进制也可以用于表示小数，小数点后的权重为 \(2\) 的负数次方；如 \(1.011\) 表示 \(2^0+2^{-2}+2^{-3}= 1.375\)．
产生的问题：如果小数太小会造成极大的浪费，如 \(0.1640625\) 的二进制表示为 \(0.0010101\)．类比科学计数法，其可以写成 \(2^{3}\times 1.0101\) 的形式．我们将小数点浮动到其二进制表示的第一个 \(1\) 后方，这也就是浮点数的名字来源．
3.2 IEEE浮点表示
\(\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]\) 是用于表示规格化数的．对于非规格化的数与特殊值的表达，见下表：
| Exponent | Significand | Object |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 非零 | 非规格化数 |
| 1-254 | anything | 规格化数 |
| 255 | 0 | \(+\infty/- \infty\) |
| 255 | nonzero | NaN |
零：当阶码与尾数全为 \(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\)；当继续增加时，后续的步长将会越来越大，导致浮点数在表示较大数字时会出现无法表达出所有整数的情况．
3.3 舍入
向正无穷舍入：即向上舍入．
向负无穷舍入：即向下舍入．
向零舍入：正数向下舍入，负数向上舍入．
向偶数舍入：当恰好位于两个可能的舍入结果中间时，可以使用向偶数舍入，如 \(1.5\) 与 \(2.5\) 均舍入为 \(2\)．在二进制中，\(1.1\) 舍入为 \(10\)，\(0.1\) 舍入为 \(0\)．
3.4 浮点计算
由于浮点数在较大时步长也大，因此可能不满足一些基本数学定律：
- \((-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\)．
- 将浮点型强制转化为整型再转化回去，或者是将整型强制转化为浮点型再转化回去，结果都有可能不同．