Crash Course Computer Science（1-10）

约 4568 字大约 15 分钟

2019-07-27

在 B站发现了一门好课《Crash Course Computer Science》（计算机科学速成课），虽然讲“速成”有点急功近利的意思，但这门课从计算机的历史开始讲起，几乎涵盖了从布尔逻辑到二进制、从硬件到软件、从编译原理到操作系统、从计算机网络到信息安全等等计算机科学的知识，作为一种科普，扩充知识面还是相当不错的。

课程地址：

全集笔记：

P1 计算机的早期历史

计算机起源于人们计算的需求，最早被发明的是算盘，用来计算大数字，后来又出现了很多变种应用于各行各业，比如星盘让船可以在海上计算纬度，计算尺帮助计算乘除法，各种时钟用于计算日出、潮汐、天体位置等。而 Computer 一词，最初是指以计算为职业的人，后来才慢慢代指机器，其中以 1694 年发明的“步进计算器”最出名，它通过转动齿轮，带动数字加减过程的进位。1822年，Charles Babbage 提出了一种“差分机”，用于解决同一个公式下不同参数的计算，但这个项目最终失败了。在研究差分机期间，Charles Babbage 还构想了一种“分析机”可以做不同的运算，由于这个思想太超前，所以同样没有建成。但是分析机的思想奠定了 计算机可以自动完成一系列操作 这个基础。英国数学家 Ada 根据分析机的理念，设计了假想的程序，所以 Ada 被认为是世界上第一个程序员。

1880年，美国人口快速增长，人口普查局找到 Herman Hollerith 制造一款打孔卡片制表机，用传统机械来计数，用电动结构连接其他组件，大大提升了统计的数据。企业开始意识到计算的价值，之后 Hollerith 成立了制表机器公司，在1924年跟其他机械公司合并后，成为国际商业机器公司（International Business Machines），即 IBM 。

步进计算器发明者 Gottfried Leibniz：

让优秀的人浪费时间算数简直是侮辱尊严，农民用机器能算得一样准。

P2 电子计算机

IBM 在 1944年建造了哈佛马克一号机电计算机，它的基本组件是 继电器（一种用电控制的机械开关）。但继电器是机械结构，本身有重量，而且频繁开闭容易坏，所以效果不是很理想。早在 1904年，英国物理学家就发明了真空管（二级管），1906年美国发明家往真空管加入了控制电路，变成 三极管，达到了跟继电器一样的效果，从此计算机从机械走向了电子。世界上第一台通用，可编程的电子计算机是ENIAC，每秒能进行5000次加法运算。

三极管是其他电子器件的基础，但也不是完美的，经常烧坏，1947年，贝尔实验室发明了 晶体管，晶体管涉及的原理十分复杂，简单地说，就是两个电极之间有一种材料隔开，这种材料有时导电，有时不导电，这叫做 半导体。晶体管通过改变导电性让电荷流动或不流动，达到跟继电器和三极管一样的效果。自那以后，IBM 建造了很多纯晶体管的计算机，计算机的体积也越来越小，最终让计算机从实验室走向办公室，再走向普通家庭。

有趣的是，晶体管的主要材料是硅，而彼时晶体管和半导体的开发集中在美国的加州，所以那个地方被称为硅谷。连晶体管发明者之一 William Shockley 都搬了过去，成立了肖克利半导体，里面的员工后来成立了仙童半导体，里面的员工后来又成立了英特尔。

从继电器到三极管再到晶体管，我们只做了一件事，那就是让开关开闭得更快，而且更不容易损坏，仅此而已。

P3 布尔逻辑和逻辑门

用两种状态表示信息叫做「二进制」，二进制可以用 true 和 false ，或者 1 和 0 来表示。计算机二进制的理论来自于布尔代数，在布尔代数中，变量的值只有 true 和 false 两种，运算法则有与、或、非、异或（AND、OR、NOT、XOR）等。晶体管的控制信号表示输入，结果表示输出。用不同的晶体管组合来实现不同的布尔逻辑运算，这就是逻辑门。

与（AND）：两个值都为true，结果才为true
或（OR）：两个值只要有一个为true，结果才为true
非（NOT）：取反
异或（XOR）：两个值相同时，结果为 false ，否则为 true

P4 二进制

在十进制中，只有 0-9 十个数字，想表示更大的数字，加位数就行了，比如51，5在十位表示5个10。在二进制中只有 0 和 1 两个数，想表示更大的数字，也是加位数，这样一个位，我们称之为 比特（bit），比如 101，表示 1个1 + 0个2 + 1个4 = 5。二进制逢二进一，需要比十进制更多的进位，在计算机里，大部分操作都是八位八位这样子计算的，比如 11011010，所以我们把八个位称为一个 字节（byte），8位能表示256种不同的状态，在8位的游戏里，只有256种颜色，而16位是65536种。

就跟 1000克 = 1千克 一样，1000 byte = 1 kilobyte（千字节） = 1KB = 8000 bits ，以此类推， MB是百万字节（Mega）， GB是十亿字节（Giga）。可是在计算机中，还有另外一种计算方式，那就是1千字节 = 2^10 byte = 1024 byte ，在 Linux 系统中为了加以区分，常用 1 KiB 这样的写法跟 1KB 区分开来，前者是 1024 byte，后者是 1000 byte。

为了表示负数，我们把第一位作为符号位，1表示负，0表示正。类似于科学计数法，在32位系统中，为了表示小数（浮点数），我们会取第2-9位作为指数，剩下23位作为有效位数。

除了数字，我们也要在计算机中表示文字。最简单的方法就是编码，ASCII（美国信息交换标准代码）发明于1963年，采用7位编码，可以表示128个不同的值，我们的每一个英文字母、数字和常用符号都对应一个值，比如 a 的编码是 97，当计算机遇到二进制97的编码时，就在显示器上显示 a 。随着计算机在全世界的流行，各个国家都推出了自己的字符编码，比如中国的 GBK，后来由于实在是太混乱了，Unicode 就诞生了——统一了所有编码的标准。Unicode是16位的，足以解决所有国家的编码问题。

就像用二进制编码来表示不同的字符一样，其他格式的二进制编码，如 .mp3 / .jpg / .avi 等等都是特定的二进制编码，用来编码音乐、图片和视频。所以，在计算机中，归根结底都是一长串的 0 和 1 罢了。

P5 算术逻辑单元（ALU）

我们用二进制表示数字，但真正重要的是有意义地处理数字。 算术逻辑单元（ALU） 是计算机负责运算的组件，ALU包含一个算术单元（Arithmetic）和一个逻辑单元（Logic）。算术单元我们可以用一个 XOR 和一个 AND 组装成一个半加器，两个半加器组装一个全加器，再由全加器组装8位加法器。在8位加法器中，如果两个数相加超过了11111111，那么我们就称 溢出(overflow) 了。逻辑单元是负责逻辑运算的组件，比如 AND、OR、NOT、XOR，以及一些简单的数值测试（如一个数是否负数）。

在8位的ALU中，我们有两个8位的输入 A 和 B，以及一个4位的操作码告诉ALU应该执行什么操作，例如用操作码1000表示做加法，用1100表示做减法。ALU有一个8位的输出，以及一些标志输出，例如是否溢出标志，是否为零标志。

P6 寄存器和内存

算术逻辑单元可以对数字进行运算，而 寄存器和内存负责对结果进行保存。断电后丢失的存储称为随机存储（RAM），而断电后永久保存的称为持续存储（ROM）。用一个 AND 门，一个 OR 门，一个 NOT 门能制作一个 AND-OR 锁存器，可以存储一位。锁存器加一些额外的逻辑门，可以实现允许写入和允许读取，用这个来控制该位是否允许被读写。将8个一位锁存器并排，就可以存储8位的二进制数了，一组这样的锁存器称为 8位寄存器，当然，也有16位、32位或64位的寄存器。

在64位的寄存器中，每个锁存器都要有线来控制读写显得很麻烦，可以用矩阵来级联，矩阵一横一竖的交叉点即是特定位置的锁存器。这样，对于256位的寄存器，只需要35条线（1条数据线、1条允许写入线、1条允许修改线、16行+16列矩阵线用于选择锁存器）。例如，要选择第12行第8列的锁存器，可以启用对应的矩阵线，其交点就是目标，对应的矩阵线用二进制标记就是 1100 1000，这就是内存地址概念的由来。内存的一个重要特性是，可以随时访问任何位置，因此叫 随机访问存储器（RAM）。

如今，无论是 SRAM，DRAM 或其他 RAM，从根本上都是矩阵层层嵌套，来存储大量信息罢了。

P7 中央处理器（CPU）

CPU负责执行程序。程序由一个个操作组成，这些操作称为 指令（instruction），如果是计算指令，CPU 会与 ALU 通信进行计算操作，如果是内存指令，CPU 会与内存通信，然后读写值。

程序可以放在内存里，指令也一样可以放在内存里。在内存里放一系列8位二进制数，前4位表示 操作码，即 CPU 应该执行的指令，后4位表示数据来自哪里（内存地址或某个寄存器ID），此外，我们还需要两个寄存器来组建我们的 CPU，一个负责追踪程序运行到哪里了，称为 指令地址寄存器，存储着当前指令的内存地址，另一个负责存当前指令，称为 指令寄存器。

CPU 启动时，第一个步骤是 取地址，CPU会往指令地址寄存器上的地址去取需要的指令，例如在0地址取到00101110，这个数会被存入指令寄存器中。第二个步骤是 解码（decode），取到的00101110指令表示什么意思？需要由 控制单元 进行解码，控制单元本质上也是一些逻辑门的组合，它可以解释例如前4位0010是存储操作，后4位1110是应该存入的地方。知道该做什么操作和往哪里存储后，第三个步骤就可以执行了。CPU会有一些线连接到内存，打开内存对应地址的允许写入线，然后往里面写值。

执行完毕后，指令地址寄存器的值自动加一，一个CPU操作就完成了。像这样，CPU 取指令 → 解码 → 执行 → +1 这样一个周期称为 时钟周期。现代PC或手机一秒能达到10亿次时钟周期。所谓超频或降频，就是让 CPU 周期更快或更慢的技术。

P8 指令和程序

CPU的强大之处在于可编程，写入不同的指令就会执行不同的任务。

假设在内存地址0的地方，存放着00101100，前四位是操作码表示 LOAD_A ，后四位表示内存地址14，写成人类容易理解的内容是 LOAD_A 14，意思是，从内存地址14的位置取数放到寄存器A，内存地址14假设存放着数字3，那么数字3就会被放到寄存器A。同样的，内存地址1的地方，存放着 LOAD_B 15，CPU就会从内存地址15的地方取数放到寄存器B，最后，当 CPU 遇到 ADD B A，表示把寄存器B的值加到寄存器A上，遇到 STORE_A 13，表示把当前寄存器A的值存入内存地址13。这样就完成了一次加法。

除了 LOAD、ADD 和 STORE，CPU还有其他一些指令，SUB减法、JUMP跳转（用于实现循环和分支）、JUMP_NEGATIVE条件跳转、HALT停止（没有这个指令程序会一直执行下去），

P9 高级CPU设计

1.特殊指令

早期CPU是没有除法指令的，除法用减法来实现，例如16÷4，相当于16-4-4-4-4，这要花费很多个时钟周期。现代CPU设计中，从硬件层面上加了除法的指令，这样只要一个时钟周期就能搞定。此外，现代处理器有一些专门的电路来处理图像操作，解码压缩视频，加密等复杂运算，这些用标准操作要很多时钟周期，但一旦在硬件层面搞定，速度便大大提升。

2.Cache缓存

CPU的设计越来越巧妙和强大，以至于RAM读写的速度跟不上，RAM读写的这段时间，CPU白白空等完全就是浪费。于是人们在CPU和RAM之间加了个中间层——Cache缓存，CPU 从 RAM 拿数据时，不用一个个拿，而是一批批拿，即将用到的指令直接存在Cache缓存里，这样大大提高了读写效率。但这样带来了Cache和RAM数据不一致的问题，于是Cache会专门设计一个脏位，Cache存满后会检查脏位，把内容写回RAM后再清空缓存。

3.指令流水线

CPU有一种提升性能的方式，并行处理。我们知道，CPU一次完整的操作包含取指 → 解码 → 执行。我们可以在执行一条指令的时候，先解码下一条待执行的指令，以及做取下下条指令的操作。这种方式叫 指令流水线。但这种方式会带来两个问题：

第一，依赖性的问题，比如你在读某个数据，而正在执行的指令会修改这个数据，因此，我们要弄清楚指令之间的依赖关系，必要时暂停指令流水线，避免出错。现代CPU会动态排序有依赖关系的指令，在学习Java volatile时，你可能听说过"重排序"的问题，就来源于CPU的指令依赖关系。第二，JUMP跳转问题。一般的CPU会再JUMP前等待观察，一旦JUMP的结果出来，便往正确的分支塞指令。更高级的CPU会猜测JUMP到哪个分支的概率更大，叫 分支预测，提前用流水线塞指令，如果猜对了直接按流水线执行，否则就要先清空流水线，再重新塞正确的指令了。现代CPU分支预测的正确率能达到90%，所以效率棒棒哒。

4.多核处理器

现代CPU往往有多个核心，可以同时处理多个指令流。多核可以同时共同参与运算，提升效率也是很明显的。当多核也不够时，为啥不考虑下多CPU呢？中国国家超算中心的超威·太湖之光超级计算机就有 40960 个 CPU，每个 CPU 有 256 个核心，是世界上最快的计算机。

P10 早期的编程方式

程序需要加载进内存。可能你已经知道，早期的编程都是通过纸带打孔的方式，这种方式其实最早来源于纺织业。后来在19世纪美国人口普查中穿孔纸卡被用于记录汇总数据。但这只是数据，还不是程序。为了达到可编程的目的，程序员需要某种控制面板用于输入数据，最早被发明的控制面板是“插线板”，世界上第一台计算机ENIAC就用到了大量的插线板，其缺点是连线复杂，换程序十分不方便。还有一种是用大量的开关代替插线，叫做面板编程（panel programming）。

1940-1950年代，内存开始出现，使用了内存的计算机称为“存储程序计算机”，如果内存足够，不仅仅可以存程序，还可以存需要的数据，包括程序运行时产生的新数据。程序和数据存储在同一个地方，这种结构称为 冯诺依曼结构。冯诺依曼计算机的标志是：算术逻辑单元 + 数据寄存器 + 指令寄存器 + 指令地址寄存器 + 内存。

早期的编程方式都是专家活，我们亟需一种简单的方式告诉计算机我们要做什么，于是，编程语言诞生了！请看下篇。