计算导论: 计算系统基本思维
前言
开学要考试啊 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上的在线课程
- 点奇 - 数字逻辑电路 逻辑运算 与、或、非、与非、或非、与或非、异或、同或
- 刘水镜 - 原码、反码、补码和移码其实很简单
- 匿名用户 - 计算机怎么计算,具体工作原理是什么?
- 小橋流水 - 一道关于计算机如何做加法的面试题
- 中华胡杨的专栏 - 计算机计算乘除法的原理