信息的表示与处理

作者: 刚子来简书啦 | 来源:发表于2020-09-10 09:57 被阅读0次

信息存储

大多数计算机使用8位的块，或者字节（byte），作为最小的可寻址的存储器单位，而不是在存储器中访问单独的位。机器级程序将存储器视为一个非常大的字节数组，称为虚拟存储器。存储器的每个字节都由一个唯一的数字来标识，称为它的地址，所有可能地址的集合称为虚拟地址空间。顾名思义，这个虚拟地址空间只是一个展现给机器级程序的概念性映像。实际的实现是将随机访问存储器（RAM）、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。

每台计算机都有一个字长，指明整数和指针数据的标称大小。因为虚拟地址是以这样一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于一个字长为w位的机器而言，虚拟地址的范围为0～2^w-1，程序最多访问2^w个字节。比如字长32位的计算机，虚拟地址空间最多为2³²≈4GB。

计算机和编译器支持多种不同方式编码的数字格式，如整数和浮点数，以及其他长度的数字。C语言支持整数和浮点数的多种数据格式，下表是C语言中不同数据类型分配的字节数。

C声明	32位机器	64位机器
char	1	1
short int	2	2
int	4	4
long int	4	8
long long int	8	8
char *	4	8
float	4	4
double	8	8

指针（例如被声明为“char *”类型的变量）使用机器的全字长。程序员应该力图使他们的程序在不同的机器和编译器上是可移植的。比如，许多程序员假设一个声明为int类型的程序对象能被用来存储一个指针，这在大多数32位的机器上能正常工作，但是在一台64位的机器上却会导致问题。

对于跨越多字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在存储器中如何排列这些字节。在几乎所有的机器上，多字节对象被存储为连续的字节序列，对象的地址为所使用的字节中最小的地址。某些机器选择在存储器中按照从最低有效字节到最高有效字节的顺序存储对象，而另一些机器则按照从最高有效字节到最低有效字节的顺序存储。前一种规则（最低有效字节在最前面）称为小端法，后一种规则（最高有效字节在最前面）称为大端法。

对于大多数应用程序员来说，他们机器所使用的字节顺序是完全不可见的，无论为哪种类型的机器编译的程序都会得到同样的结果。不过有时候，字节顺序也会成为问题。

当进行网络传输时，应用程序的代码编写必须遵守已建立的关于字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换为它的内部表示。

当阅读表示整数数据的字节序列时，需要根据机器的字节顺序来正确阅读，否则会出现相反的顺序。

当编写规避正常的类型系统的程序时，字节顺序将会产生影响。C语言中，可以使用强制类型转换（cast）来允许以一种数据类型引用一个对象，而这种数据类型与创建这个对象时定义的数据类型不同。

信息表示

C语言中字符串被编码为一个以null（其值为0）字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是ASCII字符码。在使用ASCII码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。因而，文本数据比二进制数据具有更强的平台独立性。

不同的机器类型使用不同的且不兼容的指令和编码方式。即使是完全一样的进程运行在不同的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。计算机系统的一个基本概念就是从机器的角度来看，程序仅仅只是字节序列。机器没有关系初始源程序的任何信息。

C语言提供了一组移位运算，以便向左或向右移动位模式。移位运算是从左至右可结合的。
$x_n$ << k：x向左移动k位，丢弃最高的k位，并在右端补k个0。移位量应该是一个0～n-1之间的值。
$x_n$ >> k：x向右移动k位，逻辑右移是在左端补k个0，算术右移是在左端补k个最高有效位的值。无符号数据使用逻辑右移，有符号数据使用算术右移。

Java对于如何右移有明确的定义。表达式x>>k会将x算术右移k个位置，而x>>>k会对x做逻辑右移。

整数表示

无符号编码
$B2U_w(\vec x)$ = $\sum_{i=0}^{w-1}x_i2^i$

$B2U_4([0001]) = 0\cdot2^3 + 0\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = 0+0+0+1 = 1$
$B2U_4([0101]) = 0\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = 0+4+0+1 = 5$
$B2U_4([1011]) = 1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 8+0+2+1 = 11$
$B2U_4([1111]) = 1\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 8+4+2+1 = 15$

有符号的补码编码
$B2T_w(\vec x)$ = $-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$

$B2T_4([0001]) = -0\cdot2^3 + 0\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = 0+0+0+1 = 1$
$B2T_4([0101]) = -0\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = 0+4+0+1 = 5$
$B2T_4([1011]) = -1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = -8+0+2+1 = -5$
$B2T_4([1111]) = -1\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = -8+4+2+1 = -1$

C语言标准定义了每种数据类型必须能够表示的最小的取值范围，并没有要求必须用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。

C库中的文件<limits.h>定义了一组常量，来限定编辑器运行的这台机器的不同整数类型的取值范围。比如，它定义了常量 INT_MAX、INT_MIN和UINT_MAX，它们描述了有符号和无符号整数的范围。

ISO C99标准在文件stdint.h中引入了另一类整数类型。这个文件定义了一组数据类型，它们的声明形如intN_t和unitN_t，指定的是N位有符号和无符号整数。N的具体值与实现相关，但是大多数编译器允许的值为8、16、32和64。因此，通过将它的类型声明为uint16_t，我们可以无歧义地声明一个16位无符号变量，而如果声明为int32_t，就是一个32位有符号变量。这些数据类型对应着一组宏，定义了每个N的值对应的最小值和最大值。这些宏名字形如INTN_MIN、INTN_MAX和UINTN_MAX。

关于整数数据类型的取值范围和表示，Java标准是非常明确的。它要求采用补码表示，取值范围与64位机器的情况一致。在Java中，单字节数据类型成为byte，而不是char，而且没有 long long 数据类型。这些非常具体的要求都是为了保证无论在什么机器上，Java程序运行的表现都能完全一样。

有符号数和无符号数之间的转换

$T2U_w\text(x)= \begin{cases} x+2^w，x<0 \\ x，x \geqslant 0 \\ \end{cases}$

$U2T_w\text(u)= \begin{cases} u，u<2^{w-1}\\ u-2^u，u \geqslant 2^{w-1} \end{cases}$

扩展一个数字的位表示

一种常见的运算是在不同字长的整数之间转换，同时又保持数值不变。这在当从一个较小的数据类型转换到一个较大的类型总是可能的，反之则未必。将一个无符号数转换为一个更大的数据类型，我们只需要简单地在表示的开头添加0，这种运算成为零扩展。将一个补码数字转换为一个更大的数据类型可以执行符号扩展，规则是在表示中添加最高有效位的值的副本。由此可知，如果我们原始值的位表示为 $[x_{w-1},x_{w-2},\cdots,x_0]$ ，那么扩展后的表示就为 $[x_{w-1},\cdots,x_{w-1},x_{w-1},x_{w-2},\cdots,x_0]$ 。

截断数字

对于无符号数字 $x$ ，截断的结果是：
$B2U_k([x_{k-1},x_{k-2},\cdots,x_0])=B2U_w\text([x_{w-1},x_{w-2},\cdots,x_0])mod2^k$

无符号截断的推导过程参考
$\begin{align} B2U_w([x_{w-1},x_{w-2},\cdots,x_0])mod2^k&=[\sum_{i=0}^{w-1}x_i2^i]mod2^k \\ &=[\sum_{i=0}^{k-1}x_i2^i]mod2^k \\ &=\sum_{i=0}^{k-1}x_i2^i \\ &=B2U_k([x_{k-1},x_{k-2},\cdots,x_0]) \\ \end{align}$
利用的属性：对于任何 $i \geqslant k,2^imod2^k=0$

对于一个补码数字 $x$ ，一般而言，我们将被截断的数字视为有符号的，截断的结果是：
$B2T_k([x_{k-1},x_{k-2},\cdots,x_0])=U2T_w(B2U_w([x_{w-1},x_{w-2},\cdots,x_0])mod2^k)$

整数运算

无符号加法

$x+_w^uy= \begin{cases} x+y, &x+y<2^w \\ x+y-2^w,&2^w\leqslant {x+y}<2^{w+1} \end{cases}$

补码加法

$x+_w^ty=U2T_w(T2U_w(x)+_w^uT2U_w(y))$

先转换成无符号进行加法运算，然后再把运算结果转成有符号的整数。从无符号转换成有符号的时候，按照补码形式的转换公式进行计算，考虑位的溢出。

$x+_w^ty= \begin{cases} x+y-2^w, &2^{w-1}\leqslant{x+y} &\text正溢出 \\ x+y,&-2^{w-1}\leqslant{x+y}<2^{w-1} &\text正常 \\ x+y+2^w,&{x+y}<-2^{w-1} &\text负溢出 \\ \end{cases}$

补码的非

$-_w^tx= \begin{cases} -2^{w-1}, &x=-2^{w-1} \text特殊值的声明 \\ -x, &x>-2^{w-1} \end{cases}$

无符号乘法

$x\times_w^uy=(x \cdot y)mod 2^w$

补码乘法

$x\times_w^ty=U2T_w((x\cdot y)mod 2^w)$

先进行无符号的乘法，再将无符号的结果转换成有符号整数，注意字节长度内的溢出。

乘以常数

在大多数机器上，整数乘法指令相当慢，需要10个或者更多的时钟周期，然后其他整数运算（例如加法、减法、位级运算和移位）只需要1个时钟周期。因此，编译器使用了一项重要的优化，试着用移位和加法运算的组合来代替乘以常数因子的乘法。

假设一个程序包含表达式 $x\times14$ 。利用等式 $14=2^3+2^2+2^1$ ，编译器会将乘法重写为 $(x<<3)+(x<<2)+(x<<1)$ ，实现了将一个乘法替换为三个移位和两个加法。无论 $x$ 是无符号的还是补码，甚至当乘法会导致溢出时，两个计算都会得到相同的结果。更好的方式是，编译器还可以利用属性 $14=2^4-2^1$ ，将乘法重写为 $(x<<4)-(x<<1)$ ，这时只需要两个移位和一个减法。

对于乘以2的幂： $x<<k$ 等价于 $x\times2^k$ 。
对于除以2的幂：无符号的逻辑右移， $x>>k$ 等价于 $x/2^k$ ；补码的算术右移， $(x<0?(x+(1<<k)-1):x)>>k$ 等价于 $x/2^k$ ，负数时涉及舍入的问题。

浮点数

IEEE浮点标准用 $V=(-1)^s\times M\times 2^E$ 的形式来表示一个数：

符号（sign）s决定这个数是负数还是正数，而对于0的符号位解释作为特殊情况处理。
尾数（significand）M是一个二进制小数，它的范围是 $1～2-\epsilon$ ，或者是 $0～1-\epsilon$ 。
阶码（exponent）E的作用是对浮点数加权，这个权重是2的E次幂（可能是负数）。

将浮点数的位表示划分为三个字段，分别对这些值进行编码：

一个单独的符号位s，直接编码符号s。
k位的阶码字段 $\text{exp}=e_{k-1}\cdots e_1e_0$ 编码阶码E。
n位小数字段 $\text{frac}=f_{n-1}\cdots f_1f_0$ 编码尾数M。

单精度浮点格式（C语言中的float）中，s、exp和frac的字段分别为1位、k=8位和n=23位，得到一个32位的表示；双精度浮点格式（C语言中的double）中，s、exp和frac的字段分别为1位、k=11位和n=52位，得到一个64位的表示。

规格化的表示

当表示阶码的字段位，不全为0或不全为1时，都成为规格化的表示，这也是最普遍的情况。

阶码字段解释为以偏置（bias）形式表示的有符号整数。也就是说，阶码的值是 $E=e-Bias$ ，其中 $e$ 是无符号数，其位表示位 $e_{k-1}\cdots e_1e_0$ ，而 $Bias$ 是一个等于 $2^{k-1}-1$ （单精度是127，双精度是1023）的偏置值。由此产生指数的取值范围，对于单精度是 $-126～+127$ ，而对于双精度是 $-1022～+1023$ 。

小数字段 $frac$ 的解释为描述小数值 $f$ ，其中 $0\leqslant f < 1$ ，其二进制表示为 $0.f_{n-1}\cdots f_1f_0$ ，也就是二进制小数点在最高有效位的左边。尾数定义为 $M=1+f$ 。有时，这种方式也叫做隐含的以1开头的表示，因为我们可以把M看成一个二进制表达式位 $1.f_{n-1}\cdots f_1f_0$ 的数字。既然我们总是能够调整阶码 $E$ ，使得尾数 $M$ 在范围 $1\leqslant M<2$ 之中，那么这种表示方法是一种轻松获得一个额外精度位的技巧。由于第一位总是等于1，因此我们就不需要显示地表示它。