CSAPP-1:信息的表示和处理

24 Nov 2023

信息的表示和处理

信息存储

基本概念

位(bit) 为计算机方位内存中单独的位，字节(byte) 为计算机中最小的可寻址的内存单位，大多数计算机使用8-Bit的字节。机器级程序将内存视为一个非常大的字节数，称为虚拟内存(virtual memory)。内存的每个字节都由一个唯一的数字来标识，被称为它的地址(address)，所有可能地址的集合被称为虚拟地址空间。

每台计算机都有一个字长(word size)，指明指针数据的标准大小(normal size)，对于一个字长为 $w$ 的机器而言，虚拟地址的范围为 $0\sim 2^w-1$，程序最多访问 $2^w$ 个字节。

基本C数据类型的典型大小(以字节为单位)

寻址和字节顺序

在几乎所有的机器上，多字节对象都被存储为连续的字节，但排列表示一个对象的字节有两种通用规则：

最低有效字节在前面的方式称为小端法(little endian)，大多数Intel兼容机，Android和IOS都只用小端模式，
最高有效字节在前面的方式称为大端法(big endian)，网络传送数据时要求使用大端法规则。

假设变量 $x$ 类型为int，位于地址0x100处，十六进制的值为0x01234567，下图表示两种方法排列表示的规则：

对于大多数情况下，及其所使用的字节顺序是完全不可见的，但在一些情况下，字节顺序会成为问题：

当小端法机器产生的数据被发送到大端法机器时，接收程序会发现字节反序，为避免这类问题，网络应用程序的代码编写必须遵守大端法规则（见11章）。
当阅读表示整数数据的字节序列时字节顺序很重要，这通常发生在检查机器级程序时，例如阅读反汇编器生成的代码时（见3章）。

当编写规避正常的类型系统的程序时字节顺序变得重要，例如：我们将byte_pointer定义为一个指向类型为unsigned char的对象的指针，这样一个字节指针引用一个字节序列，其中每一个字节都被认为是一个非负整数，

 typedef unsigned char *byte_pointer;

 void show_bytes(byte_pointer start, size_t len) {
     size_t i;
     for (i = 0; i < len; i++)
     printf(" %.2x", start[i]);
     printf("\n");
 }

 void show_int(int x) {
     show_bytes((byte_pointer) &x, sizeof(int)); 
 }

 void show_float(float x) {
     show_bytes((byte_pointer) &x, sizeof(float)); 
 }

 void show_pointer(void *x) {
     show_bytes((byte_pointer) &x, sizeof(void *));
 }

 void test_show_bytes(int val) {
     int ival = val;
     float fval = (float) ival;
     int *pval = &ival;
     show_int(ival);
     show_float(fval);
     show_pointer(pval);
 }

在不同机器上得到的结果并不相同，如下图所示：

这里注意每输出一次都是两位十六进制数，因为一个字节是8Bit，对应两位十六进制数。

字符串表示

C语言中字符串被编码为一个以null(其值为0)字符结尾的字符数组，例如我们以参数12345和6来运行show_bytes，我们会得到结果 31 32 33 34 35 00.

布尔代数简介

最简单的布尔代数是在二元集合{0,1}上定义的:

布尔运算 $\sim$ 对应于逻辑运算 NOT，在命题逻辑中用符号 $\lnot$ 表示，
布尔运算 $\And$ 对应于逻辑运算 AND，在命题逻辑中用符号 $\land$ 表示，
布尔运算 $\vert$ 对应于逻辑运算 OR，在命题逻辑中用符号 $\lor$ 表示，
布尔运算 ^ 对应于逻辑运算异或(Exlusive or)，在命题逻辑中用符号用 $\oplus$ 表示。具体规则如下图所示：

以上布尔运算可以扩展到位向量的运算，其中位向量就是固定长度为w，由0和1组成的串，它一个很有用的应用就是表示有限集合。

C语言中的位级运算

位级运算的一个常见用法就是掩码运算，例如：

掩码0xFF表示一个字的低位字节，位级运算x & 0xFF生成一个由 $x$ 的最低有效字节组成的值，而其他的字节都被置为0，
位级运算x | 0xFF将x的最低有效字节设为1，其他字节保持不变，
x ^ 0xFFFFFFFF等价于~x，x ^ 0不发生改变，
x ^ ~0xFF使得x最低有效字节不变，其他位都取补。
注意是最低有效字节，8位，所以是0xFF。

关于异或运算还有两点注意：

x ^ y = (x & ~y) | (~x & y).
a ^ a = 0.
y = x^y, x = x^y, y = x^y即可做到不需要第三个位置就可以交换 $x$ 和 $y$ 的值。
!(x^y)满足当 $x,y$ 相等时返回1，否则返回0。

三个二元位级运算都具有交换律和结合律。

C语言中的逻辑运算

逻辑运算有三种: &&, ||, !，注意别和位级运算混淆即可，另外&&和||具有短路性。

C语言中的移位运算

对于一个位表示为 $[x_{w-1},x_{w-2},\ldots,x_0]$ 的操作数 $x$，左移运算x<<k使得 $x$ 向左移动 $k$ 位，丢弃最高的 $k$ 位，并在右端补上 $k$ 个0。并且移位运算从左到右是可结合的。

相应地，右移运算x>>k分为两种:

对无符号数使用逻辑右移，即在左端补 $k$ 个0，得到 $[0,\ldots,0,x_{w-1},\ldots,x_k]$ .
对有符号数使用算术右移，即在左端补 $k$ 个最高有效位的值，得到 $[x_{w-1},\ldots,x_{w-1},x_{w-1},x_{w-2},\ldots,x_{k}]$.

注意:

对于一个 $w$ 位组成的数据类型，当 $k\geq w$ 很大的时候，实际上的位移量就是k mod w位。
加减法的优先级比移位运算要高，因此在拿不准的时候记得加括号。

整数表示

整数编码

对于位向量 $\mathbf{x} = [x_{w-1},x_{w-2},\ldots,x_0]$, 无符号数编码定义为 $\text{B2U}_w(\mathbf{x}) = \sum\limits_{i=0}^{w-1} x_i 2^i$

补码编码的定义为 $\text{B2T}_w(\mathbf{x}) = -x_{w-1}2^{w-1} + \sum\limits_{i=0}^{w-2} x_i 2^i$

可以证明当 $0\leq x \leq 2^w-1$ 时，无符号数编码是唯一的，当 $\text{TMin}_w = -2^{w-1} \leq x \leq 2^{w-1}-1 = \text{TMax}_w$ 时，补码编码是唯一的。

关于这些数字，有几点值得注意：

补码的范围是不对称的，即 |TMin| = |TMax| + 1，
最大的无符号数刚好比补码的最大数的两倍大1，即UMax = 2TMax +1，
-1和 UMax 有同样的位表示，即一个全1的串。

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

对于满足 $\text{TMin}_w \leq x \leq \text{TMax}_w$ 的 $x$ 有，

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

对于满足 $0 \leq u \leq \text{UMax}_w$ 的$u$有，

\[\text{U2T}_w(u) = \begin{cases} u-2^w ,\quad & u > \text{TMax}_w \\ u,\quad & u \leq \text{TMax}_w \end{cases}\]

当 $u>\text{TMax}_w$ 时，$u$的最高位有效数字为1，转化为补码表示就相当于最高位权重从+1变为-1，因此少了 $2^w$，反之同理，越靠近0的负数映射为越大的无符号数。

另外，可以证明U2T和T2U两个函数都是双射，两个函数的行为如下图所示：

在C语言中允许两者之间相互转换，主要有四种情况：

显示的强制类型转换就会导致转换发生，例如
```
 int tx; 
 unsigned ux; 
 tx = (int)ux;
```
一种类型的表达式被赋值给另外一种类型的变量，例如
```
 tx = ux;
```
当用printf输出数值时，分别用%d,%u和`%x%表示有符号十进制、无符号十进制和十六进制格式输出一个数字，例如
```
 int x = -1;
 printf("x = %u = %d\n", x, x); \\ x = 4294967295 = -1.
```
当执行一个两侧分别为有符号和无符号数的运算时，会隐式地将有符号数转换为无符号数，例如
1. -1 < 0U是错误的，
2. -1 > (unsigned)-2是正确的，
3. 2147483647 > (int)2147483648U是正确的。

在C头文件limit.h中是这样定义TMin和TMax的：

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

因为在某些编译器中可能会把-2147482648认为是正数，这里不深究，了解即可。

扩展一个数字的位表示

宽度为 $w$ 的位向量 $\mathbf{u} = [u_{w-1},\ldots,u_0]$ 扩展到 $w’$ 位的 $\mathbf{u}’ = [0,\ldots,0,u_{w-1},\ldots,u_0]$，则有 $\text{B2U}_w(\mathbf{u}) == \text{B2U}_{w'}(\mathbf{u}')$
宽度为 $w$ 的位向量 $\mathbf{x} = [x_{w-1},\ldots,x_0]$ 扩展到 $w’$ 位的 $\mathbf{x}’ = [x_{w-1},\ldots,x_{w-1},x_{w-1},\ldots,x_0]$，则有 $\text{B2T}_w(\mathbf{x}) == \text{B2T}_{w'}(\mathbf{x}')$

举个例子，有符号数1001 -> -7，扩展到8位时11111001 -> -7，因为 $-2^{p+k}+2^{p+k-1}+\ldots+2^p = -2^p.$

值得注意的是，从一个数据大小到另一个数据大小的转换，以及无符号和有符号之间的转换的相对顺序能够影响一个程序的行为，例如

short sx = -12345;
unsigned uy = sx; /* Mystery! */
printf("uy = %u:\t", uy);
show_bytes( (byte_pointer)&uy, sizeof(unsigned));
\\ uy = 4294954951: ff ff cf c7.

这表明当short转换成unsigned时，我们先要改变大小，然后再完成有符号到无符号的转换，即(unsigned)sx等价于(unsigned)(int)sx而不是(unsigned)(unsigned short)sx。

截断数字

截断一个数字可能会改变它的值，这也是溢出的一种形式。

令 $\mathbf{x} = [x_{w-1},\ldots,x_0]$，将其阶段为k位有 $\mathbf{x}’ = [x_{k-1},\ldots,x_0]$, 记 $x=\text{B2U}w(\mathbf{x}), x’ = \text{B2U}{k}(\mathbf{x}’)$，则有 $x’ = x\mod\ 2^k$.
令 $\mathbf{x} = [x_{w-1},\ldots,x_0]$，将其阶段为k位有 $\mathbf{x}’ = [x_{k-1},\ldots,x_0]$, 记 $x=\text{B2U}w(\mathbf{x}), x’ = \text{B2T}{k}(\mathbf{x}’)$, 则有 $x’ = \text{U2T}_k(x\mod\ 2^k)$.

其实两个操作在位级别上是相同的，只是最后按照不同编码表示而已。

整数运算

整数加法

对于满足 $0\leq x,y < 2^w$ 的整数 $x,\ y$ 有:

\[x+_w^u y = \begin{cases} x+y,\quad &x+y<2^w\quad &\text{正常} \\ x+y - 2^w,\quad &2^w \leq x+y < 2^{w+1}\quad &\text{溢出} \end{cases}\]

对于满足 $-2^{w-1} \leq x,y \leq 2^{w-1}-1$ 的整数 $x,\ y$，有:

\[x +_w^t y = \begin{cases} x + y - 2^w, \quad & 2^{w-1}\leq x+y \quad &\text{正溢出} \\ x + y, \quad & -2^{w-1} \leq x+y < 2^{w-1} \quad &\text{正常} \\ x + y + 2^w, \quad & x+y < -2^{w-1} \quad &\text{负溢出} \end{cases}\]

负溢出的情况下截断后最高位有效数字必为0，否则就不会出现溢出了。

这里值得注意的是补码加法与无符号数加法有相同的位级表示，用数学语言表示就是

\[x +_w^t y = \text{U2T}_w(\text{T2U}_w(x) +_w^u \text{T2U}_w(y)) = \text{U2T}_w[(x+y) mod 2^w]\]

这样计算机就可以用同一个算法进行加法，之后的乘法也是如此。

另外，模数加法形成了阿贝尔群，它是可交换的并且可结合的，存在单位元0，并且每个元素有一个加法逆元（位级操作上为取反后+1）：

对于满足 $0\leq x< 2^w$ 的整数 $x$ 有:

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

对于满足 $-2^{w-1} \leq x\leq 2^{w-1}-1$ 的整数 $x$，有:

\[-_w^t x = \begin{cases} \text{TMin}_x, \quad & x = \text{TMin}_w \\ -x, \quad & x > \text{TMin}_w \end{cases}\]

判断是否出现溢出的方法如下:

对于在范围 $0\leq x,y \leq \text{UMax}_w$ 的 $x,\ y$, 令 $s=x +_w^u y$，则计算发生溢出当且仅当 $s<x$(或者等价地$s<y$)。
对于在范围 $\text{TMin}_w \leq x,y \leq \text{TMax}_w$的 $x,\ y$, 令$s=x +_w^t y$，则
1. 发生正溢出当且仅当 $x>0,y>0,s\leq 0$，
2. 发生负溢出当且仅当 $x<0,y<0,s\geq 0$.

对于补码而言，判断是否发生溢出的代码如下：

int tadd_ok(int x, int y){
    int sum = x + y;
    int neg_over = x < 0 && y < 0 && sum >=0;
    int pos_over = x >= 0 && y >= 0 && sum < 0;
    return !neg_over && !pos_over;
}

注意以下写法是不对的：

int tadd_ok(int x, int y){
    int sum = x + y;
    return (sum - x == y) && (sum -y == x);
}

因为模数加法构成阿贝尔群，$(x+y-x)$ 的结果永远都是$y$.

虽然我们现在可以判断加法是否溢出，我们是无法直接简单地通过加法来判断减法是否溢出的：

int tsub_ok(int x, int y){
    return tadd_ok(x, -y);
}

当 $x>0,\ y = \text{TMin}_w$ 时，$-y = \text{TMin}_w$，此时一正一负判断为不溢出，然而实际是溢出的。

整数乘法

对于满足 $0\leq x,y < 2^w$ 的整数$x,\ y$ 有:
\[x *_w^u y = (x\cdot y)\ \text{mod}\ 2^w.\]
对于满足 $-2^{w-1} \leq x,y \leq 2^{w-1}-1$的整数$x,\ y$，有:
\[x *_w^t y = \text{U2T}_w((x\cdot y)\ \text{mod}\ 2^w).\]

无符号和补码乘法的位级操作是等价的，即给定长度为$w$的位向量 $\mathbf{x}, \mathbf{y}$，用补码形式来定义整数 $x,y$，用无符号形式来定义整数 $x’, y’$，则有

\[\text{T2B}_w(x *_w^t y) = \text{U2B}_w(x' *_w^u y').\]

检测整数乘法是否溢出的代码如下：

int tmult_ok(int x, int y){
    // first way:
    int p = x * y;
    return !x || p/x == y;

    // second way:
    int64_t p = x*y;
    return p == (int)p;
}

证明思路如下：

$x$和$y$的乘积可以写作 $x\cdot y = p + t2^w$, 计算溢出当且仅当 $t\neq 0$.
$p$ 可以写作 $p = xq +r$，其中 $ r < x $.
可证明 $q=y$ 当且仅当 $r=t=0$.

在分配内存的时候尤其要注意溢出的情况，由此会产生很多安全漏洞！

乘以常数

C中变量x和k有无符号数$x$和$k$，且 $0\leq k < w$，则有x<<k得到数值 $x *_w^u 2^k$.
C中变量x和k有补码值$x$和无符号数$k$，且 $0\leq k < w$，则有x<<k得到数值 $x *_w^t 2^k$.

对于某个常数$K$，编译器会将$K$的二进制表达为一组01序列: $[(0\ldots 0)(1\ldots 1)(0\ldots 0)\ldots(1\ldots 1)]$，考虑一组从位置$n$到位置$m$的连续的1，我们可以用下面两种不同形式的一种来计算这些位对乘积的影响：

(x<<n) + (x<<(n-1)) + ... + (x<<m)
(x<<(n+1)) - (x<<m)

例：

x*17 == (x<<4) + x
x*(-7) == x - (x << 3)
x*60 == (x<<6) + (x<<2)
x*-112 == (x<<4) - (x<<7)

除以2的幂

C中变量x和k有无符号数$x$和$k$，且 $0\leq k < w$，则有x>>k得到数值 $\lfloor x/2^k \rfloor$.
C中变量x和k有补码值$x$和无符号数$k$，且 $0\leq k < w$，则有x>>k得到数值 $\lfloor x/2^k \rfloor$.

然而对于负数而言，移位会导致结果向下舍入，但我们更希望向零舍入，此时我们利用偏移(biasing)的方法来进行修正：

C中变量x和k有补码值$x$和无符号数$k$，且 $0\leq k < w$，则有(x+ (1<<k) - 1) >> k得到数值 $\lceil x/2^k \rceil$.

这里利用了性质：对于整数 $x,y(y>0)$，有 $\rceil x/y \rceil = \rfloor (x+y-1)/y \lfloor.$ 由此我们可以写出C语言计算 $x/2^k$的代码

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

例题：写一个函数计算$x/16$:

int bias = (x >> 31) & 0xF;
x = (x + bias) >> 4;

注意这里利用了算术右移以及掩码的性质。

一些C语言Interger puzzles


1. $x<0 \nRightarrow(x*2)<0$	可能会出现溢出
2. $ux \geq 0$	正确
3. $x \& 7 == 7 \Rightarrow (x«30)<0$	正确
4. $ux > -1$是错的	隐含的int转换为unsigned
5. $x>y \nRightarrow -x<-y$，注意TMin的情况	-(Tmin)=TMin
6. $x*x\geq 0$是错的	可能会出现溢出
7. $x>0 \&\& y>0 \nRightarrow x+y > 0 $	可能会出现溢出
8. $x\geq 0 \Rightarrow -x\leq 0$	正确
9. $x\leq 0 \nRightarrow -x \geq 0$	TMin
10. $(x \vert -x)»31 == -1$ 当$x\neq 0$的情况下成立	正确
11. $ux»3 == ux/8$	正确
12. $x»3 == x/8$ 当$x$为负数的时候不成立	正确
13. $x\& (x-1)!=0$当$x==2^k$的时候不成立	正确
14. $x+y == ux + uy$	正确，隐含转换
15. $x * \sim y + uy*ux == -x$	~y=-y-1,模数加乘具有交换性
16. $(x<y) == (-x>-y)$	注意y=TMin
17. $((x+y)«4)+y-x = 17y+15x$	正确，模数加乘具有交换性
18. $(ux-uy) == -(unsigned)(y-x)$	正确
19. $((x»2)«2) \leq x$	正确

浮点数

IEEE浮点表示

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

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

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

一个单独的符号位 $s$ 编码符号 $s$，
$k$ 位的阶码字段exp $=e_{k-1}\ldots e_0$ 编码阶数 $E$，
$n$ 位小数字段frac $=f_{n-1}\ldots f_0$ 编码尾数 $M$，但是编码出来的值也依赖于阶码字段的值是否为0.

在单精度浮点格式中，$s$,exp,frac字段分别为1位，$k=8$位，$n=23$位；在双精度浮点格式中，$s$,exp,frac字段分别为1位，$k=11$位，$n=52$位。

给定位表示，根据exp的值，被编码的值分为三种情况：

规格化的值：当exp的位模式既不全为0，也不全为1的时候，称为规格化的值，阶码字段被解释为偏置(bias)形式表示的有符号整数，阶码的值为 $\mathbf{E=e-bias}$，其中 $e$ 是无符号数，其位表示为 $e_{k-1}\ldots e_1e_0$(1-254,1-2046)，而bias是一个等于 $2^{k-1}-1$ (127,1023)的偏置值。由此产生的指数取值范围对于单精度是 $[-126,127]$，对于双精度为 $[-1022,1023]$。

小数字段frac被解释为描述小数值 $0\leq f < 1$，其二进制表示为 $0.f_{n-1}\ldots f_1f_0$，尾数定义为 $\mathbf{M=1+f}$，这样也叫做隐含的以1开头的表示(implied leading 1)，这样我们就可以轻松获得一个额外精度位。
非规格化的值 当阶码域全为0时，所表示的数是非规格化形式，在这种情况下，阶码值为$\mathbf{E=1-Bias}$，而尾数值为 $\mathbf{M=f}$，也就是不包含隐含的开头的1。

这种数有两个用途：
1. 提供了一种表示0的方法，因为使用规格化数必须使 $M\geq 1$,因此我们不能表示0，此时有+0.0和-0.0，在一些数值运算下被认为是不同的。
2. 非规格化数也用来表示那些非常接近于0.0的数，他们提供了一种属性称为逐渐下溢，其中，可能的数值分布均匀地接近于0.0.
特殊值 当阶码全为1时，如果小数域全为0，表示的则是无穷；如果小数域非零，表示的则是NaN，通常一些运算的结果不能是实数或者无穷的时候就会返回NaN。

下图是三种情况的位表示图例：

数字示例

假如我们有8位格式，阶码位 $k=4$ 位，尾数位 $n=3$ 位，则偏置量为 $2^{4-1}-1=7$，部分可能结果如下：

可以观察到最大非规格数和最小规格化数之间的平滑转变，这归功于我们对非规格化数$E$的定义。另外，阶数越高，两个数之间的间距越大。

还可以发现，假如我们将浮点数的位表达式解释为无符号整数，那么对于所有正数而言，它们就是升序排列的，负数正好相反，IEEE这样设计就是为了浮点数能够使用整数排序函数来进行排序。

这里举一些特殊的值：

值+0.0总有一个全为0的位表示。
最小的正非规格化值的位表示是最低有效位为1而其他所有位为0构成的，此时尾码值$M=f=2^{-n}$，阶码值 $E=-2^{k-1}+2$，因此 $V=2^{-n-2^{k-1}+2}$。
最大的正非规格化值的位表示是全为0的阶码字段和最低有效位为1而其他所有位为0构成的，此时尾码值 $M=f=1-2^{-n}$，阶码值 $E=-2^{k-1}+2$，因此 $V=(1-2^{-n})\times 2^{-2^{k-1}+2}$。
最小的正规格化值的位模式的阶码的最低有效位为1，其他为0，此时尾码值$M=1$，阶码值为 $E=-2^{k-1}+2$，因此 $V=2^{-2^{k-1}+2}$。
最大的正规格化值的位模式的阶码的最低有效位为0，其他为1，此时尾码值 $M=2-2^{-n}$，阶码值为 $E=2^{k-1}-1$，因此 $V=(2-2^{-n})\times 2^{2^{k-1}-1} = 2^{2^{k-1}}(1-2^{-n-1})$。
值1.0的位表示的阶码字段除了最高有效位为0外，其他位均为1，尾码字段均为0，此时 $M=1,E=0$。

例子：12345具有二进制表示[11000000111001] = $1.1000000111001_2\times 2^{12}$，此时我们丢掉开头的1，并且在末尾加10个0，来构造小数字段，得到二进制表示[10000001110010000000000]，位构造阶码字段，我们用13加上偏置值127得到140，二进制表示为[10001100]，再加上符号位0，就得到了二进制的浮点数表示[0 10001100 10000001110010000000000],观察到整数值二进制[11000000111001]，正好对应于等于1的最高有效位之前（这就是隐含的开头1）。

对于一个具有$n$位小数的浮点格式，不能准确描述的最小正整数为 $2^{n+1}+1$：当表示到 $2^{n+1}$ 之后，下一个数为 $2^{n+1}+2^{n+1}\times 2^{-n}=2^{n+1}+10$。

能够被准确描述的最大奇整数位 $2^{n+1}-1$。

舍入

舍入共有四种形式：向偶数舍入、向零舍入、向上舍入、向下舍入。

向偶数舍入可以叫做“四舍六入五留双”，例如，可以将1.234999舍入为1.23，1.235001舍入为1.24，1.235000舍入为1.24，因为4是偶数。

同样的，向偶数舍入可以应用到二进制小数上，我们将最低有效位的值0认为是偶数，1认为是奇数。一般来说，只有形如XXXXX.YYYY10000的二进制位模式才会向偶数舍入，其中最右边的Y是被舍入的位置。

例：

$10.010_2\Rightarrow 10.0$
$10.011_2\Rightarrow 10.1$
$10.110_2\Rightarrow 11.0$
$11.001_2\Rightarrow 11.0$

浮点运算

前面我们看到了整数加法形成了阿贝尔群，实数的加法同样如此，但是我们要考虑舍入的影响。我们定义 $x+^f y = \text{Round}(x+y)$。

加法运算过程：$(-1)^{s_1}M_12^{E_1} +^f (-1)^{s_2}M_2 2^{E_2} \rightarrow (-1)^sM2^E(E_1\geq E_2)$:

$S,M$位对齐后的加法，$E=E_1$.
如果$M\geq 2$，$M$右移一位，$E$加1.
如果$M<1$，$M$左移$k$位，$E$减$k$.
如果$E$超出范围则溢出，
舍入到frac精度范围。

可以看到它有以下性质：

运算是可交换的，即$x+^f y = y +^f x$，
运算是不可结合的，例如$(3,14+1e10)-1e10=0.0,\ 3.14+(1e10-1e10)=3.14$，
大多数值在浮点加法下存在逆元，但是无穷和NaN是例外，
浮点加法满足单调性：如果$a\geq b$，那么除了NaN，对于任何$x$的值都有$x+a\geq x+b$。整数加法是不具备这个性质的，
0是加法的单位元。

浮点数乘法的定义也是类似的$x\times^fy=\text{Round}(x\times y)$，浮点乘法有以下性质：

乘法是封闭的，是可交换的，有乘法单位元1.0，
不可结合的，例如$(1e201e20)1e-20$为正无穷，而$1e20(1e201e-20)$为$1e20$.
对于加法没有分配性，例如$1e201e20-1e201e20$会得到NaN，
对于任何$a,b,c$，并且都不为NaN，则乘法也满足单调性。

C语言中的浮点数

int转换为double，数字不会溢出但是可能被舍入。
int或float转换为double，能够保留精确数值。
double转换成float，可能会溢出，也可能会舍入。
float或double转换为int，如果没有溢出的话，值会向零舍入。

例子：x,f,d分别为int, float, double.

x==(int)(double)x
x!=(int)(float)x
d != (double)(float)d
f == (float)(double)f
f == -(-f)
1.0/2 = 1/2.0
d*d>=0
(f+d)-f != d：浮点加法不存在结合律（后面的-f无法移动到前边）
d>f => -d < -f

x,y,z为int，dx,dy,dz = (double)x,y,z.

(float) x == (float)dx dx保留了x的所有精度，所以转化为float是一样的。
dx-dy == (double)(x-y) 错误，x-y有可能会溢出
(dx+dy)+dz == dx+(dy+dz) 正确，因为三个int相加不会出现舍入误差
(dx*dy)*dz == dx*(dy*dz) 正确
dx/dx == dz/dz 错误，当dx为0，dz不为0的时候不相等。

csapp