计算导论: 计算系统基本思维
前言
开学要考试啊 orz……
学校推荐预习《计算机与计算思维导论》，然而作死的我却购入了《大学计算机——计算思维导论》（因为更便宜）。作此文以梳理本蒟蒻觉得重要的地方，以试图减小开学考试对咸鱼造成的恐惧。
逻辑运算
基本逻辑运算
我们先从三种最常见的逻辑运算开始：
“与”运算 AND：逻辑乘法
| \(A\) | \(B\) | \(A + B\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
“或”运算 OR：逻辑加法
| \(A\) | \(B\) | \(AB\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
“非”运算 NOT：逻辑否定
| \(A\) | \(\overline{A}\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
复合逻辑运算
由以上介绍的三种基本逻辑运算，我们可以组合出常见的复合逻辑运算。
“与非”运算 NAND
即先与后非。
\[ X \text{ NAND } Y = \overline{AB} \]
| \(A\) | \(B\) | \(\overline{A \cdot B}\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
“或非”运算 NOR
即先或后非。
\[ A \text{ NOR } B = \overline{A + B} \]
| \(A\) | \(B\) | \(\overline{A + B}\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
“异或”运算 XOR
相同为假，相异为真。
\[ A \oplus B = \bar{A}B + A\bar{B} \]
| \(A\) | \(B\) | \(A \oplus B\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
“同或”运算 XNOR
相同为真，相异为假。
\[ A \odot B = \bar{A}\bar{B} + AB \]
| \(A\) | \(B\) | \(A \odot B\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
二进制与算术运算
数值表示
有大小关系的数通常采用进位制表达，即用数码和带权值的数位来表示。
进制的基本概念就不啰嗦了吧…… r进制就是逢r进1。就只记下常见进制的英文以备后用吧：
- 二进制 Binary
- 八进制 Octal
- 十进制 Decimal
- 十六进制 Hexadecimal
在计算机中我们通常采用二进制，其主要优点有：
- 二进制运算规则简单；
- 二进制算术运算可与逻辑运算实现统一，即可以用逻辑运算实现算术运算；
- 能表示两种状态的元器件容易找到，如继电器开关、灯泡、二极管/三极管等。
哦对了，唯一的重点就是十进制小数转二进制，小数部位使用乘 \(2\) 取整法，按顺序写出，看到循环了取最小循环数就行了……
符号表示
我们来梳理几个基本概念：
- 原码： 如果机器字长为 \(n\)，那么一个数的原码就是用一个 \(n\) 位的二进制数。其中最高位为符号位（正为 \(0\)，负为 \(1\)）剩下的 \(n - 1\) 位表示该数的绝对值。
- 反码： 对于非负整数，反码与原码一样；对于负整数，在原码的基础上，符号位不变，其他位按位取反。
- 补码： 对于非负整数，补码与原码一样；对于负整数，补码即反码 \(+ 1\)。
- 移码： 取补码并对其符号位取反。
例如，对于 \(8\) 位二进制：
\(-1\) 的原码为 \(1000 \ 0001\)，反码为 \(1111 \ 1110\) ，补码为 \(1111 \ 1111\) ，移码为 \(0111 \ 1111\)。
机器数，也就是一个在计算机中的二进制表示形式，可以用原码、反码和补码表示。若只使用原码表示，则 \(0\) 有两种表示方式，即 \(+0\) 和 \(-0\) ，表示范围为\(-(2^n - 1) \sim +(2^n - 1)\)。但若牵扯进补码的话 \(0\) 就只有一种表示了，范围也就变成了\(-2^n \sim +(2^n - 1)\)。如欲了解 C 语言中存储数字的具体方式，不妨参考上篇博文 乱谈整型与浮点。
数值运算
加法实现原理
我们不妨把加法运算分为两个部分：按位加过程 和 进位过程。
首先，我们来研究一下一位二进制的加法运算问题：
| A | B | SUM | CARRY |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
很容易发现，SUM（和） 一栏即为前面介绍到的 “异或”运算，而 CARRY（进位） 则为前面介绍到的“与”运算。
我们记 \(A_i, \ B_i\) 分别为第 \(i\) 位加数和被加数，\(C_i\) 为第 \(i - 1\) 位运算产生的进位，\(S_i\) 为第 \(i\) 位运算的和，\(C_{i + 1}\) 为产生的进位，这样就可以总结出下列公式：
不考虑进位
\[ \begin{cases} S_i = A_i \oplus B_i \\ C_{i + 1} = A_i B_i \end{cases} \]
考虑进位
\[ \begin{cases} S_i = A_i \oplus B_i \oplus C_i \\ C_{i + 1} = (A_i \oplus B_i) C_i + A_i B_i \end{cases} \]
减法实现原理
先对减数取负，再执行上述加法即可。
乘法实现原理
我们知道左移1位为乘以2，右移一位为除以 \(2\)，因此计算机的乘法是由加法和位移组合实现的：
\[ \sum\limits_{i=0}^{k}a \cdot 2^n \]
除法实现原理
人类计算除法
当我们在计算 \(51 / 3 = 17\) ，抛开乘法表。
- 从被除数的最高位 \(5\) 开始，从 \(0 \sim 9\) 选一个数，使得 \(5 - i \times 3 \ge 0\) 且使 \(5 - (i + 1) \times 3 < 0\)。我们选择了1，余数为2；
- 将余数\(2 \times 10 + 1 = 21\)，继续从 0 ~ 9 中选一个数，使得\(21 - 3 \times i \ge 0\)且使\(5 - (i + 1) \times 3 < 0\)。我们选择了 \(7\)；
- 由此，我们找到了答案 \(17\)。
计算机计算除法
计算机计算除法的过程与人类计算的过程很类似，只是选择范围变成了0或1。 还以 \(51 / 3\) 为例说明（\(51 = 110011_2\)；\(3 = 11_2\)）
- 从第一位开始为 \(1\)，小于 \(11\)，结果位置 \(0\)；余数为 \(1\)
- 从第二位开始，余数 \(1 \times 2 + 1 = 11\)，等于 \(11\)，结果位置 \(1\)，余数为 \(0\)；
- 从第三、四位开始，余数 \(0 \times 2 + 0 = 0 < 011\)，结果位置 \(0\)，余数为 \(0\)；
- 从第 \(5\) 位开始，余数 \(0 \times 2 + 1 = 1 < 11\)，结果位置 \(0\)，余数为 \(1\)；
- 从第 \(6\) 位开始，余数 \(1 \times 2 + 1 = 11 = 11\)，结果位置 \(1\)，余数为 \(0\)。
此时将结果位相连，恰好是 \(10001\)（\(17\)）。
小数点表示
可以参考上篇博文 乱谈整型与浮点中的“浮点数”部分。
编码
概念： 以若干数位或符号的不同组合来表示非数值信息的方法，是人为将若干数码或符号的每种组合钦定一种唯一的含义。
特性：
- 唯一性：每种组合都有唯一确定含义。
- 公共性：所有相关者均认同、遵守、使用该种编码。
- 规律性：具有一定规律和一定编码规则，便于计算机和人使用它。
ASCII 码、Unicode 和 GB2312-1980 不在本文中介绍，详情咨询百科。
趣题赏析
有 \(1000\) 篇大新闻，其中一篇是长者的，香港记者只要报道了长者的新闻生命就会在 \(24h\) 内被续掉，问至少要多少名香港记者才能在 \(24h\) 内鉴别出长者的新闻？
鬼才想得到计算思维……
🐷：这还不简单，\(1000\) 名就够啦。
😏：猪就是蠢，\(999\) 名不就行啦。
🤓：其实 \(10\) 名就够了。这其实是一个二进制转十进制问题。我们以 \(0\) 代表记者存活，\(1\) 代表记者被续。给记者编号 \(0 \sim 9\)；给新闻编号 \(0 \sim 999\)。
- 让 \(9\) 号记者报道新闻 \(512 \sim 999\)（\(2^9\)）；
- 让 \(8\) 号记者报道新闻 \(256 \sim 51, 768 \sim 999\)（\(2^8\)）；
- 让 \(7\) 号记者报道新闻 \(128 \sim 255, 384 \sim 511, 640 \sim 767, 896 \sim 999\)（\(2^7\)）；
- 让 \(6\) 号记者报道新闻 \(64 \sim 127, 192 \sim 255, 320 \sim 383, \dots, 936 \sim 999\)（\(2^6\)）； …… 依此类推，直到最后让 \(0\) 号记者报道所有的奇数新闻（\(2^0\)）。
\(24h\) 后，将 \(0 \sim 9\) 号记者的生存情况排列成一个二进制数，将其转换为 \(10\) 进制，即为长者新闻编号。
例如，假设 \(817\) 号新闻是长者的，那么根据上述步骤得到的二进制数即为：
\[ 1100110001_2 = 817_{10} \]
还没懂？
那我们这样想，二进制数转十进制数的过程是不是对二进制数的每一位（第 \(n\) 位）乘以 \(2^n\) 并求和。若 \(0\) v号记者最终被续，那么长者新闻的编号自然含有 \(1 \times 2^9\)，同理，若8号记者被续则必然含有 \(1 \times 2^8\)…… 现在明白了吧。
为什么这样想？
\(1000\) 篇新闻，有一篇是能送命的，无非意味着一共仅有 \(1000\) 种状态。我们只要找出一种方法能够表示这种状态就可以了——比如 \(10\) 位二进制就是一个不错的选择（状压 DP 入门？）。
参考文献
- 战德臣、聂兰顺等 - 《大学计算机——计算思维导论》
- 战德臣老师在中国大学MOOC上的在线课程
- 点奇 - 数字逻辑电路 逻辑运算 与、或、非、与非、或非、与或非、异或、同或
- 刘水镜 - 原码、反码、补码和移码其实很简单
- 匿名用户 - 计算机怎么计算，具体工作原理是什么？
- 小橋流水 - 一道关于计算机如何做加法的面试题
- 中华胡杨的专栏 - 计算机计算乘除法的原理