概念
- 字节，八位的位块，最小的可寻址内存单位
- 虚拟内存，机器级程序将内存看成一个非常大的字节数组，称为虚拟内存。
- （虚拟）地址，内存的每个字节都由一个唯一的数字标示，这个数字叫做这个字节的地址。
- 虚拟地址空间，所有（虚拟）地址的集合称为虚拟地址空间。
- 字长，指明指针数据的norminal size。一个字长为w位的机器，虚拟地址的范围从0到$2^w -1$。
- 大端和小端。大端，最高有效字节在最前面；小端，最低有效字节在最前面。用于跨多字节的对象，它的地址是什么，如何排列这些字节。在网络传输二进制数据时，可能会出现问题。
- 算术右移和逻辑右移。算术右移在左端补k个最高有效位的值，而逻辑右移在左端补k个0，C语言没有规定对于有符号数使用哪种右移，但是几乎所有的编译器和机器组合都对有符号数进行算术右移。对于无符号数，右移必须是逻辑右移。
信息的表示和处理
浮点数表达的范围大，但是确实近似的，精度有限。如$(3.14+1e20) - 1e20$的值是$0.0$，而$3.14+(1e20-1e20)$的值是$3.14$。
而整数的表示范围小，但是是精确的。比如：$200\times 300\times 400\times 500$会溢出，
信息的存储
虚拟内存和虚拟地址空间
字节是八位的位块，它是最小的可寻址内存单位。机器级程序将内存看成一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字标示，这个数字叫做这个字节的地址。虚拟地址空间，所有（虚拟）地址的集合称为虚拟地址空间。
字数据大小
每台计算机都有一个字长，指明指针数据的标称大小（norminal size）。虚拟地址就是用这样的一个字编码的，字长决定的最重要的参数就是虚拟地址空间的最大大小。一个字长为w位的机器，虚拟地址的范围从0到$2^w -1$。
寻址和字节顺序
为了寻找跨越多字节的程序对象，我们必须建立两个规则：
- 这个对象的地址是什么。在几乎所有的机器上，多字节对象都存储为连续的字节序列，对象的地址就是所使用字节中的最小的地址。
- 如何在内存中排列这些字节。通常有两个规则，大端，最高有效字节在最前面；小端，最低有效字节在最前面。字节顺序在以下三个地方变得很重要：
- 在网络传输二进制数据时，可能会出现问题。
- 阅读表示整数数据的字节序列时，通常是在检查机器级程序时。
- 编写规避正常的类型系统的时候，比如C语言的强制类型转换时，把一个4字节的int转换成一个字符数组，大端小端输出的结果是不一样的。
一般情况下，数值变量在各类机器/操作系统中除了大端小端的区别外，没有其他区别。而指针变量在各类机器/操作系统之间差异显著。
字符串表示
使用ASCII码作为字符码的任何系统，它们对于字符串的表示是相同的。
函数表示
指令编码在不同的机器上是不同的。不同的机器类型使用不同的而且不兼容的指令和编码方式。
布尔代数和C语言的位运算
与或非，异或，这四个操作，都是对位进行操作的。更多关于位运算的介绍可以查看。
C的逻辑运算和移位运算
逻辑运算一定要记得加括号。
算术右移和逻辑右移。算术右移在左端补k个最高有效位的值，而逻辑右移在左端补k个0，C语言没有规定对于有符号数使用哪种右移，但是几乎所有的编译器和机器组合都对有符号数进行算术右移。对于无符号数，右移必须是逻辑右移。
整数表示
整数的类型
ISO C给出了C中每个整形的最小取值范围（至少要满足这个范围，可以更大）。但是具体每个整形的长度是多少是和实现相关的。几个特殊的类型int32_t和uint32_t，``int64_t，uint64_t`，是和实现无关的，它们的长度通过类型中的数字显示出来。
无符号数的编码
假设一个w位的整数数据类型，用bit vector $x = [x_{w-1}, \cdots, w_0]$表示，其中每一位的取值都是0或者1。用一个函数$B2U_w$表示：
无符号数编码的定义
对于bit vector $x = [x_{w-1}, \cdots, w_0]$
$$ B2U_w (x) = \sum_{i=0}^{w-1} x_i 2^i $$
将一个长度为w的bit vector映射到一个非负整数。
有符号数的编码
补码
补码（Two’s Complement）是用来表示有符号的一种方法。这个定义中，将字的最高有效位解释为负权。用函数$B2T_w$表示：
补码的定义
对于bit vector $x = [x_{w-1}, \cdots, w_0]$
$$ B2U_w (x) = - x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i $$
最高有效位$x_{w-1}$也称为符号位，它的权重是$-2^{w-1} $。
反码
反码（Ones’ Complement）：最高有效位的权重是$ - (2^{w-1} -1) $而不是$ - 2^{w-1} $，其余的地方和补码一样：
$$ B2O_w (x) = - (x_{w-1} 2^{w-1} - 1) + \sum_{i=0}^{w-2} x_i 2^i $$
原码
原码（Sign-Magnitude）：最高有效位是符号位，用来确定剩下的位是正权还是负权：
$$ B2S_w (x) = (-1)^{x_{w-1} } \cdot \sum_{i=0}^{w-2} x_i 2^i $$
区别和联系
原码和反码，它们对于数字0都有两种不同的表示方法。注意，反码和补码，反码是Ones’而补码是Two’s，因为对于一个正整数$x$，求$-x$的表示时，使用反码是$[111…111]w - x$，而补码是$[1000…000]{w+1}-x$。
一个长度为$w$位的bit vector，可以解释成补码，也可以解释成无符号编码，当最高有效位为0时，它们都表示正整数；当最高有效位为$1$时，解释为补码时，它是负数，解释为无符号编码时，它是一个正整数，它们两个的绝对值相加等于$2^{w+1} $，
有符号数和无符号数的转换
在C语言的大多数实现中，处理同样字长的有符号数和无符号数的转换的规则是：数值可能会改变，但是bite vector不变。
字长为16的整数补码
0
0000 0000 0000 0000
-1
1111 1111 1111 1111
-2^15
1000 0000 0000 0000
2^15-1
0111 1111 1111 1111
补码表示的有符号数转换为无符号数
给定bit vector的补码表示的无符号数和无符号数之间的关系可以表示为函数$T2U$：
对于满足$TMin_w \lt x \lt TMax_w $的$x$有：
$$T2U_w(x) = \begin{cases}x, x\ge 0 \\ 2^w + x\lt 0\end{cases}$$
无符号数转换为补码表示的有符号数
对于满足$0\le u \le UMax_w$的$u$，有：
$$U2T_w(u) = \begin{cases}u, u\le TMax_w \\u - 2^w\gt TMax_w\end{cases}$$
有符号数和补码表示的无符号数之间的关系
只要记住一条就行，上面的两个转换就能推导出来。
一个字长为$w$，最高有效位为$1$的bit vector，用补码方式解释为负数A，用无符号编码解释为整数B，A和B的绝对值之和为$2^w $。为什么？
假设字长为8，给定一个正整数$x$，比如$x=9$，无符号编码为$0000 1001$，$-x$的补码编码怎么计算，$2^8 - 9$，即$10000 0000 - 0000 1001$，结果是$1111 0111$。
$1111 0111$表示$-x$的补码，绝对值$x$的无符号编码表示是$0000 1001$，用无符号编码解释$1111 0111$，显然，$1111 0111$加上$0000 1001$，等于$2^w $。
C语言中的有符号数和无符号数
对于相同字长的整形和无符号整形，如果一个运算的两个运算数一个是有符号的，一个是无符号的，C语言会隐式的将有符号参数强制转换为无符号的。
整形提升
无符号数的扩展，在左面添加0，叫做零扩展。
有符号数的扩展，在左面添加最高有效位的值，叫做符号扩展。
当强制类型转换同时涉及到操作数的大小和符号变化时，先改变操作数的大小，然后再改变操作数的符号。比如short转换成unsigned，先把short转换成int，然后再把它转换成unsigned的
整形截断
无符号数的截断
将长度为$w$的bit vector $\mathbf{x}$，丢弃最高位的值，将其截断为长度为$k$的bit vector $\mathbf{x’}$。令$x=B2U_w(\mathbf{x})$，$x’=B2U_k(\mathbf{x’})$，则$x’= x mod 2^k $。
补码数值截断
将长度为$w$的bit vector $\mathbf{x}$，丢弃最高位的值，将其截断为长度为$k$的bit vector $\mathbf{x’}$。令$x=B2U_w(\mathbf{x})$，$x’=B2T_k(\mathbf{x’})$，则$x’=U2T_k(x mod 2^k)$。
先截断为无符号数，然后将无符号数转换成有符号数。
有符号数和无符号数的建议
- 相同长度的无符号数和有符号数，在运算中有有符号数的话，就会把有符号数转换成无符号数。比如for循环中，
for(unsigned i = 10; i >= 0; --i)，永远不会跳出for循环，因为当$i=0$时，--i就相当于得到了有符号数$-1$，而$-1$的补码形式和无符号数的$2^w -1 $的编码是一样的，而这里就是得到了$2^w -1$。 - 两个无符号数相减。永远不可能小于0。
整数运算
无符号数加法
无符号数加法
无符号数加法：
对于满足$0\le x, y \lt 2^w $的无符号数$x$和$y$有：
$$x+y = \begin{cases}x+y, x+y \lt 2^w, 正常\\ x+y -2^w , 2^w \le x+y \le 2^{w+1}, 溢出 \end{cases}$$
算术溢出
当$x+y$的和超出$w$位能表示的最长长度时，就说它发生了算术溢出。
加法逆元
加法逆元，对于每一个值$0\le x \lt 2^w $，都存在一个值$0\le y \lt 2^w $$，使得$x+y = 0$，这个$y$就叫做$x$的加法逆元，反过来，$x$也是$y$的加法逆元。
$$y = \begin{cases}x, x=0\\ 2^w -x, x \gt 0\end{cases}$$
补码加法
补码加法：
对于满足$- 2^{w-1} \le x, y \lt 2^{w-1} -1 $的有符号整数$x$和$y$有：
$$x+y = \begin{cases}x+y - 2^w, x+y \ge 2^{w-1} \\ x+y, - 2^{w-1} \le x+y \lt 2^{w-1} \\ x + y + 2^w, x+y \le 2^{w-1} \le 2^{w+1} \end{cases}$$
可以先进行无符号数加法，然后将结果使用$U2T_w$转换成有符号数。为什么可以这样子呢？是因为，补码加法和无符号数加法有完全相同的位级表示，在很多实现中执行补码加法和无符号数加法的机器指令一样。
补码的非
这个非是什么意思？？？怎么感觉有问题，就是用$2^w - x$呗。不管怎么样，这一接就是介绍补码的逆元，只要$x+y % 2^2 =0$就行了。
对于满足$TMin_w \le x \le TMax_w$的每个数字$x$都有加法逆元$y$：
$$y = \begin{cases}TMin_w, x=TMin_w\\ -x, x\gt TMin_w \end{cases}$$
无符号乘法
对于满足$0\le x, y \lt 2^w $的w位无符号数$x$和$y$有，它们的乘积需要$2w$位来表示，而C语言中，无符号乘法定义为$w$位，从$2w$位中截取低$w$位，作为结果：
$$ x\times y = ((x\cdot y) mod 2^w)$$
补码乘法
对于满足$- 2^{w-1} \le x, y \lt 2^{w-1} -1 $的有符号整数$x$和$y$，先将它们当做无符号数相乘，然后截断为$w$位，再将无符号数转化成有符号数：
$$ x\times y = ((x\cdot y) mod 2^w)$$
为什么可以这样子。因为对于无符号和补码乘法来说，它们具有相同的位级表示。即：
$$T2B_w(x\cdot y) = U2B(x’ \cdot y’)$$
给定bit vector $\mathbf{x}, \mathbf{y}$，分别用无符号整数编码和补码进行编码，得到$x’,y’, x, y$。最后它们乘出来的结果截断为$w$位之后还是一样的。
乘以常数
整数乘法的指令相当的慢，需要十个或者更多个时钟周期，而其他整数运算（加法，减法，位级运算和移位），都只需要一个时钟周期。所以，编译器会尝试使用移位和加法的组合运算来提高运算速度。
对于和2的幂相乘的无符号乘法来说，其实就相当于左移一个数值。而固定大小的补码算术运算的位级操作和其无符号运算等价。
除以2的幂
浮点数的表示
IEEE754标准。
二进制小数
将一个含有小数值的二进制数转换为十进制。给出如下形式的二进制小数：
$$b_mb_{m-1}\cdots b_1b_0.b_{-1}b_{-2}\cdots b_{-n-1}b_{-n}$$
它表示的数字$b$定义如下：
$$b=\sum_{i=-n}^m 2^i\times b_i$$
小数点后的位，它的权值为$2$的负幂。
IEEE浮点运算
示例
舍入
浮点运算
C语言中的浮点数
参考文献
1.《CSAPP》第五版