前言

开学要考试啊 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

在计算机中我们通常采用二进制，其主要优点有：

1. 二进制运算规则简单；
2. 二进制算术运算可与逻辑运算实现统一，即可以用逻辑运算实现算术运算；
3. 能表示两种状态的元器件容易找到，如继电器开关、灯泡、二极管/三极管等。

哦对了，唯一的重点就是十进制小数转二进制，小数部位使用乘 $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$ ，抛开乘法表。

1. 从被除数的最高位 $5$ 开始，从 $0 \sim 9$ 选一个数，使得 $5 - i \times 3 \ge 0$ 且使 $5 - (i + 1) \times 3 < 0$ 。我们选择了1，余数为2；
2. 将余数$2 \times 10 + 1 = 21$ ，继续从 0 ~ 9 中选一个数，使得$21 - 3 \times i \ge 0$ 且使$5 - (i + 1) \times 3 < 0$ 。我们选择了 $7$ ；
3. 由此，我们找到了答案 $17$ 。

计算机计算除法

计算机计算除法的过程与人类计算的过程很类似，只是选择范围变成了0或1。还以 $51 / 3$ 为例说明（$51 = 110011_2$ ；$3 = 11_2$ ）

1. 从第一位开始为 $1$ ，小于 $11$ ，结果位置 $0$ ；余数为 $1$
2. 从第二位开始，余数 $1 \times 2 + 1 = 11$ ，等于 $11$ ，结果位置 $1$ ，余数为 $0$ ；
3. 从第三、四位开始，余数 $0 \times 2 + 0 = 0 < 011$ ，结果位置 $0$ ，余数为 $0$ ；
4. 从第 $5$ 位开始，余数 $0 \times 2 + 1 = 1 < 11$ ，结果位置 $0$ ，余数为 $1$ ；
5. 从第 $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$ 。

1. 让 $9$ 号记者报道新闻 $512 \sim 999$ （$2^9$ ）；
2. 让 $8$ 号记者报道新闻 $256 \sim 51, 768 \sim 999$ （$2^8$ ）；
3. 让 $7$ 号记者报道新闻 $128 \sim 255, 384 \sim 511, 640 \sim 767, 896 \sim 999$ （$2^7$ ）；
4. 让 $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上的在线课程
• 点奇 - 数字逻辑电路 逻辑运算 与、或、非、与非、或非、与或非、异或、同或
• 刘水镜 - 原码、反码、补码和移码其实很简单
• 匿名用户 - 计算机怎么计算，具体工作原理是什么？
• 小橋流水 - 一道关于计算机如何做加法的面试题
• 中华胡杨的专栏 - 计算机计算乘除法的原理