全文内容主要来自对课程《深入浅出计算机组成原理》的学习笔记。
11 | 二进制编码
逢二进一
源码表示法（最左侧位的 0/1 代表整体正负）：
$0011 = + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 3$
$1011 = - (0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0) = -3$
ASCII 码（American Standard Code for Information Interchange，美国信息交换标准代码）但此时0可以表示成 0000 和 1000，一对多，不合适。
补码表示法（最左侧位仅表其位负）：
$1011 = -1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0) = -5$
如此4位的话，可以表示-8到7这16个整数。
字符串的表示
ASCII 码（American Standard Code for Information Interchange，美国信息交换标准代码）。
它存储了128个字符和8位二进制数的映射关系，一一对应。
表示逻辑case：
a：ASCII 里第 97 个，二进制表示为 01100001，而上图映射表中为十六进制表示，每4位一组即可，即0110|0001=61(16进制)=6x16+1=97(10进制)；
9：ASCII 里第 57 个（字符9不是整数9），二进制表示为 00111001，而上图映射表中为十六进制表示，每4位一组即可，即0011|1001=39。
一个弊端：
如果是int32最大数2147483647，二进制只需要32位，但上述的拆分字符串表示法就需要8x10=80位。
不管是整数也好，浮点数也好，采用二进制序列化会比存储文本省下不少空间。
当使用国家多了后，上述的128个字符表示就不够了，就需要其他的字符映射关系。日常说的 Unicode，其实就是一个字符集，包含了 150 种语言的 14 万个不同的字符。其可以用UTF-8 来编码成二进制，当然也可以用GT-32 编码等，只是不同的编码对应关系。
12 | 理解电路
电报原理
古时候军队的金和鼓、烽火、灯塔等都是信号传递，通过不同的组合表达不同的意思，但都是二进制的类似。
电报传输的信号有两种：
- 短促点信号（dot 信号），1
- 长的划信号（dash 信号），0
那么“SOS”就可以表示为111000111。
电报机本质是“蜂鸣器 + 电线 + 开关”
理解继电器
上述电报机的问题：如果电线太长，使得电阻大，蜂鸣器电压不足会不响。
解决办法：在路线中，插入一个机器，将接收的信号原模原样的发送出去，这就是继电器。
继电器一般就用“螺旋线圈 + 磁性开关”构建。通过线圈和开关的组合，也可以创造出“与（AND）”“或（OR）”“非（NOT）”等逻辑电路。
13 | 加法器
门电路图，就是计算机硬件的积木，组合成cpu的核心模块。
- 与门：1、1 输出 1，其他 0；
- 或门：有任一个 1 输出 1，其他 0；
- 非门：1 输出 0，0 输出 1；
- 或非门：或门+非门，0、0 输出 1，其他均 0；
- 异或门：相同（同 0 或同 1）则输出 1，否则输出 0；
- 与非门：与门+非门，1、1 输出 0，其他均 1。
异或门和半加器
两个二进制无符号整数相加，对于个位需要判断的就是进位与个位。实际上对应2种门电路：
- 个位：异或（XOR）
- 进位：与门
将上述2种电路打包就可以得到一个半加器（Half Adder）。
全加器
上述强调了个位的加法可以通过半加器（Half Adder）实现，但再往后面的位半加器就不够用了，原因很简单，还需要考虑上一位的进位。
解法：全加器（Full Adder），用两个半加器和一个或门。
- 输入：进位信号、加数和被加数
- 输出：进位信号、和
如此，两个 8 bit 数的加法可以通过8个全加器串联：
溢出：整数是没有位置标记溢出的，比如 int32。实际上，计算结果是否溢出是通过加法器的结果中，将溢出输出给到硬件中其他标志位里实现的，也是硬件层面的支持。
总结
我们通过门电路、半加器、全加器可以搭建出类似加法器这样的组建，一般把这些用来做算术逻辑计算的组件叫作 ALU，算术逻辑单元。
14 | 乘法器
从 $13 \times 9$ 开始，二进制的方式和10进制一样：
顺序乘法
对于上述乘法过程，只需要简单的加法器、一个可以左移一位的电路和一个右移一位的电路，就能完成整个乘法。过程如下所示：
弊端：不同位置间串行，复杂度高。
并行加速
朴素的思想就是通过并行把 O(N) 的时间复杂度，降低到 O(logN)。
如下图所示，通过并联更多的 ALU，加上更多的寄存器，让不同位置的乘法并行计算，然后进行结果的合并。
电路并行
上述的算法并行实际上还是比较慢，前后需要有结果的依赖等待。
例如每一个全加器，都要等待上一个全加器，把对应的进入输入结果算出来，才能算下一位的输出。这个每一步等待的时间叫门延迟（Gate Delay），一般作“T”。
一个全加器，其实就已经有了 3T 的延迟（进位需要经过 3 个门电路）。
加速思路：空间换时间
把原来需要较少的，但是有较多层前后计算依赖关系的门电路，展开成需要较多的，但是依赖关系更少的门电路。
如上图，例如一个 4 位整数最高位是否进位，展开门电路图只需要 3T 的延迟就可以拿到进位结果。64 位的整数，多复制上述电路即可。
计算机通过更多的晶体管，就可以拿到更低的门延迟，以及用更少的时钟周期完成一个计算指令。
15 | 浮点数和定点数（上）
如何用二进制表示所有的实数?
浮点数的不精确性
看下面代码结果，可以发现计算机简单的计算精度也有丢失。
1 | 0.3 + 0.6 |
计算机一般用 16 或 32 位来表示数，32 个比特，只能表示 2 的 32 次方个不同的数，差不多是 40 亿个。而这里必然是使用了其他表示法导致精度丢失。
定点数
一个朴素的想法：32位拆成8段4位，每4个bit可以表示0-9整数。那么把前6段作为整数部分，后2段作为小数部分，就可以表示0-999999.99这1亿个数。
上述叫BCD编码，一般在超市、银行使用。
缺点：
- 浪费；
32位从40亿的表示能力降为了1亿，且范围不够用。
- 没办法表示更大更小数；
物理和数学上的高精度需要就不行。
浮点数
解决方案：浮点数（Floating Point），也就是 float 类型。
思想：科学计数法。
IEEE标准，有2个基本格式：
- 32 bit，即 float / float32；
- 64 bit，即 double / float64。
以 float32 为例：
- s：符号位，1 bit，表正负；
- e：指数位，8 bit，用 1～254 映射 -126～127；
- f：有效数位，23 bit。
表示形式：
此外，还有一些特殊值表示：
| e | f | s | 浮点数 |
|---|---|---|---|
| 0 | 0 | 0 or 1 | 0 |
| 0 | !=0 | 0 or 1 | 0.f |
| 255 | 0 | 0 | 无穷大 |
| 255 | 0 | 1 | 无穷小 |
| 255 | !=0 | 0 or 1 | NAN |
case：0.5
s = 0,f = 0, e = -1, $(-1)^0 \times 1.0 \times 2^{-1}=0.5$
因此，float32 能表示的绝对值范围是 $1.17 \times 10^{-38} to 3.40 \times 10^{38}$。
上述范围大约由 1.9999999 ^(2^127) 和 1.0000000 ^ (2^-126) 转成科学记数法得到。
16 | 浮点数和定点数（下）
浮点数的二进制转化
以 9.1 换算成float为例，整数部分9，换算成 1001。
对于小数部分，先看二进制小数转10进制。
把二进制小数点后的每一位，都对应的 2 的 -N 次方。如 0.1001 可转化成
反过来，将十进制的小数转为二进制：
则和整数的二进制表示采用“除以 2，然后看余数”的方式类似；
即乘以 2，记录是否超过 1，剩余差值则是乘积结果（<1）或者 乘积结果-1（>1）.
如下方示例：
9.1 拆成 9 和 0.1，前者是 1001，后者通过上述算法（如下表过程） .000110011…(23位)。
最终有：$1001.000110011 \times 2^0$ 或小数点左移3位后 $1.001000110011 \times 2^3$。
二进制的存储如下：
注意：指数位 e 是用 1～254 映射 -126～127，所以 3 需要用 3 + 127 = 130 来映射的
因此，将其再转为十进制，就是9.09999942779541015625，精度有一定损失。
加法和精度损失
先对齐、再计算。
以 0.5 + 0.125 为例，过程如下表所示：
| 步骤 | 符号位s | 指数位e | 有效位1.f |
|---|---|---|---|
| 0.5 | 0 | -1 | 1.00… |
| 0.125 | 0 | -3 | 1.00… |
| 0.125对齐指数位 | 0 | -1 | 0.01 |
| 0.5+0.125 | 0 | -1 | 1.01 |
问题：
在有效位对齐的时候，指数位较小的需要进行右移，会使得最右侧的有效位丢失进而造成精度丢失，除非最右侧丢失的都是0。
case:
Java 程序，让一个值为 2000 万的 32 位浮点数和 1 相加，你会发现，+1 这个过程因为精度损失，被“完全抛弃”了。
Kahan Summation 算法
用一个循环相加 2000 万个 1.0f，最终的结果会是 1600 万左右，而不是 2000 万。因为1600w之后精度就丢失了。
1 | public class FloatPrecision { |
Kahan Summation 算法可以解决，其原理就是：
在每次的计算过程中，都用一次减法，把当前加法计算中损失的精度记录下来，然后在后面的循环中，把这个精度损失放在要加的小数上，再做一次运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class KahanSummation {
public static void main(String[] args) {
float sum = 0.0f;
float c = 0.0f;
for (int i = 0; i < 20000000; i++) {
float x = 1.0f;
float y = x - c;
float t = sum + y;
c = (t-sum)-y;
sum = t;
}
System.out.println("sum is " + sum);
}
}
1 | public class KahanSummation { |