跳转至

数字的表示和处理

Abstract

计算机系统 Ⅰ 第二周课程内容

参考:

  • Computer System: A Programmer's Perspective (3rd.) Chapter 2: Representing and Manipulating Information

整数表示法

无符号整型

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

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

可以知道 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]\),将其视为补码转换为有符号整数:

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

它的最高位(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]\),将其视为反码转换为有符号整数:

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

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

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

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

无符号与有符号转换

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

\[ T2U_w(x) = B2U_w(T2B_w(x)) \]

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

\[ T2U_w(x) = \begin{cases}x+2^w, &x<0\\x, &x\geq 0\end{cases} \]

对于无符号转有符号:

\[ U2T_w(x) = B2T_w(U2B_w(x)) \]

同时:

\[ U2T_w(x) = \begin{cases}x, &x\leq TMax_w=2^{w-1}-1\\x-2^w, &x > TMax_w=2^{w-1}-1\end{cases} \]

整数运算

无符号整型加法

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

\[ x+_w^\mathrm{u}y = (x+y)\bmod{2^w} \]

即:

\[ x+_w^\mathrm{u}y = \begin{cases} x + y, &x + y < 2^w\quad \text{Normal}\\ x + y - 2^w, &2^w\leq x + y < 2^{w + 1}\quad \text{Overflow} \end{cases} \]

无符号整型减法

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

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

\[ -_w^\mathrm{u}x = \begin{cases}x, &x=0\\2^w-x, &x>0\end{cases} \]

补码表示中加法

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

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

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

\[ x+_w^\mathrm{t}y = \begin{cases} x+y-2^w, & 2^{w-1}\leq x + y \quad \text{Positive overflow}\\ x+y, &-2^{w-1}\leq x+y < 2^{w-1}\quad \text{Normal}\\ x+y+2^w, &x+y < -2^{w-1}\quad \text{Negative overflow} \end{cases} \]

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

\[ x+_w^\mathrm{t}y=U2T_w(T2U_w(x)+_w^\mathrm{u}T2U_w(y)) \]

补码表示中的减法

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

但是和原码不同,它本身就带正负,所以取负则可以直接进行(即取反加一)
但有一个特殊,也就是最小的 \(-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^\mathrm{t}x = \begin{cases} -2^{w-1}, &x = -2^{w-1}\\ -x, &x > -2^{w-1} \end{cases} \]

乘法

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

\[ x*_w^\mathrm{t}y = U2T_w(x*_w^\mathrm{u}y) = U2T_w(x*y\bmod 2^w) \]

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

x * 2k = x << k
x * 14 = (x << 3) + (x << 2) + (x << 1)

除以二的幂次

Unsigned

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

x / 2k = x >> k

并且是向下取整

Signed

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

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

所以向 0 取整:

(x < 0 ? (x + (1 << k) - 1) : x) >> k

浮点数表示法

前面的整型都是一种定点数(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 小于 1002,则直接舍去 bcd
  • 如果 bcd 大于 1002,则向 a 进一位
  • 如果 bcd 等于 1002
    • 如果 a 为 0(偶),则舍去 bcd
    • 如果 a 为 1(奇),则向 a 进一位

浮点数加法

会存在舍入问题

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


最后更新: 2022年5月24日 12:55:02
创建日期: 2022年3月8日 23:22:31
回到页面顶部