欢迎大家来到IT世界,在知识的湖畔探索吧!

从最根本上讲，计算机并不是真正懂数学，也不了解计算的含义。即使一台计算机计算1 + 1得到2，它实际上也不是在处理数字，而是根据特定规则来操纵电流。

为了让这些规则产生对我们有用的东西，我们需要将计算机内部的电信号与人类喜欢使用的数字和符号相关联。

4.2.1　整数

这是一个令人震惊（触电）的想法！

将电信号与数字关联的明显方法，是在电压（或电流）和数字之间指定直接的对应关系。例如，我们可以让0V对应于数字0，让1V对应于1，10V对应10，依此类推。曾经有一段时间，这是在所谓的模拟计算机中完成的。但是这种方法存在一些问题，不仅仅是需要一台百万伏特的计算机！

这是谁的好主意？让人眼前一亮。

下面是另一种方法。设想我们使用灯泡来表示数字。如果灯泡熄灭，则数字为0；如果灯泡点亮，则数字为1。这很好，但是它只能表示两个数字。

好吧，让我们升级到三光灯泡。三光灯泡实际上具有4个开关位置：关闭和3个增加的亮度级别。在内部，三光灯泡有两根灯丝（见图4.1），一根暗，一根亮。例如，一根灯丝可能是50W，另一根灯丝可能是100W。通过一个也不选择、选择一个、选择另一个、选择两个，我们可以得到0W、50W、100W、150W的灯丝。我们可以用那个灯泡代表数字0、50、100和150，也可以决定4个级别分别代表数字0、1、2和3。

图4.1　三光灯泡

在内部，计算机使用相同的思路表示整数。不是像上面的照明示例那样使用50、100和150，而是使用2的幂组合的数字。设想我们有一个灯泡，灯泡上有

W、

W和

W的灯丝。然后，我们不打开任何灯丝就可以得到数字0，仅打开

W的灯丝就可以得到数字1，通过打开

W的灯丝可以得到2，以此类推，直到打开全部3根灯丝，得到

。

现在设想我们拥有以下4个连续的2的幂：

、

、

和

。请花一点时间，利用若干这些2的幂，写出数字0、1、2等，直到最大可能值。暂停阅读，我们会等你尝试完成这个任务。

如果一切顺利，你会发现可以利用0个或多个这些2的幂，得到0～15的所有整数。例如，13可以表示为

。

这个世界上有10种人：懂二进制的人和不懂二进制的人。

写成另一种方式就是：

请注意，我们在左边写了较大的2的幂，在右边写了较小的2的幂。我们很快就会看到，这一惯例很有用。上式中的0和1（即2的幂的“系数”）指出是否使用了2的特定幂。这些0和1系数称为“比特”（bit），代表二进制数字。二进制表示使用两个值——这里，两个值是0和1。

使用比特序列来表示数字而无须明确表示2的幂，这很方便。例如，我们会使用比特序列1101来表示数字13，因为这是比特在上述等式中出现的顺序。同样，0011代表数字3。我们通常忽略前导（即最左边）0，所以我们可以将它写成11。

我们在这里使用的表示形式称为“基数为2”，因为它基于2的幂。当然！你也可以使用基数为10的数字。在基数为10的数字中，数字由10的幂构成，并且我们不仅仅使用0和1作为系数，而是使用0～9。例如，序列603实际上意味着：

在《星球大战》中，赫特人有8个手指，因此也以8为基数。

其他基数也有用。例如，北加利福尼亚州的美国原住民部落由基人（Yuki）使用8为基数。在以8为基数时，我们使用8的幂，并且使用的系数是0～7。因此，例如，以8为基数的序列207表示：

这是135（以10为基数）。人们相信，由基人使用8为基数，是因为它们使用了手指之间的8个“槽”进行计数。

请注意，如果我们选择某个基数b（其中b是大于或等于2的某个整数），用作系数的数字是0～b−1。为什么？不难从数学上证明，当我们使用这种约定时，可以用d个数字表示0～

-1的正整数。此外，这个范围内的每个整数都有唯一的表示形式，这很方便，因为它避免了相同数字具有多个表示形式的麻烦。例如，就像42在基数10中没有其他表示形式一样，在基数2中的数字1101（我们刚刚看到，在基数10中是13）也没有其他表示形式。

许多较旧的或较小的计算机使用32比特来表示以2为基数的数字。我们机智地称它们为“32比特计算机”。因此，我们可以唯一地表示0～

-1（即4，294，967，295）的所有正整数。功能强大的现代计算机使用64比特表示每个数字，可以表示最大

的整数，大约是18万亿。

4.2.2　算术

以2为基数、以8为基数或以42为基数的算术类似于以10为基数的算术。例如，让我们考虑加法。基数为10时，我们就是从最右边的列开始，我们将这里的这些数字相加，并在需要时“进位”到下一列。例如，当进行以下计算时：

我们会开心地做加法！

5 + 7 = 12，所以我们在最右边的列中记下2，并进位1。那个1代表10，因此传播（即“进位”）到下一列代表10的位置。

我们将尽量不对这些例子激动不已，但你应该尝试计算一些以2为基数的数字相加，以确保你理解了它。

以2为基数的加法几乎相同。让我们来计算111（你应该记得，以10为基数是7）加上110（以10为基数是6）。我们从最右边（或“最低有效”）列开始，将1加到0，得到1。现在，我们移至下一列，即

位，即表示2的位置。两个数字中的每一个在此位置都为1。1 + 1 = 2，但我们在基数为2时仅使用0和1，因此在基数为2时，我们会得到1 + 1 = 10。这类似于在基数为10时计算7 + 3：我们写下0而不是写下10，并将1进位到下一列。同样，在基数为2时，对于1 + 1，我们写下0，并将1进位到下一列。

你知道为什么这样可行吗？在2的位置有2，相当于在4的位置有1。一般来说，在对应于

的列上有一个2，相当于在对应于

的下一列中有一个1，因为

。

要点：在你喜欢的基数中，加、减、乘和除都类似于基数为10时的那些运算！

4.2.3　负数思维

我们已经成功地以2为基数来表示数字，并对它们进行了算术运算。但是我们所有的数字都是正数。表示为负数怎么样？分数呢？

让我们从负数开始。一种相当明显的方法，是保留1比特来指示数字是正数还是负数。例如，在32比特计算机中，我们可能将最左边的比特用于此目的。将该比特设置为0可能意味着剩余的31比特表示的数字为正，而如果最左边的比特为1，则剩余的数字将被视为负。这称为“符号-大小”表示。我们付出的代价是我们损失了一半的范围（因为在我们的示例中，由于现在只有31比特来表示数字的大小）。虽然我们并不想在这里说得太消极，但更大的问题在于，构建计算机电路来操纵符号幅度数字是很棘手的。作为替代，我们使用所谓的“二进制补码”系统。

二进制补码背后的思想是这样的：如果将数字的表示形式加上其负数的表示形式总和为0，这将非常方便。例如，由于3加上−3为0，所以如果3的二进制表示形式加上−3的二进制表示形式总和为0，就很好了。我们已经知道3的二进制表示形式是11。假设我们有一台8比特计算机（而不是32比特或64比特），只是为了让这个例子比较容易。然后，包括前导0，3将表示为00000011。现在我们如何表示−3，使得将它与00000011相加后表示为0，即00000000？

请注意，如果我们“翻转”3的表示形式中的所有比特，就得到11111100。另外，00000011 + 11111100 =11111111。如果对此再加1比特，则得到11111111 + 00000001，当我们用进位进行加法时，我们得到100000000，即1后跟8个0。如果计算机仅使用8个比特来表示每个数字，则不会记录最左边的（第9个）比特！在这种情况下，保存的只是低位8比特000000000，即0。因此，要表示−3，我们可以简单地取3的表示形式，翻转这些比特，然后对它加1。请尝试一下，确保你理解它的工作原理。

总之，在二进制补码系统中表示负数需要先翻转正数的比特，然后再加1。

4.2.4　分数：拼接在一起

如何表示分数？一种方法（通常在视频和音乐播放器中使用）是建立一种约定，即以某种方便的分数为单位来度量一切（就像我们的三光灯泡以50W为单位工作）。例如，我们可能决定所有内容都以0.01为单位，因此数字100111010并不代表314，而是代表3.14。

这种方法的问题在于，科学计算通常需要比该策略提供的精度更高和数字范围更大的数字。例如，化学家经常使用的数值约为

或更高（阿伏伽德罗常量约为

），而核物理学家使用的数值可能小至

，甚至更小。

可以按以下方式解决此问题：假设我们以10为基数进行操作，并且只有8位数字代表我们的数字。我们可能会使用前6位数字来表示一个数，并约定在第一个数字之前有一个隐式的0和一个小数点。例如，6个数字123456将代表数字0.123456。然后可以用最后两位数字来表示10的幂的指数，因此12345678将代表

。计算机利用类似的思想来表示小数，只是用基数2代替了基数10。

4.2.5　字母和字符串

如你所知，计算机不仅仅可以操作数字，还可以处理符号、单词和文档。现在我们有了将数字表示为多个比特的方法，可以使用这些数字表示其他符号。

用数字表示字母相当容易。我们只需要对编码达成协议，即“约定”。例如，我们可能决定1代表“A”，2代表“B”，依此类推。或者我们可以用42代表“A”，用97代表“B”。只要我们完全在自己的计算机系统中工作，就没有关系。

尽管我发现，与自己达成协议通常比较容易。

但是，如果我们想将文档发送给朋友，那么与更多的人而不只是与我们自己达成协议，就会有所帮助。很久以前，美国国家标准协会（American National Standards Institute，ANSI）发布了这样的协议，称为ASCII（读作“ask-ee”，代表美国信息交换标准码）。它定义了大写和小写字母、数字和一组选定的特殊字符的编码，所有这些恰好是印在标准美式键盘上的符号，这并非巧合。

你可以在网上查找ASCII编码标准。另外，你可以用Python函数ord查找任何符号的数字表示形式。例如：

>>> ord('*') 
42
>>>  ord('9') 
57

欢迎大家来到IT世界,在知识的湖畔探索吧!

在ASCII中，数字42表示星号（*）。

为什么’9’的序数值报告为57？请记住，带引号的’9’只是一个字符，像星号、字母或标点符号一样。在ASCII约定中，它显示为字符57。顺便说一下，与ord相对的是chr。键入chr(42)将返回星号’*’，而chr(57)将返回字符’9’。

ord代表“ordinal”（序数）。你可以将它看作是在询问该符号的“序号”

ASCII中的每个字符都可以用8比特表示，通常称为一个字节（Byte）。不幸的是，只有8比特的ASCII只能表示256个不同的符号。（你可能会发现，在这里暂停一下并编写一个简短的程序很有趣，该程序是以0～255计数的，并且针对这些数字中的每一个，输出与该数字相对应的ASCII符号。你会发现，某些符号输出很奇怪，甚至是不可见的。（在网上查找一下，了解更多原因。）

似乎256个符号已经很多了，但是它没有提供法语等语言中使用的带重音符号的字符，更不用说西里尔字母、梵语字母或成千上万的中文和日语符号了。

有时将4比特称为“nybble（半字节）”；对于这种可怜的、书呆子式的双关语，我们不承担任何责任。

为了解决这一疏忽，国际标准化组织（International Organization for Standardization，ISO——读作“eye-so”，而不是念单个字母）最终设计了一个名为“Unicode”的系统，它可以表示每种已知语言中的每个字符，并为未来的增长留有空间。因为Unicode对于英语文档有点浪费空间，所以ISO还定义了几种节省空间的Unicode转换格式（Unicode Transformation Format, UTF），其中最流行的是UTF-8。你可能已经在计算机上使用了UTF-8，但是我们在这里不做详细介绍。

甚至还有非官方的克林贡语Unicode符号！

当然，单个字母本身并不是很有趣。人们通常喜欢将字母串在一起，并且我们已经看到，Python使用一种名为“字符串”的数据类型来实现这一点。用数字序列很容易做到这一点。例如，在ASCII中，序列99、104、111、99、111、108、97、116、101解释为“chocolate”。唯一缺少的细节是，当给定一长串数字时，你必须知道何时停止。常见的约定是在序列的最开始处包含“长度字段”。这个数字告诉我们字符串中有多少个字符。（Python使用了长度字段，但对我们隐藏了它，以防止字符串显得混乱。）

4.2.6　结构化信息

使用相同的概念，我们几乎可以将任何信息表示为数字序列。例如，图片可以表示为排列成行的一系列彩色点。每个彩色点（也称为“图像元素”，即像素）可以表示为3个数字，给出该像素处的红色、绿色和蓝色分量。同样，声音是空气中声压级的时间序列。影片是更复杂的单个图片的时间序列，通常为每秒24帧或30帧，并伴随匹配的声音序列。

那会有一点点烦人！

这又是抽象层的概念！比特组成数字，数字组成像素，像素组成图片，图片组成影片。一部两小时的影片可能需要数十亿比特，但是制作或观看影片的人都不想考虑所有这些比特！

关键术语

abstraction：抽象

AND, OR and NOT gates：AND、OR和NOT门

ASCII

assembly language：汇编语言

base：基数

binary：二进制

bit：位

byte：字节

circuit：电路

coefficients：系数

command line：命令行

compiler：编译器

conditional jump instruction：条件跳转指令

CPU

full adder：全加器

halt：停止

instruction register：指令寄存器

interpreter：解释器

latch：锁存器

length field：长度字段

logic gates：逻辑门

machine language：机器语言

merge sort：归并排序

minterm：最小项

minterm expansion principle：最小项扩展原理

modular design：模块化设计

no-operation instruction：无操作指令

opcode：操作码

operation code：操作码

padding：填充

parameter passing：参数传递

pixel：像素

pop：弹出

program counter (PC)：程序计数器

push：压入

RAM (Random Access Memory)：随机存取存储器

registers：寄存器

ripple-carry adder：波纹进位加法器

sign-magnitude representation：符号-大小表示

stack：栈

stack discipline：栈规则

stack pointer：栈指针

truth table：真值表

two’s complement：二进制补码

unconditional　jump instruction：无条件跳转指令

Unicode

UTF-8

variable jump target：可变跳转目标

von Neumann architecture：冯·诺依曼架构

word：字

本文摘自《计算机科学概论》（Python版）。

本书的其余部分遵循了同样的思路。我们使用Python语言，因为它的语法简单，并且有一套丰富的工具和软件包，让新手程序员能够编写有用的程序。在第2章中，我们对使用Python进行编程的介绍仅限于该语言语法的有限子集，这体现了函数式编程语言的精神。通过这种方式，读者很早就掌握了递归，并意识到他们可以用极少的代码编写有趣的程序。

第3章在函数式编程上更进一步，介绍了高阶函数的概念。第4章关注一个问题：“我的计算机如何做到这一切？”我们研究了计算机的内部工作原理，从数字逻辑到计算机组织，再到用机器语言编程。

既然已经揭开了计算机的“神秘面纱”，读者也看到了“幕后”发生的事情的物理表示，于是我们在第5章中继续探讨了计算中更复杂的思想，同时探讨了诸如引用和可变性等概念，以及包括循环在内的构造、数组和字典。我们利用第4章介绍的计算机物理模型来解释这些概念和结构。根据我们的经验，如果读者建立了底层的物理模型，就更容易理解这些概念。所有这些都是在读者熟悉的场景下完成的，这就是一个推荐程序，就像在线购物中使用的那种。

内容新！有改进！有许多“边缘的”有用注释！

在第6章中，我们探讨了面向对象编程和设计中的一些关键思想。这里的目标不是培养专业级的程序员，而是解释面向对象范式的基本原理，并让读者了解一些关键概念。最后，在第7章中，我们研究了问题的“难度”——在计算复杂性和可计算性方面，提供了一些优雅的，但数学上非常合理的处理方法，最终证明了计算机上无法解决的许多计算问题。我们使用Python作为模型，而不是使用形式化的计算模型（如图灵机）。

本书意在与我们为课程开发的大量资源一起使用，这些资源可从网站https://www.cs. hmc.edu/csforall上获得。这些资源包括完整的授课PPT、丰富的每周作业集、一些附带的软件和文档，以及关于该课程已发表的论文。

我们有意让这本书的篇幅相对较短，并努力让它变得有趣、可读性好。本书准确地反映了课程的内容，而不是一本不可能在一个学期学完的、令人望而生畏的百科全书。我们编写这本书时相信，读者可以随着课程的进行而舒适地阅读所有内容。