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

Author Avatar
Jimmy Zhang Aug 19, 2017
  • Read this article on other devices

前言

开学要考试啊 orz……

学校推荐预习《计算机与计算思维导论》,然而作死的我却购入了《大学计算机——计算思维导论》(因为更便宜)。作此文以梳理本蒟蒻觉得重要的地方,以试图减小开学考试对咸鱼造成的恐惧。

逻辑运算

基本逻辑运算

我们先从三种最常见的逻辑运算开始:

"与"运算 AND:逻辑乘法

AABBABA \land B
000
010
100
111

"或"运算 OR:逻辑加法

AABBABA \lor B
000
011
101
111

"非"运算 NOT:逻辑否定

AA¬A\lnot A
01
10

复合逻辑运算

由以上介绍的三种基本逻辑运算,我们可以组合出常见的复合逻辑运算。

"与非"运算 NAND

先与后非

X NAND Y = NOT (X AND Y) == (NOT X) AND (NOT Y)

AABB¬(AB)\lnot (A \land B)
001
011
101
110

"或非"运算 NOR

先或后非

X NOR Y = NOT (X OR Y) == (NOT X) OR (NOT Y)

AABB¬(AB)\lnot (A \lor B)
001
010
100
110

"异或"运算 XOR

相同为假,相异为真。

X XOR Y = ((NOT X) AND Y) OR (X AND (NOT Y))

AABBABA \oplus B
000
011
101
110

"同或"运算 XNOR

相同为真,相异为假。

X XNOR Y = ((NOT X) AND (NOT Y) OR (X AND Y)

AABBABA \odot B
001
010
100
111

二进制与算术运算

数值表示

有大小关系的数通常采用进位制表达,即用数码和带权值的数位来表示。

进制的基本概念就不啰嗦了吧…… r进制就是逢r进1。就只记下常见进制的英文以备后用吧:

  • 二进制 Binary
  • 八进制 Octal
  • 十进制 Decimal
  • 十六进制 Hexadecimal

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

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

哦对了,唯一的重点就是十进制小数转二进制,小数部位使用乘 2 取整法,按顺序写出,看到循环了取最小循环数就行了……

符号表示

我们来梳理几个基本概念:

原码: 如果机器字长为 nn,那么一个数的原码就是用一个 nn 位的二进制数。其中最高位为符号位(正为 00,负为 11)剩下的 n1n - 1 位表示该数的绝对值。

反码: 对于非负整数,反码与原码一样;对于负整数,在原码的基础上,符号位不变,其他位按位取反。

补码: 对于非负整数,补码与原码一样;对于负整数,补码即反码 +1+ 1

移码: 取补码并对其符号位取反。

例如,对于 88 位二进制:

1-1 的原码为 1000 00011000 \ 0001,反码为 1111 11101111 \ 1110 ,补码为 1111 11111111 \ 1111 ,移码为 0111 11110111 \ 1111

机器数,也就是一个在计算机中的二进制表示形式,可以用原码、反码和补码表示。若只使用原码表示,则 00 有两种表示方式,即 +0+00-0 ,表示范围为(2n1)+(2n1)-(2^n - 1) \sim +(2^n - 1)。但若牵扯进补码的话 00 就只有一种表示了,范围也就变成了2n+(2n1)-2^n \sim +(2^n - 1)。如欲了解 C 语言中存储数字的具体方式,不妨参考上篇博文 乱谈整型与浮点

数值运算

加法实现原理

我们不妨把加法运算分为两个部分:按位加过程 和 进位过程

首先,我们来研究一下一位二进制的加法运算问题:

ABSUMCARRY
0000
0110
1010
1101

很容易发现,SUM(和)一栏即为前面介绍到的"异或"运算,而CARRY(进位)则为前面介绍到的"与"运算

因此我们不难总结出下列公式:

注:AiA_iBiB_i分别为第 ii 位加数和被加数,CiC_i 为第 i1i - 1 位运算产生的进位,SiS_i 为第 ii 位运算的和,Ci+1C_{i+1} 为产生的进位。

不考虑进位

{Si=AiBiCi+1=AiBi\begin{cases}
S_i = A_i \oplus B_i \
C_{i + 1} = A_i \land B_i
\end{cases}

考虑进位

{Si=(AiBi)CiCi+1=((AiBi)Ci)(AiBi)\begin{cases}
S_i = (A_i \oplus B_i) \oplus C_i \
C_{i + 1} = ((A_i \oplus B_i) \land C_i) \lor (A_i \land B_i)
\end{cases}

减法实现原理

先对减数取负,再执行上述加法即可。

乘法实现原理

我们知道左移1位为乘以2,右移一位为除以2,因此计算机的乘法是由加法和位移组合实现的:
i=0ka2n\sum\limits_{i=0}^{k}a \cdot 2^n

除法实现原理

人类计算除法

当我们在计算51 / 3 = 17,抛开9 * 9乘法表。

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

计算机计算除法

计算机计算除法的过程与人类计算的过程很类似,只是选择范围变成了0或1。
还以51 / 3为例说明(51=110011251 = 110011_23=1123 = 11_2

  1. 从第一位开始为1,小于11,结果位置0;余数为1
  2. 从第二位开始,余数 1×2+1=111 \times 2 + 1=11,等于11,结果位置 1,余数为 0;
  3. 从第三、四位开始,余数 0×2+0=0<0110 \times 2 + 0 = 0 < 011,结果位置 0,余数为 0;
  4. 从第5位开始,余数 0×2+1=1<110 \times 2 + 1 = 1 < 11,结果位置 0,余数为 1;
  5. 从第6位开始,余数 1×2+1=11=111 \times 2 + 1 = 11 = 11,结果位置 1,余数为 0。

此时将结果位相连,恰好是10001(17)。

小数点表示

可以参考上篇博文 乱谈整型与浮点中的“浮点数”部分。

编码

概念: 以若干数位或符号的不同组合来表示非数值信息的方法,是人为将若干数码或符号的每种组合钦定一种唯一的含义。

特性

  • 唯一性:每种组合都有唯一确定含义。
  • 公共性:所有相关者均认同、遵守、使用该种编码。
  • 规律性:具有一定规律和一定编码规则,便于计算机和人使用它。

ASCII 码、Unicode 和 GB2312-1980 不在本文中介绍,详情咨询百科。

趣题赏析

10001000 篇大新闻,其中一篇是长者的,香港记者只要报道了长者的新闻生命就会在24h内被续掉,问至少要多少名香港记者才能在 24h24h 内鉴别出长者的新闻?

鬼才想得到计算思维……

【猪】:这还不简单,10001000 名就够啦。

【人】:猪就是蠢,999999 名不就行啦。

【犇】:其实 1010 名就够了。这其实是一个二进制转十进制问题。我们以 00 代表记者存活,11 代表记者被续。给记者编号 090 \sim 9;给新闻编号 09990 \sim 999

  1. 99 号记者报道新闻 512999512 \sim 999292^9);
  2. 88 号记者报道新闻 25651,768999256 \sim 51, 768 \sim 999282^8);
  3. 77 号记者报道新闻 128255,384511,640767,896999128 \sim 255, 384 \sim 511, 640 \sim 767, 896 \sim 999272^7);
  4. 66 号记者报道新闻 64127,192255,320383,,93699964 \sim 127, 192 \sim 255, 320 \sim 383, \dots, 936 \sim 999262^6);
    ……
    依此类推,直到最后让 00 号记者报道所有的奇数新闻(202^0)。

24h24h 后,将 090 \sim 9 号记者的生存情况排列成一个二进制数,将其转换为 1010 进制,即为长者新闻编号。

例如,假设 817817 号新闻是长者的,那么根据上述步骤得到的二进制数即为:

11001100012=817101100110001_2 = 817_{10}

还没懂?

那我们这样想,二进制数转十进制数的过程是不是对二进制数的每一位(第 nn 位)乘以 2n2^n 并求和。若 00 v号记者最终被续,那么长者新闻的编号自然含有 1×291 \times 2^9,同理,若8号记者被续则必然含有 1×281 \times 2^8…… 现在明白了吧。

为什么这样想?

10001000 篇新闻,有一篇是能送命的,无非意味着一共仅有 10001000 种状态。我们只要找出一种方法能够表示这种状态就可以了——比如 1010 位二进制就是一个不错的选择。

参考文献

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2017/08/19/basics-on-computational-thinking/