本章首先介绍了(1)计算机中信息的存储方式(二值信号)，然后介绍了(2)计算机用有限的二进制数字(位)的组合来编码整数、浮点数(实数近似值)的方法，同时分析了(3)计算机编码的数字之间算术运算的性质 (受限于有限的位表示，一些运算不具有我们所熟知的数学属性，比如乘法分配律)。
信息的存储
现代计算机存储和处理用二值信号表示的信息。二值信号很容易表示、存储和传输，比如可以表示为穿孔卡片上有洞或无洞、导线上的高电压或低电压、或磁场引起的顺时针或逆时针。
大多数计算机使用字节(byte)作为最小的可寻址的存储器单位。每个字节都由一个数字来标识，称为它的地址(address)，所有可能地址的集合就称为虚拟地址空间。【C语言中指针的值都是某个存储块的第一个字节的虚拟地址】
指针是C的一个重要特性，和变量类似，指针也包含两方面：它的值和它的类型。它的值表示某个对象的位置，它的类型表示那个位置上所存储对象的类型。
每台计算机都有一个字长(word size)，决定了虚拟地址空间的大小。对于一个字长为位的机器来说，虚拟地址的范围为
，即程序最多访问
字节。比如对于32位的计算机，虚拟地址空间为4GB。
一个字节包含8位(bit)，在二进制表示法中，它的值域是00000000 ~ 11111111；在十进制表示法中，它的值域是0 ~ 255。由于二进制太过冗长，十进制与位模式的转化很麻烦，因此有了十六进制表示法。
十六进制(简写为Hex)使用数字0 ~ 9和字符A ~ F来表示16个可能的值。用十六进制书写，一个字节的取值范围为00 ~ FF。C语言中以0x或者0X开头的数字常量是十六进制的数值，字符A ~ F可以大写也可以小写。
十六进制和二进制之间的转换很方便，比如只需将十六进制的每个数展开，即可得到对应的二进制表示：
十六进制转二进制
寻址
在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节序列中最小的地址。比如一个int类型(4个字节)的变量地址为0x100，也就是说该变量的4个字节会被存在存储器的0x100, 0x101, 0x102, 0x103位置上。
虚拟地址空间
字符串的表示
C语言中的字符串被编码为一个以字符NULL结尾的字符数组。每个字符都由某个标准编码比如ASCII字符码来表示，NULL的ASCII码值为0。
字符串表示
使用ASCII码来表示字符，在任何系统上都会得到相同的结果，与字节顺序和字大小无关，因此文本数据比二进制数据具有更强的平台独立性。
整数的表示
计算机编码的整数有两种：unsigned无符号整数(非负数)和默认有符号整数(负数，零，正数)。
64位机器上C语言整型的典型取值范围
无符号数的编码
假设一个整型有位，位向量表示为
，每一位
取值为0或1，则可定义无符号数编码
(Binary to Unsigned)为：
\begin{equation}
B2U(x) = \sum_{i=0}^{n-1}x_i 2^i
\end{equation}
位无符号编码所能表示的值的范围为
。
有符号数的编码(补码)
计算机利用补码(two's-complement)来表示有符号数。我们定义补码编码(Binary to Two's-complement)为：
\begin{equation}
B2T(x) = -x_{n-1} 2^{n-1} + \sum_{i=0}^{n-2}x_i 2^i
\end{equation}
最高有效位也被称为符号位，权重为
。当符号位为1时，表示值为负；当符号位为0时，表示值非负。
位补码所能表示的值的范围为
，即补码最小值Tmin=[1,0,...,0]，补码最大值Tmax=[0,1,1,...,1]。
有符号数还有反码和补码两种表示方法，但是几乎所有的现代机器都是用补码。
有符号数和无符号数之间的转换
C语言允许在各种不同的数字数据类型之间做强制类型转换，比如(unsigned) x, (int) u。
相同字长的整数类型之间的转换
对于大多数C语言的实现，处理相同字长的有符号数和无符号数之间转换的一般规则是：位表示不变，数值可能改变。
有符号数和无符号数的转换
比如0xCFC7的16位位表示既是-12345的补码表示，又是53191的无符号表示。注意有12345 + 53191 = 65536 = 2^{16}。
-
补码转无符号数
w表示数据类型的位数即上文n，TMin和TMax分别表示补码表示的最小值和最大值
-
无符号数转补码
w表示数据类型的位数即上文n，UMax表示无符号数最大值
证明如下：
无符号数和补码之间的转换
所以补码和无符号数编码之间的映射关系如图：
补码和无符号数编码的映射关系
注意，当执行一个运算时，如果一个运算数是有符号数而另一个是无符号数，那么C语言会隐式地将有符号数强制转换成无符号数，即假设这两个数都是非负的，再执行该运算。
不同字长的整数类型之间的转换
从一个较小的数据类型转换到一个较大的数据类型，比如short到int。扩展位表示，保持数值不变：
- 对于无符号数，只需在开头加0，称为
零扩展。 - 对于有符号数，只需在开头添加最高有效位的值，称为
符号位扩展。
从一个较大的数据类型转换到一个较小的数据类型，比如int到short。截断位表示，数值可能改变：
- 对于无符号数，直接截断，丢弃多余高位。
- 对于有符号数，也是直接截断，丢弃多余高位，剩下的最高位为符号位。
e.g.
int x = 53191;
short sx = (short) x; // -12345
int y = sx; // -12345
当把x强制转化为short时，我们将32位的int截断为了16位的short int，从而得到16位的位模式对应的补码值-12345；当我们再把它强制转回int时，通过符号位扩展把高16位置1，得到32位的补码表示，保持数值-12345不变。
整数的运算
计算机执行整数的运算实际上是一种模运算形式。表示数字的有限字长限制了数值的取值范围，运算结果可能溢出，此时会将高位截断丢弃，相当于进行了mod高位运算。
无符号加法
无符号加法
补码加法
补码加法
无符号乘法
无符号乘法
补码乘法
补码乘法
无符号乘法和补码乘法本质都是截断为位。因此，对于相同位表示对应的无符号乘法和补码乘法，它们乘法运算的结果位表示都是一样的。
w=3位无符号乘法和补码乘法示例
如图所示，虽然完整的的位表示不一样，但是最终截断后的结果一样。
乘以常数
在大多数机器上，整数乘法指令相当慢，需要10个或更多时钟周期，而其他整数运算(比如加法、减法、移位)只需要1个时钟周期。因此，编译器使用了一项优化，试着用移位和加减法来替代乘法指令。
- 乘以2的幂
乘以2的幂
当为固定字长左移位时，高
位会被截断丢弃。
- 乘以常数K
乘以常数K
比如表达式的值：
-
，编译器将乘法重写为
，只需三个移动和两个加法。
-
，编译器将乘法重写为
，只需两个移位和一个减法。
除以2的幂
在大多数机器上，整数除法要比整数乘法更慢，需要30个或更多时钟周期。除以2的幂也可以使用移位运算实现，只不过使用右移，而不是左移。左移只有一种形式，而右移有两种形式：
- 无符号数使用逻辑右移实现。
逻辑右移在左端补0 - 补码数使用算术右移实现。
算术右移在左端补最高有效位的值
8位参数x的移位运算
整数除法总是向零舍入，也就是对于大于0的值，向下舍入，比如floor(3.14)=3；对于小于0的值，向上舍入，比如ceil(-3.14)=-3。
- 除以2的幂的无符号除法
从下图可以看出，无符号数除以2的幂是向下舍入：
无符号数除以2的幂
- 除以2的幂的补码除法
从下图可以看出，补码除以2的幂也是向下舍入：
补码除以2的幂
当补码数为负数时，则不符合向零舍入原则，因此我们在移位前对其修正，加一个偏置(1<<k)-1，然后再进行算术右移，得到向上舍入的结果：
补码除以2的幂，向零舍入
偏置的原理为对于整数 x 和 y (y>0)，ceil(x / y) = floor((x+y-1) / y)
注意，除以2的幂我们可以通过逻辑或算术右移实现，但是与乘法不同，该方法不能推广到除以任意常数。
浮点数
浮点表示为了对形如的有理数进行编码，来近似地表示实数。
二进制小数(定点表示)
，其中每一位
取值0或1：
小数的二进制表示
IEEE浮点表示
定点表示不能有效表示非常大的数字，比如要用101后面接100个0的位模式表示。
IEEE浮点表示
浮点数的位表示划分为3个字段，分别编码：
- 符号位 s 编码符号
- 阶码字段 exp 编码阶码
- 小数字段 frac 编码尾数
浮点表示
C语言中单精度float的s, exp, frac分别为1位，8位，23位；双精度double的s, exp, frac分别为1位，11位，52位；
浮点数根据阶码的值，被分成了3类：
- 规格化值：exp的位模式不全为0，也不全为1
- 非规格化值：exp的位模式全为0
- 特殊值：exp的位模式全为1
单精度浮点数的分类
- 对于规格化值，exp字段所能表示的无符号数
的范围为[1, 254]，但是阶码
的值不等于
，其中
，
为exp字段的位数。因此对于单精度值，
，故阶码
尾数定义为
，即1+小数字段的值：
位数M的二进制表示
-
对于非规格化值，阶码
，尾数
，即直接为小数字段的值。它提供了一种表示0的方法，因为规格化数中，我们总使
，因此无法表示0。当非规格化数的s=0, exp全为0，frac也全为0，此时得到+0.0；当非规格化数的s=1, exp全为0，frac也全为0，此时得到-0.0。其次，非规格化值可以表示那些很接近于0的数。
-
对于特殊值，exp字段全为1。当frac字段全为0时表示无穷，此时若s=0则表示
，若s=1则表示
。当把两个非常大的数相乘，或者除以0，无穷能够表示溢出的结果。当frac字段非零时，结果被称为NaN(Not a Number)。一些运算的结果不能是实数或无穷，就会返回NaN，比如
。
8位非负浮点数，阶码字段4位，小数字段3位。
可以发现位表示对应的无符号整数是升序排列的，而它们对应的浮点数也是升序排列的。这不是偶然，IEEE浮点格式如此设计就是为了能够使用整数排序函数来进行排序。
整型转单精度浮点型
int to float
所以可以发现整数值12345(0x3039)和单精度浮点值12345.0(0x4640E400)在位表示上有重叠：
整型和单精度浮点型的对应
重叠区域对应整数的低位，和浮点数的小数字段的高位。
舍入
因为表示方法限制了浮点数的范围和精度，所以浮点运算只能近似地表示实数运算。因此，对于，我们一般希望找到最接近的的匹配值
，使得其能用浮点形式表示出来。
IEEE浮点格式定义了四种不同的舍入方式：
- 向上舍入
- 向下舍入
- 向零舍入：正数向下舍入，负数向上舍入，得到
，使得
- 向偶数舍入(默认)：也称为向最接近的值舍入。当遇到两个可能值的中间结果时，则选择向上舍入还是向下舍入取决于舍入结果的最低有效数字是否是偶数。比如2.5的舍入结果取决于2和3哪个是偶数。
向偶数舍入
向偶数舍入有一半情况向上舍入，一半情况向下舍入，从而避免了数值的统计偏差。
浮点运算
由于溢出或者舍入而失去精度，浮点数的加法和乘法不具有结合性，同时乘法也不具有分配性。
不同数据类型之间强制转换时，有如下原则：
- int 转 float，数字不会溢出，但是可能被舍入。因为单精度浮点数的小数字段为23位，可能会出现无法保留精度的情况。
- int 或 float 转 double，因为double有更大的范围和精度(有效位数)，所以能够保留精确数值。
- double 转 float，因为float的范围较小，所以值可能溢出为
- float 或 double 转 int，值会向零舍入。比如1.99被转成1，-1.99被转成-1；值还可能发生溢出。
网友评论