信息的表示和处理
十六进制表示法
- 一个字节由8位组成。
- 二进制表示法：$00000000_2 \sim 11111111_2$
- 十进制表示法：$0_{10} \sim 255_{10}$
- 十六进制表示法：使用数字$0 \sim 9$以及字符$A \sim F$来表示16个可能的值。一个字节的值域为 $00_16 \sim FF_16$
- 以$0x$或$0X$开头的数字常量被认为是十六进制的值。例如：$0xFA1D37B$
字数据大小
- 每台计算机都有一个字长(
word size),指明指针数据的标称大小(norminal size)。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。对于一个字长为w位的机器而言，虚拟地址的范围为$0 \sim 2^{w-1}$,程序最多访问$2^w$个字节。 - 将程序称为“32位程序”或"64位程序"时，区别在于该程序是如何编译的，而不是其运行的机器类型。
寻址和字节顺序
- 对于跨越多字节的程序对象，必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。
- 排列表示一个对象的字节有两个通用的规则。考虑一个$w$位的整数，其位表示为$[X_{w-1},X_{w-x},...,X_2,X_1]$，其中$X_{w-1}$是最高有效位，而$X_0$是最低有效位。假设$w$是$8$的整数，这些位就能被分组成为字节，其中最高有效字节包含位$[X_{w-1},X_{w-2},...,X_{w-8}]$，而最低有效字节位$[X_7,X_6,...,X_0]$，其他字节包含中间的位。
- 小端法：选择在内存中按照从最低有效字节到最高有效字节的顺序存储对象。
- 大端法：按照从最高有效字节到最低有效字节的顺序存储。
- 排列表示一个对象的字节有两个通用的规则。考虑一个$w$位的整数，其位表示为$[X_{w-1},X_{w-x},...,X_2,X_1]$，其中$X_{w-1}$是最高有效位，而$X_0$是最低有效位。假设$w$是$8$的整数，这些位就能被分组成为字节，其中最高有效字节包含位$[X_{w-1},X_{w-2},...,X_{w-8}]$，而最低有效字节位$[X_7,X_6,...,X_0]$，其他字节包含中间的位。
布尔代数
-
二进制是计算机编码、存储和操作信息的核心，所以围绕数值$0$和$1$的研究已经演化出了丰富的数据知识体系。
-
布尔代数的运算
-
~ 0 1 1 0 -
& 0 1 0 0 0 1 0 1 -
| 0 1 0 0 1 1 1 1 -
^ 0 1 0 0 1 1 1 0 - 二进制$1$和$0$表示逻辑值
TRUE或者FALSE，而运算符~、&、|、^分别表示逻辑运算$NOT$、$AND$、$OR$和EXECLUSIVE-OR
- 二进制$1$和$0$表示逻辑值
-
逻辑运算
- 逻辑运算符
||、&&、!，分别对应于布尔运算逻辑中的OR、AND、NOT运算。逻辑运算很容易和位级运算相混淆，但是它们的功能是完全不同的。- 逻辑运算认为所有非零的参数都表示为
TRUE，而参数0表示FALSE。也就是说，按位运算只有在特殊情况下，也就是参数被限制为0或者1时，才和与其对应的逻辑运算有相同的行为。 - 逻辑运算符
&&和||与它们对应的位级运算&和|之间第二个重要的区别：如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。
- 逻辑运算认为所有非零的参数都表示为
移位运算
- 移位运算：向左或者向右移动模式。
- $x << k$：
x向左移动k位，丢弃最高的k位，并在右端补k个0。移位量应该是一个$0~w-1$之间的值。 - x >> k：分为逻辑右移和算术右移
- 逻辑右移：左端补
k个0，得到的结果是$[0,...,0,X_{w-1},X_{w-2},...,X_k]$。 - 算术右移是在左端补
k个最高有效位的值，得到的结果是$[X_{w-1}...,X_{w-1},X_{w-2},...,X_k]$。
- 逻辑右移：左端补
- $x << k$：
整数表示
-
下图是数学术语，用于精确定义和描述计算机如何编码和操作整数。
-
符号 类型 含义 $B2T_w$ 函数 二进制转补码 $B2U_w$ 函数 二进制转无符号数 $U2B_x$ 函数 无符号数转二进制 $U2T_x$ 函数 无符号数转补码 $T2B_w$ 函数 补码转二进制 $T2U_w$ 函数 补码转无符号数 $TMin_w$ 函数 最小补码值 $TMax_w$ 函数 最大补码值 $UMax_w$ 函数 最大无符号数 $+_w^t$ 操作 补码加法 $+_w^u$ 操作 无符号数加法 $*_w^t$ 操作 补码乘法 $*_w^u$ 操作 无符号数乘法 $-_w^t$ 操作 补码取反 $-_w^u$ 操作 无符号数取反
-
-
假设有一个整数数据类型有
w位。可以将位向量写成$\vec{x}$，表示整个向量，或者写成$[x_{w-1},x_{w-2},...,x_0]$，表示向量中的每一位，把$\vec {x}$看做一个二进制表示的数，就获得$\vec{x}$的无符号表示。
无符号数的编码
- 原理：无符号函数编码的定义
- 对向量$\vec{x} = [x_{w-1},x_{w-2},...,x_0]$：
- $B2U_x(\vec{x})==\sum\limits_{i=0}^{w-1} x_i2^i$
- 在这个等式中，符号"=="表示左边被定义为等式右边。函数$B2U_w$将一个长度为$w$的0，1串映射到非负整数。
- 对向量$\vec{x} = [x_{w-1},x_{w-2},...,x_0]$：
- 原理：无符号数编码的唯一性
- 函数$B2U_x$是一个双射
- 双射是指一个函数$f$有两面：它将数值$x$映射为数值$y$，即$y=f(x)$，但它也可以反向操作，因为对每一个$y$而言，都有唯一一个数值$x$使得$f(x)=y$。
- 在本例中，即$x=f^{-1}(y)$。函数$B@U_w$将每一个长度为$w$的位向量都映射为$0 \sim 2^w-1$之间的唯一值；反过来，称其为$U2B_w$（即“无符号数到二进制")，在$0~2^{w-1}$之间的每一个整数都可以映射为一个唯一的长度为$w$的位模式。
补码编码
- 原理：对补码编码的定义
- 对向量$\vec{x}=[x_{w-1},x_{w-2},...,x_{0}]$：
- $B2T_w(\vec{x})==-x_{w-1}2^{w-1}+\sum\limits_{i=0}^{w-2} x_i2^i$
- 最高有效位$X_{w-1}$称为符号位，它的”权重“为$-2^{w-1}$，是无符号表示中权重的负数。符号位被设置为$1$时，表示值为负，而当设置为$0$时，值为非负。
- 对向量$\vec{x}=[x_{w-1},x_{w-2},...,x_{0}]$：
- 原理：补码编码的唯一性
- 函数$B2T_{w}$是一个双射
- 定义函数$TxB_w$（即”补码到二进制“）作为$B2T_w$的反函数。也就是说，对于每个数$x$，满足$TMin_w\leq x \leq TMax_w$，则$T2B_w(x)$是$x$的（唯一的）$w$位模式。
有符号数和无符号数之间的转换
-
定义函数$U2B_w$和$TxB_w$,它们将数值映射为无符号数和补码形式的位表示。
- 也就是说，给定$0\leq x \leq UMax_w$范围内的一个整数$x$，函数$U2Bw(x)$会给出$x$的唯一的$w$位无符号表示。
- ，相似的，当$x$满足$TMin_w\le x \le TMax_w$，函数$T2B_w(x)$会给出$x$的唯一的$w$位补码表示。
-
原理：补码转换为无符号数
-
对满足$TMin_w \le x \le TMax_w$的$x$有：
- $T2U_w(x)=\left{ \begin{array}{l} x+2^w,x < 0 \ x ,x\ge 0\end{array} \right.$
-
推到：补码转换为无符号数
- 如果计算$B2U_w(\vec{x})-B2T_w(\vec{x})$之差，从$0$到$w-2$的位的加权和将互相抵消掉，剩下一个值：$B2U_w(\vec{x})-B2T_w(\vec{x})=x_{w-1}(2^{w-1}-(-2^{w-1}))=x_{w-1}2^w$。
- 这就得到一个关系：$B2U_w(\vec{x})=x_{w-1}2^w+B2T_w(\vec(x))$，因此就有
- $B2U_w(T2B_w(x))=T2U_w(x)=x+x_{w-1}2^w$
- 根据上述公式的两种情况，在$x$的补码表示中，位$x-1$决定了$x$是否为负。
-
原理：无符号数转化为补码
-
对满足$0 \le u\le UMax_w$的$u$有：
- $U2T_w(u)=\left{ \begin{array}{l} u,u \le TMax_w \ u-2^w , u \gt TMax_w\end{array} \right.$
-
推到：无符号数转换为补码
-
如果计算$B2U_w(\vec{u})-B2T_w(\vec{u})$之差，从$0$到$w-2$的位的加权和将互相抵消掉，剩下一个值：$B2U_w(\vec{u})-B2T_w(\vec{u})=u_{w-1}(2^{w-1}-(-2^{w-1}))=u_{w-1}2^w$。
-
这就得到一个关系：$B2T_w(\vec{u})=-u_{w-1}2^w+B2U_w(\vec(u))$，因此就有
- $U2T_w(u)=-u_{w-1}2^w+u$
- 根据上述公式的两种情况，位$u_{w-1}$决定了$u$是否大于$Tmax_w=2^{w-1}-1$
-
C语言中的有符号数与无符号数
- 当执行一个运算时，如果它的一个运算数时有符号的而另一个是无符号的，那么C语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负地，来执行这个运算。
扩展一个数字地位表示
- 一个常见的运算是在不同字长的整数之间转换，同时又保持数值不变。
- 要将一个无符号数转换为一个更大的数据类型，只要简单地在表示的开头添加0.这种运算被称为零扩展(
zero extension)。 - 原理：无符号数地零扩展
- 定义宽度位$w$地位向量$\vec{u}=[u_{w-1},u_{w-2},...,u_0]$和宽度为 $w^{\prime}$ 的位向量$ \vec{u}^{\prime}=[0,...,0,u_{w-1},u_{w-2},...,u_0] $，其中$w^{\prime} > w $。则$B2U_W(\vec{u}) = B2U_w(\vec{u}^{\prime})$
- 要将一个补码数字转换为一个更大的数据类型，可以执行一个符号扩展(
sign extension)，在表示中添加最高有效位的值。 - 原理：补码数的符号扩展
- 定义宽度为$w$的位向量$\vec{x}=[x_{w-1},x_{w-2},...,x_{0}]$和宽度为$w^{\prime}$的位向量$\vec{x}^{\prime}=[x_{w-1},...,x_{w-1},x_{w-1},x_{w-2},...,x_0]$，其中$w^{\prime}>w$。则$B2T_w(\vec{x})=B2T_{w^{\prime}}(\vec{x}^{\prime})$。
- 推导：补码数值的符号扩展
- 关键属性是$2^w-2^{w-1}=2^{w-1}$。因此，加上一个权值为$-2^w$的位，和将一个权值为$-2^{w-1}$的位转换为一个权值为$2^{w-1}$的位，这两项运算的综合兄啊过就会保持原始的数值。
截断数字
- 假设不用额外的位来扩展一个数值，而是减少表示一个数字的位数。
- 原理：截断无符号数
- 令$\vec{x}$等于位向量$[x_{w-1},x_{w-2},...,x_0]$，而$\vec{x}^{\prime}$是将其截断为$k$位的结果：$\vec(x)^{\prime}=[x_{k-1},x_{k-2},...,x_0]$，令$x=B2U_w(\vec{x})$，$x^{\prime}=B2U_k(\vec{x}^{\prime})$。则$x^{\prime}=x mod 2^k$。
- 该原理背后的直觉是所有被截取的位其权重形式都为$2^i$，其中$i \ge k$，因此，每一个权再取模操作下结果都为零。可用如下推导表示：
- 推导：截断无符号数
- $B2U_w([x_{w-1},x_{w-2},...,x_0]) mod 2^k=[\sum\limits_{i=0}^{w-1}x_i2^i] mod 2^k = [\sum\limits_{i=0}^{k-1}x_i2^i]mod 2^k = \sum\limits_{i=0}^{k-1}x_i2^i=B2U_k([x_{k-1},x_{k-2},...,x_0])$
- 在这段推到中，利用了属性：对于任何$i \ge k$，$2^i~mod~2^k = 0$
- 补码截断也具有相似的属性，只不过要将最高位转换为符号位：
- 原理：截断补码数值
- 令$\vec{x}$等于位向量$[x_{w-1},x_{w-2},...,x_0]$，而$\vec{x}^{\prime}$是将其截断为$k$位的结果：$\vec(x)^{\prime}=[x_{k-1},x_{k-2},...,x_0]$，令$x=B2U_w(\vec{x})$，$x^{\prime}=B2T_k(\vec{x}^{\prime})$。则$x^{\prime}=U2T_k(x~mod~2^k)$。
- 推导：截断补码数值
- 使用与无符号数截断相同的参数，则有
- $B2U_w([x_{w-1},x_{w-2},...,x_0])~mod~2^k=B2U_k[x_{k-1},x_{k-2},...,x_0]$，也就是说，$x~mod~2^k$能够被一个位级表示为$[x_{k-1},x_{k-2},...,x_0]$的无符号数表示。将其转换为补码数则有$x^{\prime}=U2T_k(x~mod~2^k)$
整数运算
无符号数加法
- 原理：无符号数加法
- 对满足 $0~\le~x,y~<~2^w$的$x$和$y$有：
- $x~+_w^u~y=\left{ \begin{array}{l} x+y,~x+y~<2^w ~正常 \ x~+~y~-~2^2~,~2^w~\le~x+y~<2^{w+1} ~溢出\end{array} \right.$
- 推导：无符号数加法
- 一般而言，我们可以看到，如果$x+y~<~2^w$，和的$w+1$位表示中的最高位会等于$0$，因此丢弃它不会改变这个数值。另一方面，如果$2^w \le~x+y~<~2^{w+1}$，和的$w+1$位表示中的最高位会等于$1$，因此丢弃它就相当于从和中减去了$2^w$。
- 原理：检测无符号数假发中的溢出
- 对在范围$0~\le~x,y~\le~UMax_w$中的$x$和$y$，令$s=x+_w^uy$。则对计算$x$，当且仅当$s~<~x$（或者等价$s~<y~$）时，发生了溢出。
- 推导：检测无符号数加法中的溢出
- 通过观察发现$x+y~\ge~x$，因此如果$s$没有溢出，我们能够肯定$s~\ge~x$。另一方面，如果$s$确实溢出了，我们就有$s~=~x+y-2^w$。假设$y~<~2^w$，我们就有$y-2^w~<~0$，因此$s=x+(y-2^w)<x$。
补码加法
- 原理：补码加法
- 对满足$-2^{w-1}~\le~x,y~\le~2^{w-1}-1$的整数$x$和$y$，有：
- $x~+_w^~ty=\left{ \begin{array}{l} x+y-2^w,2^{w-1}~\le~x+y ~正溢出\ x~+~y,-2^{w-1}~\le~x~+~y~<2^{w-1} ~正常 \ x~+~y~+~2^w,x~+~y~<~-2^{w-1}~负溢出\end{array} \right.$
- 推导：补码加法
- 既然补码加法与无符号数加法有相同的位级表示，就可以按如下步骤表示运算$+^t_w$：将其参数转换为无符号数，执行无符号数加法，再将结果转换为补码
- $x+w^ty=U2T(T2U_w(x)+w^uT2U_w(y))=U2T_w[(x{w-1}2^w+x+y{w-1}2^w+y)~mod~2^w]=U2T_2[(x+y)~mod~2^w]$
- 消除了$x_{w-1}2^w$和$y_{w-1}2^w$这两项，因为它们模$2^w$等于$0$。
- 为了更好地理解这个数量，定义$z$为整数和$z=x+y$,$z^{\prime}$为$z^{\prime}=z~mod~2^w$，而$z^{{\prime}{\prime}}$为$z^{{\prime}{\prime}}=U2T_w(z^{\prime})$。数值$z^{{\prime}{\prime}}$等于$x~+_w^t~y$。
- $-2^w~\le~z~<~-2^{w-1}$。然后，我们会有$z^{\prime}~=~z+2^w$。这就得出$0~\le~z^{\prime}~<~-2^{w-1}+2^w=2^{w-1}$。这种情况称为负溢出(
negative overflow)。将两个负数x和y相加（这是得到$z~<~-2^{w-1}$的唯一方式），得到一个非负地结果$z^{{\prime}{\prime}}=x+y+2^w$ - $-2^{w-1}~\le~<0$。补码和等于整数和$x+y$
- $0~\le~z~<2^{w-1}$。补码和等于整数和$x+y$
- $2^{w-1}~\le~z~<~2^w$。我们又将有$z^{\prime}=z$，得到$2^{w-1}~\le~z^{\prime}~<~2^w$。在这个范围内，我们有$z^{{\prime}{\prime}}=z^{\prime}-2^w$，得到$z^{{\prime}{\prime}}=x+y-2^w$。这种情况称为正溢出（
positive overflow）。我们将正数x和y相加（这是我们能得到$z~\ge~2^{w-1}$的唯一方式，得到一个负数结果$z^{{\prime}{\prime}}=x+y-2^w$
- $-2^w~\le~z~<~-2^{w-1}$。然后，我们会有$z^{\prime}~=~z+2^w$。这就得出$0~\le~z^{\prime}~<~-2^{w-1}+2^w=2^{w-1}$。这种情况称为负溢出(
- 原理：检测补码加法中的溢出
- 对满足$TMin_w~\le~x,y~\le~Tmax_w$的
x和y，令$s=x+_w^ty$。当且仅当$x>0,y>0$，但$x\le0$时，计算$s$发生了正溢出。当且仅当$x<0,y<0$，但$s\ge0$时，计算$s$发生了负溢出。 - 推导：检测补码加法中的溢出
- 如果$x>0,y>0$，而$s\le0$，那么显然发生了正溢出。反过来，正溢出的条件为：
- $x>0,y>0$（否则$x+y~<~TMax_w$)
- $s~\le~0$。同样的讨论也适用于负溢出情况。
浮点数
二进制小数
- 理解浮点数的第一步是考虑含有小数值的二进制数字。
- 首先，更熟悉的十进制表示法
- $d_md_{m-1}...d_1d_0.d_{-1}d_{-2}...d_{-n}$
- 其中每个十进制数$d_i$的取值范围是$0~9$,这个表达描述的数值$d$定义如下：
- $d=\sum\limits_{i=-n}^{m}10^i~*~d$
- 数字权的定义与十进制小数点符号('.')相关，这意味着小数点左边的数字的权是10的正幂，得到整数值，而小数点右边的数字的权是10的负幂，得到小数值。
- 二进制同理：
- $b=\sum\limits_{i=-n}^m2^i~*~b_i$
- 点左边的位的权是2的正幂，点右边的位的权是2的负幂。
IEEE浮点数表示
- 定点法表示不能很有效地表示非常大的数字。相反，能够通过给定$x$和$y$地值，来表示形如$x*2^y$地数。
IEEE浮点标准用$V=(-1)^s~\times~M~\times~2^E$地形式来表示一个数- 符号(
sign)：s决定这数是负数($s=1$)还是正数($s=0$)，而对于数据0地符号位解释作为特殊情况处理 - 尾数(
significand)：M是一个二进制小数，它地范围是$1~\sim~2-e$，或者是$0~\sim~1-e$ - 阶码(
exponent)：E的作用是对浮点数加权，这个权重是$2$的E次幂（可能是负数） - 将浮点数的位表示为三个字段，分别对这些值进行编码：
- 一个单独的符号位$s$直接编码符号$s$
k位的阶码字段$exp=e_{k-1}...e_1e_0$编码阶码En位小数字段$frac=f_{n-1}...f_1f_0$编码尾数M，但是编码出来的值也依赖于阶码字段的值是否等于0
- 在单精度浮点格式中，
s、exp和frac字段分别为1位，k=8位和n=23位，得到一个32位的表示 - 在双精度浮点格式中，
s、exp和frac字段分别为1位，k=11位和n=52位，得到一个64位的表示
- 符号(
情况1：规格化的值
- 当
exp的位模式既不全为0(数值0)，也不全为1(单精度数值为255，双精度数值为2047)时，都属于这种情况。- 阶码的值是$E=e-Bias$，其中e是无符号数，其位表示$e_{k-1}...e_1e_0$，而$Bias$是一个等于$2^{k-1}-1$(单精度是127，双精度是1023)的偏置值。由此产生指数的取数范围，对于单精度是$-126~\sim~+127$，而对于双精度是$-1022~\sim~+1023$。
- 尾数定义为$M=1+f$
情况2：非规格化的值
- 当阶码域为全0时，所表示的数是非规格化形式。在这种情况下，阶码值是$E=1-Bias$，而尾数的值是$M=f$，也就是小数字段的值，不包含隐含的开头的1
情况3：特殊值
- 当阶码全为1的时候出现的。
- 当小数域全为0时，得到的值表示无穷，当$s=0$时是$+\infty$,或者当$s=1$时是$-\infty$。
- 当把两个非常大的数相乘，或者除以零时，无穷能够表示溢出的结果。
- 当小数域为非零时，结果值被称为"
NaN"，即不是一个数(Not a Number)的缩写
- 当小数域全为0时，得到的值表示无穷，当$s=0$时是$+\infty$,或者当$s=1$时是$-\infty$。
舍入
IEEE浮点格式定义了四种不同的舍入方式。默认的方法是找到最接近的匹配，而其他三种可用于计算上界和下界。- 向偶数舍入：将数字向上或者向下舍入，使得结果的最低有效数字是偶数。
- 原因：在$50%$的时间里，它将向上舍入，而在$50%$的时间里，它将向下舍入。
- 向零舍入：把正数向下舍入，把负数向上舍入
- 向下舍入：把正数和负数都向下舍入
- 向上舍入：把正数和负数都向上舍入
- 向偶数舍入：将数字向上或者向下舍入，使得结果的最低有效数字是偶数。