计算导论: 计算系统基本思维

前言

开学要考试啊 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 入门?)。

参考文献