书名：计算机科学概论（第13版）
ISBN：978-7-115-58263-8
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美] J. 格伦•布鲁克希尔（J. Glenn Brookshear）
[美] 丹尼斯•布里罗（Dennis Brylow）
译 刘 艺 吴 英 毛倩倩
责任编辑 杨海玲
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e58263”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
本书是计算机科学概论课程的经典教材，全书对计算机科学做了百科全书式的精彩阐述，充分展现了计算机科学的历史背景、发展历程和新的技术趋势。书中首先介绍信息编码及计算机体系结构的基本原理，进而介绍操作系统和组网以及因特网的相关内容，接着探讨算法、程序设计语言及软件工程，然后讨论数据抽象和数据库方面的问题，讲述图形学的主要应用以及人工智能，最后以计算理论的介绍结束全书。本书在内容编排上由具体到抽象逐步推进，便于教学安排，每一个主题自然而然地引导出下一个主题。此外，书中还包含大量的图、表和示例，有助于读者对知识的了解与把握。第13版对前一版进行了全面的修正和更新，还新增了Python相关的内容，并且继续使用第12版引入的Python代码示例和类Python伪代码。
本书非常适合作为高等院校计算机以及相关专业本科生教材，也适合有意在计算机方面发展的非计算机专业读者作为入门参考书。
Authorized translation from the English language edition, entitled COMPUTER SCIENCE: AN OVERVIEW, 13th Edition by BROOKSHEAR, GLENN; BRYLOW, DENNIS, published by Pearson Education, Inc, Copyright © 2019 by Pearson Education, Inc.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc.
CHINESE SIMPLIFIED language edition published by POSTS AND TELECOM PRESS CO., LTD., Copyright © 2022.
本书中文简体字版由Pearson Education Inc.授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。
本书封面贴有Pearson Education（培生教育出版集团）激光防伪标签，无标签者不得销售。
版权所有，侵权必究。
本书是计算机科学的入门教材。在力求保持学科广度的同时，还兼顾深度，以对所涉及的主题给出中肯的评价。
本书面向计算机科学以及其他各个学科的学生。大多数计算机科学专业的学生在最初的学习中都有一个误解，认为计算机科学就是程序设计、网页浏览以及因特网文件共享，因为这基本上就是他们所看到的一切。实际上计算机科学远非如此。在入门阶段，学生们需要了解他们主修的这门学科所涉及的广泛内容，这也正是本书的宗旨。本书力图使学生对计算机科学有一个总体的了解，希望在这个基础上，他们可以领会该领域与日后其他课程的关联性以及相互关系。事实上，本书采用的综述方式也是自然科学入门教程的常用模式。
其他学科的学生如果想融入这个技术化的社会，也需要具备这些宽泛的知识背景。适用于他们的计算机科学课程提供的应该是对整个领域的实用的、现实的理解和剖析，而不仅是培训学生如何上网和使用一些流行的软件。当然，这种培训也有其适用的地方，但本书的目的不在于此，而是用作计算机科学的教科书。
在编写本书前几版时，我们力求保持其对非技术类学生的可读性。因此，本书已经成功地用作教科书，读者囊括了从高中生到研究生的各个教育层级不同专业的学生。这一版会继续保持这一传统。
第13版继续使用第12版引入的Python代码示例和类Python的伪代码。我们做出这种改变有几个原因。首先，本书已经包含了相当多的各种语言的代码，有几章还有详细的伪代码。其次，读者已经吸收了相当多的句法方面的知识，似乎可以将句法重新定位为在后续课程中会实际看到的语言。最后，更重要的是，越来越多的使用本书的教师断定，即使优先介绍计算的广度，对学生来讲，如果缺乏用于探索和实验的编程工具，许多课题也会很难掌握。
那为什么选择Python呢？语言的选择始终是一个有争议的问题，任何一种选择，反对的人都至少和支持的人一样多。Python是一个极好的中间选择，因为Python：
● 句法简洁易学；
● I/O原语简单；
● 数据类型和控制结构与先前版本中使用的伪代码原语很接近；
● 支持多个程序设计范式。
Python是一种成熟的程序设计语言，它拥有充满活力的开发社区和丰富的在线资源，便于进一步的研究。根据某些衡量标准，Python仍然是业界前5种最常用的程序设计语言之一，并且在计算机科学入门课程中的使用急剧增加。对非计算机专业的学生来讲，它是一门极其受欢迎的入门课程，并且已被其他像物理学和生物学这样的STEM[1]领域广泛接受，作为计算科学应用的首选语言。
[1] STEM是4个英语单词Science（科学）、Technology（技术）、Engineering（工程）和Mathematics（数学）的缩写。 ——译者注
然而，本书的重点仍然是广义的计算机科学概念；补充Python语言的内容是为了让读者能体会到比先前版本更浓的编程味儿，而不是为了全面地介绍编程。所涵盖的Python主题是由本书现有的结构决定的。因此，第1章涉及Python句法，用于表示数据——整数、浮点数、ASCII字符串或Unicode字符串等。第2章涉及Python运算，详细讨论反映了本章其余部分所讨论的机器原语。条件、循环和函数是在第5章引入的，那里需要使用这些结构来设计一个足够完整的描述算法的伪代码。简而言之，Python结构是用来进一步阐明计算机科学概念而不是劫持话题的。
每一章都能看到对前一版对应章节的修订、更新以及修正。
本书主题由具体到抽象逐步推进——这是一种很利于教学的顺序，每一个主题自然而然地引导出下一个主题。首先介绍信息编码、数据存储及计算机体系结构的基本原理（第1章和第2章），进而研究操作系统（第3章）和计算机网络（第4章），探讨算法、程序设计语言及软件开发（第5章至第7章），探索如何更好地访问信息（第8章和第9章），考虑计算机图形学技术的一些重要应用（第10章）及人工智能（第11章），最后介绍抽象的计算理论（第12章）。
虽然本书的编排顺序自然连贯，但各个章节都具有很强的独立性，可以单独阅读，也可以根据不同学习顺序重新排列。事实上，本书通常被用作各类课程的教材，内容选择的顺序是多种多样的。其中一种教法是先介绍第5章和第6章（算法和程序设计语言），然后根据需要返回到前面的相应章节。我还知道有一门课程是从第12章有关可计算性的内容开始的。本书还曾作为深入不同领域项目的基础，用于“高级研讨班”课程的教科书。面对不需要了解太多技术的学生，在教学中可以重点讲述第4章（组网及因特网）、第9章（数据库系统）、第10章（计算机图形学）和第11章（人工智能）。
每章开篇都用星号标出了选学章节。这些选学章节要么是讨论更专业的话题，要么是对传统话题作深入探究。此举仅是为那些想采取不同阅读顺序的读者提供一点建议。当然，还有其他读法。尤其对于那些寻求快速阅读的读者，我们建议采取下面的阅读顺序。
| 章 节 |
主 题 |
|---|---|
| 1.1～1.4 |
数据编码和存储基础 |
| 2.1～2.3 |
机器体系结构和机器语言 |
| 3.1～3.3 |
操作系统 |
| 4.1～4.3 |
组网及因特网 |
| 5.1～5.4 |
算法和算法设计 |
| 6.1～6.4 |
程序设计语言 |
| 7.1～7.2 |
软件工程 |
| 8.1～8.3 |
数据抽象 |
| 9.1～9.2 |
数据库系统 |
| 10.1～10.2 |
计算机图形学 |
| 11.1～11.3 12.1～12.2 |
人工智能 计算理论 |
在本书中有几条贯穿始终的主线。主线之一为计算机科学是不断发展变化的。本书从历史的角度反复呈现各个主题，讨论其当前的状况，并指出研究方向。另一条主线是抽象的作用以及用抽象工具控制复杂性的方式。该主线在第0章引入，然后在操作系统架构、组网、算法的发展、程序设计语言设计、软件工程、数据组织和计算机图形学等内容中反复体现。
本教材所包含的内容很难在一个学期内讲授完，因此一定要果断砍掉不适合自己教学目标的那些主题，或者根据需要重新调整讲授顺序。你会发现，尽管本书有它固有的结构体系，但各个主题在很大程度上是相对独立的，完全可以根据需要做出选择。我写本书的目的是把它作为一种课程的资源，而非课程的定义。我们建议鼓励学生自己阅读课堂上没有讲授的内容。如果我们认为所有的东西都一定要在课堂上讲，那就低估学生的能力了。我们应该教会他们独立学习。
关于本书从具体到抽象的组织结构，我们觉得有必要多言几句。作为学者，我们总以为学生会欣赏我们对于学科的观点，这些观点通常是我们在某一领域的多年工作中形成的。但作为教师，我们认为最好从学生的视角呈现教材内容。这就是为什么本书首先介绍数据的表示/存储、计算机体系结构、操作系统以及组网，因为这些都是学生们最容易产生共鸣的主题：他们很可能听说过JPEG、MP3这些术语，可能用DVD和闪存盘刻录过数据，应用过某一操作系统，日常使用过因特网和智能手机。从这些主题开始讲授这门课程，学生可以为许多让他们困惑多年的问题找到答案，并且把这门课看成实践课程而不是纯理论的课程。由此，就会很自然地过渡到较抽象的算法、算法结构、程序设计语言、软件开发方法、可计算性以及复杂性等内容上，而这些内容就是我们本领域的人认为的计算机科学的主要内容。正如前面所说的，以这种方式呈现全书并不是强求大家都按此顺序讲课，只是鼓励大家如此尝试一下。
我们都知道，学生能学到的东西要远远多于我们直接传授的内容，而且潜移默化传授的知识更容易被吸收。当要“传授”问题的解决方法时，就更是如此。学生不可能通过学习问题求解的方法变成问题的解决者，他们只有通过解决问题，而且不仅仅是解决那些精心设计过的“教科书式的问题”，才能成为问题的解决者。因此，本书加入了大量的问题，并特意让其中一些问题模棱两可——这意味着正确方法或正确答案不一定是唯一的。我们鼓励大家采用并拓展这些问题。
“潜移默化学习”类的其他话题还有职业精神、道德和社会责任感。我认为这种内容不应该独立成章，而是应该在有所涉及时讨论，而这正是本书的编排方法。你会发现，3.5节、4.5节、7.9节、9.7节和11.7节分别在操作系统、组网、软件工程、数据库系统和人工智能的上下文中提及了安全、隐私、责任和社会意识的问题。你还会发现，每一章都包含了一些社会问题，这些问题将鼓励学生思考他们所生活的现实社会与教材中的内容的关系。
感谢你对本书感兴趣。无论你是否选用本书作为教材，我都希望你认同它是一部好的计算机科学教育文献。
本书是多年教学经验的结晶，因此在辅助教学方面考虑较多。最主要的是提供了丰富的问题以加强学生的参与——这一版包含1 000多个问题，分为“问题与练习”“复习题”和“社会问题”。
“问题与练习”列在每节末尾（第0章除外），用于复习刚刚讨论过的内容，扩充以前讨论过的知识，或者提示以后会涉及的有关主题。
“复习题”列在每章的末尾（第0章除外）。它们是课后作业，内容覆盖整章，书中没有给出答案。
“社会问题”也列在每章的末尾，供思考讨论。许多问题可以用来开展课外研究，可要求学生提交简短的书面或口头报告。
在每章的末尾还有“课外阅读”，其中列出了与本章主题有关的参考资料。
本书的许多补充材料可以从Pearson Higher Education官方网站上找到。以下内容面向所有读者。
● 每章的实践项目帮助读者加深理解本教材的主题，并可以帮助读者了解其他相关主题。
● 每章的“自测题”帮助读者复习本书中的内容。
● 介绍Python基本原理的手册，它在教学顺序上与本书是兼容的。
除此之外，教师还可以登录Pearson Education的教师资源中心或者填写本书后的“教师支持申请表”，申请获得以下教辅资料。
● 包含“复习题”答案的教师指南。
● PowerPoint幻灯片讲稿。
● 测试题库。
Glenn Brookshear有一点点偏执（他的一些朋友说可远不是一点点），所以写本书时，他很少接受他人的建议，许多人认为其中一些内容对于初学者过于高深。但是，我们相信即使学术界把它们归为“高级论题”，但只要与主题相关就是合适的。读者需要的是一本全面介绍计算机科学的教科书，而不是“缩水”的版本——只包括那些简化了的、被认为适合初学者的主题。因此，我们不回避任何主题，而是力求寻找更好的解释。我们力图在一定深度上向读者展示计算机科学最真实的一面。就好比对待菜谱里的那些调味品一样，你可以有选择地略过本书的一些主题，但我们全部呈现出来是为了在你想要的时候供你“品尝”，而且我们也鼓励你们去尝试。
我们还要指出的是，在任何与技术有关的课程中，当前学到的详细知识未必就适合以后的需要。这个领域是发展变化的——这正是使人兴奋的方面。本书将从现实及历史的角度展现本学科的内容。有了这些背景知识，你就会和技术一起成长。我们希望你现在就行动起来，不要局限于课本的内容，而要进行大胆探索。要学会学习。
感谢你的信任，选择了我们的这本书。作为作者，我们有责任创作出值得一读的作品。我们希望你觉得我们已经尽到了这份责任。
首先，我要感谢Glenn Brookshear，他一直照看着这本书——“他的孩子”——包括之前的11个版本，跨越了计算机科学领域快速发展和动荡变化的超过四分之一个世纪的时间。虽然这是他允许合著者来审核所有修订的第二个版本，但这一版收录的仍然基本是Glenn的“声音”，并由他主导，这也是我所希望的。任何新的瑕疵都是我造成的，而优雅的基本框架都是他设计的。
我和Glenn要感谢那些支持本书（阅读并使用本书前几个版本）的人们，我们感到很荣幸。一部计算机科学教科书的13个版本？我们一定是在接近某种记录。
在我们努力确定第13版和CS原理框架之间重叠部分的时候，Andrew Kuemmel（Madison West）一直是我们极重要的参谋。他是我认识的唯一一个成功在高中和大学教授许多CSP课程实例的人，他对我家乡威斯康星州的计算机科学教育工作者的不倦支持一直很鼓舞人心。在David T. Smith（宾夕法尼亚州印第安纳大学）和我共同编写第11版修订内容的过程中，David发挥了很重要的作用。他做的许多修订在第13版中仍然存在。David对之前版本的仔细阅读和对补充材料的仔细关注对本书来讲至关重要。Andrew Kuemmel（Madison West）、George Corliss （Marquette）和Chris Mayfield（James Madison）为这一版和之前版本的初稿提供了有价值的反馈、深刻的见解和鼓励，同时James E. Ames（Virginia Commonwealth）、Stephanie E. August（Loyola）、Yoonsuck Choe（Texas A&M）、Melanie Feinberg（UT-Austin）、Eric D. Hanley（Drake）、Sudharsan R. Iyengar（Winona State）、Ravi Mukkamala（Old Dominion）和Edward Pryor（Wake Forest）都对第12版Python方面的修订提供了宝贵的评价。
其他对这一版和之前版本做出贡献的人包括J. M. Adams、C. M. Allen、D. C. S. Allison、E. Angel、R. Ashmore、B. Auernheimer、P. Bankston、M. Barnard、P. Bender、K. Bowyer、P. W. Brashear、C. M. Brown、H. M. Brown、B. Calloni、J. Carpinelli、M. Clancy、R. T. Close、D. H. Cooley、L. D. Cornell、M. J. Crowley、F. Deek、M. Dickerson、M. J. Duncan、S. Ezekiel、C. Fox、S. Fox、N. E. Gibbs、J. D. Harris、D. Hascom、L. Heath、P. B. Henderson、L. Hunt、M. Hutchenreuther、L. A. Jehn、K. K. Kolberg、K. Korb、G. Krenz、J. Kurose、J. Liu、T. J. Long、C. May、J. J. McConnell、W. McCown、S. J. Merrill、K. Messersmith、J. C. Moyer、M. Murphy、J. P. Myers, Jr.、D. S. Noonan、G. Nutt、W. W. Oblitey、S. Olariu、G. Riccardi、G. Rice、N. Rickert、C. Riedesel、J. B. Rogers、G. Saito、W. Savitch、R. Schlafly、J. C. Schlimmer、S. Sells、Z. Shen、G. Sheppard、J. C. Simms、M. C. Slattery、J. Slimick、J. A. Slomka、J. Solderitsch、R. Steigerwald、L. Steinberg、C. A. Struble、C. L. Struble、W. J. Taffe、J. Talburt、P. Tonellato、P. Tromovitch、P. H. Winston、E. D. Winter、E. Wright、M. Ziegler，还有一位匿名的朋友。我们向他们中的每一位致以最诚挚的谢意。
Diane Christie为一个之前版本的配套网站设计了Java和C++手册，我们最新的Python资源就是从那里来的。谢谢你，Diane。另外，还要感谢Roger Eastman，他是伴随本书之前版本的每章实践项目幕后的创造动力。
我同时要感谢支持本书出版工作的Pearson出版集团的员工。特别是Tracy Johnson、Erin Ault、Carole Snyder和Scott Disanno，他们在整个过程中为本书贡献了他们的智慧并提出了许多改进建议。
最后，我要感谢我的妻子Petra，在我编写本版时，她照顾三个孩子，给我留出了很多个很长的下午和晚上。她是我的后盾。
D. W. B.
马凯特大学
2018年1月1日
AP®是美国大学理事会注册和拥有的商标，它没有参与本产品的生产，也不为本产品背书。
本书各章和各节对应了AP®计算机科学原理课程框架（简称AP®CSP课程框架）中的“持久理解”（Enduring Understanding，EU）和“学习成果”（Learning Outcome，LO）部分，具体对应关系如下所示。
| 1.1 创造性开发可能是创建计算工件的必要过程 |
||
| 1.1.1 |
在创建计算工件时应用创造性开发过程 |
5.3 |
| 1.2 计算使人们能够使用创造性开发过程来创建用于创造性表达式的计算工件或解决问题 |
||
| 1.2.1 |
为创造性表达式创建计算工件 |
1.0 |
| 1.2.3 |
通过组合或修改现有工件来创建新的计算工件 |
10.6 |
| 1.3 计算可以扩展传统的人类表达和体验的形式 |
||
| 1.3.1 |
对创造性表达式使用计算工具和技术 |
10.1 |
| 2.1 根据二进制序列构建的各种抽象可用于表示所有数字数据 |
||
| 2.1.1 |
描述用于表示数据的各种抽象种类 |
1.1, 1.4, 2.1 |
| 2.1.2 |
解释如何用二进制序列来表示数字数据 |
1.6, 1.7, 2.1, 2.2 |
| 2.2 多层次的抽象用于编写程序或创建其他计算工件 |
||
| 2.2.1 |
在编写程序或创建其他计算工件时开发抽象 |
6.3 |
| 2.2.2 |
使用多层次的抽象来编写程序 |
6.2 |
| 2.2.3 |
确定编写程序时使用的多层次的抽象 |
1.1, 2.6, 6.1, 6.4 |
| 2.3 模型和模拟使用抽象来产生新的理解和知识 |
||
| 2.3.1 |
使用模型和模拟来表示现象 |
10.3, 10.4, 10.6 |
| 2.3.2 |
使用模型和模拟来制订、改进和测试假设 |
10.4 |
| 3.1 人们使用计算机程序来处理信息从而获得深入理解和知识 |
||
| 3.1.1 |
找到数字化处理信息的模式和测试假设来获得深入理解和知识 |
9.1, 9.6 |
| 3.2 计算有助于探索和发现信息中的连接 |
||
| 3.2.1 |
从数据中提取信息来发现和解释连接或趋势 |
9.1, 11.4 |
| 3.2.2 |
确定大数据集是如何影响使用计算过程发现信息和知识的 |
9.0, 9.1, 9.4 |
| 3.3 在将信息表示为数字数据时要有所权衡 |
||
| 3.3.1 |
分析数据的表示、存储、安全和数据传输是如何涉及信息的计算操纵的 |
1.3, 1.9, 4.4, 4.5, 9.7 |
| 4.1 算法是可由计算机执行的过程的精确指令序列，是使用程序设计语言实现的 |
||
| 4.1.1 |
开发用于程序实现的算法 |
5.1, 5.2, 5.4, 6.3 |
| 4.1.2 |
用语言表达算法 |
5.2, 6.1 |
| 4.2 算法可以解决许多但不是所有的计算问题 |
||
| 4.2.1 |
解释能在合理时间内运行的算法与不能在合理时间内运行的算法之间的区别 |
12.5 |
| 4.2.2 |
解释计算机科学中可解问题与不可解问题之间的区别 |
11.3, 12.5 |
| 4.2.3 |
解释计算机科学中存在的不可决定问题 |
12.1, 12.4 |
| 4.2.4 |
分析评估和凭经验评估算法的效率、正确性和清晰度 |
5.6, 12.5 |
| 5.1 可以开发程序来进行创造性的表达、满足个人好奇心、创造新知识或解决问题（帮助人员、组织或社会） |
||
| 5.1.1 |
开发程序来进行创造性的表达、满足个人好奇心或创造新知识 |
10 |
| 5.1.2 |
开发正确的程序来解决问题 |
6.2, 7.2, 7.3, 7.4, 7.7 |
| 5.1.3 |
协作开发程序 |
5.1, 7.1, 7.6 |
| 5.2 人们编写程序来执行算法 |
||
| 5.2.1 |
解释程序是如何实现算法的 |
2.6, 6.2 |
| 5.3 适当的抽象使编程更容易 |
||
| 5.3.1 |
使用抽象管理程序复杂性 |
1.8, 2.6, 6.3, 6.5, 8.1, 8.5 |
| 5.4 人们出于不同的目的开发、维护和使用程序 |
||
| 5.4.1 |
评估程序的正确性 |
1.8, 7.5 |
| 5.5 程序设计使用数学和逻辑概念 |
||
| 5.5.1 |
在程序设计中使用适当的数学和逻辑概念 |
1.1, 1.6, 1.7, 1.8, 8.1 |
| 6.1 因特网是一个自治系统的网络 |
||
| 6.1.1 |
解释因特网中的抽象以及因特网是如何运作的 |
4.1, 4.2, 4.4 |
| 6.2 因特网的特点影响着建立在它上面的系统 |
||
| 6.2.1 |
解释因特网的特点和建立在它上面的系统 |
4.2, 4.4 |
| 6.2.2 |
解释因特网的特点是如何影响建立在它上面的系统的 |
1.3, 4.1, 4.2, 4.4, 4.6 |
| 6.3 网络安全是因特网和建立在它上面的系统的重要关注点 |
||
| 6.3.1 |
确定现有的网络安全关注点，以及通过因特网和建立在它上面的系统解决这些问题的潜在选项 |
4.6 |
| 7.1 计算增强了沟通、互动和认知 |
||
| 7.1.1 |
解释计算革新是如何影响沟通、互动和认知的 |
4 |
| 7.2 计算几乎能在每个领域实现创新 |
||
| 7.2.1 |
解释计算是如何影响其他领域创新的 |
9.6, 10.6 |
| 7.3 计算对人和社会有全球性影响—既有有利的又有有害的 |
||
| 7.3.1 |
分析计算的有利影响和有害影响 |
4.6, 9.7, 11.7 |
| 7.4 计算革新既影响着设计和使用它们的经济、社会和文化环境，又受这些环境的影响 |
||
| 7.4.1 |
解释计算和现实生活环境（包括经济、社会和文化环境）之间的关联 |
4.2 |
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
本书提供各章中问题与练习的答案。 要获得这一配套资源，请在异步社区本书页面中单击 ，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
如果您是教师，希望获得教学配套资源要获得本书配套教师资源，请加入异步教师服务群（QQ群661759394）联系客服获取，或者直接发邮件给本书责任编辑获取（yanghailing@ptpress. com.cn）。
您还可以扫码右侧二维码， 关注【异步社区】微信公众号，回复“e58263”直接获取,同时可以获得异步社区15天VIP会员卡，近千本电子书免费畅读。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的积分。积分可用于在异步社区兑换优惠券、样书或奖品。
扫描下方二维码，您将会在异步社区微信服务号中看到本书信息及相关的服务提示。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频或者参与技术审校等工作，可以通过邮件与本书责任编辑联系。
如果您来自学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接通过邮件发给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
在开篇的这一章，我们将探讨计算机科学所涉及的领域，介绍其历史背景，为深入学习奠定基础。
本章内容
0.1 算法的作用
0.2 计算的历史
0.3 学习大纲
0.4 计算机科学的首要主题
算法研究是计算机科学的核心。
学习成果 解释计算机科学领域中算法的重要性。
计算机科学近代史的特点是计算能力、小型化和连通性的快速进步。
学习成果 确定那些为我们的现代技术社会铺平道路的计算机科学史上的重要里程碑。
计算机科学的进步正在深深地影响着人类文化和社会。
学习成果 讨论计算机科学进步造成的社会、道德或法律难题。
计算机科学是寻求为计算机设计、计算机程序设计、信息处理、问题的算法解决方案和算法过程本身等主题建立科学基础的学科。计算机科学既是当今计算机应用的支柱，又是今后计算基础设施的基础。
在本书中，我们将详细介绍计算机科学，探索广泛的主题，包括构成大学计算机科学课程的大部分主题。我们要领略这个领域的博大精深和动态发展。因此，除了这些主题本身，我们还会关注它们的历史发展、研究现状和未来前景。我们的目标是让人们以学以致用的态度理解计算机科学——既帮助那些想在此领域进行深入专业研究的人，又可以使其他领域的人在日益技术化的社会崭露头角。
首先让我们了解一下计算机科学最基础的概念——“算法”。一般来讲，算法（algorithm）是完成一项任务所遵循的一系列步骤。（在第5章，我们将给出比较精确的定义。）例如，有关于烹饪的算法（称为菜谱），有在陌生城市准确寻找道路的算法（通常称为道路指南），有使用洗衣机的算法（通常标示在洗衣机盖子的内侧或者贴在自助洗衣店的墙上），有演奏音乐的算法（以乐谱的形式表示），还有魔术表演的算法（见图0-1）。
图0-1 一个魔术的算法
在机器（如计算机）执行一项任务之前，必须先找到完成这项任务的算法，并用与该机器兼容的形式表示出来。算法的表示称作程序（program）。为了人们读写方便，计算机程序通常打印在纸上或者显示在计算机屏幕上。为了便于机器识别，程序需要以一种与该机器技术兼容的形式进行编码。开发程序、采取与机器兼容的形式进行编码并将其输入机器中的过程，称作程序设计/编程（programming），有时也称作编码（coding）。程序及其所表示的算法统称为软件（software），而机械本身称为硬件（hardware）。
算法的研究起源于数学学科。事实也的确如此，探寻算法是数学家的重要活动，远远早于当今计算机的出现。它的目标是找出一组指令，描述如何解决某一特定类型的所有问题。求解两个多位数商的长除算法是早期研究中一个最著名的例子。另一个例子是古希腊数学家欧几里得发现的欧几里得算法——求两个正整数的最大公约数（见图0-2）。
图0-2 求两个正整数的最大公约数的欧几里得算法
一旦我们找到执行任务的算法，执行该任务时就不再需要了解该算法所依据的原理——任务的执行简化成了遵照指令操作的过程。（我们可以在不了解算法原理的情况下，根据长除算法求商或者根据欧几里得算法求最大公约数。）在某种意义上，解决这个问题的智能被编码到了算法中。
通过算法来捕获和传达智能（至少是智能行为），我们能够构建出执行有用任务的机器。因此，机器展现出来的智能水平受限于算法所传达的智能。只有存在执行某一项任务的算法时，我们才可以制造出执行这一任务的机器。换言之，如果我们找不到解决某问题的算法，机器就解决不了这个问题。
20世纪30年代，库尔特·哥德尔（Kurt Gödel）发表了不完备性定理的论文，它使确定算法能力的局限性成为数学学科的一个研究课题。这个定理实质上阐述的是，在任何一个包括传统意义的算术系统的数学理论内，总有一些命题的真伪无法通过算法的手段来确定。简言之，对算术系统的任何全面研究都超越了算法活动的能力范围。这一认识动摇了数学的基础，于是关于算法能力的研究随之而来，它开创了今天的计算机科学这门学科。的确，正是算法的研究构成了计算机科学的核心。
今天的计算机有着庞大久远的世系渊源，其中较早的一个计算设备是算盘。历史告诉我们，它可能源于中国古代且曾被用于早期希腊和罗马文明。算盘本身非常简单，一个矩形框里固定着一组细杆，而每个细杆上又各串有一组珠子（见图0-3）。在细杆上，珠子上下移动的位置就表示其所存储的值。这些珠子的位置代表了这台“计算机”表示和存储的数据。这台机器是依靠人的操作来控制算法执行的。因此，算盘自身只算得上一个数据存储系统，它必须在人的配合下才能成为一台完整的计算机器。
图0-3 中国木制算盘（Ekkapon/Shutterstock）
从中世纪到近代，人们一直在探求更复杂的计算机器。一些发明家开始基于齿轮技术设计计算机器。采用这种技术的发明家有法国的布莱斯·帕斯卡（Blaise Pascal，1623—1662）、德国的戈特弗里德·威廉·莱布尼茨（Gottfried Wilhelm Leibniz，1646—1716）和英国的查尔斯·巴贝奇（Charles Babbage，1792—1871）。这些机器利用齿轮的位置来表示数据，要在规定齿轮初始位置的基础上机械地输入数据。帕斯卡和莱布尼茨的机器所计算的结果是通过观察齿轮的最终位置得到的。但巴贝奇构想的机器，则可以把计算的结果打印在纸上，从而消除可能出现的抄写错误。
就执行算法的能力而言，我们可以看到这些机器在灵活性上的进步。帕斯卡的机器只是为了执行加法而设计的，因此必须将正确的步骤序列嵌入机器结构本身。同样，莱布尼茨的机器也把算法嵌入了其机器结构中，但是操作员可以从它提供的各种算术操作中进行选择。巴贝奇设计的差分机（Difference Engine）（只造了一个演示模型）可以通过修改来执行各种计算，但他设计的分析机（Analytical Engine）（从未得到过构造资助）则能够在打孔纸卡片上读取以洞孔形式表示的指令。因此，巴贝奇的分析机是可编程的。事实上，奥古斯塔·艾达·拜伦（Augusta Ada Byron，通称Ada Lovelace）经常被认为是世界上第一位程序员，她曾发表过一篇论文，阐述巴贝奇的分析机是如何通过编程实现各种计算的。
巴贝奇的差分机
查尔斯·巴贝奇设计的这台机器的确是现代计算机设计的先驱。如果能用比较经济的方式制造出这台机器，如果当时商业和政府的数据处理需求达到今天的规模，那么巴贝奇的想法可能在19世纪就引发了计算机革命。然而结果却是，他在有生之年只造出了差分机的演示模型。该机器通过计算“逐次差分”来确定数字值。我们可以通过考虑整数平方的计算问题，深入了解这一技术。我们先从基础知识开始，0的平方是0，1的平方是1，2的平方是4，3的平方是9。据此，我们可以按照下面的方法得到４的平方（见下图）。现在，我们先计算一下已知的平方之间的差：12 - 02 = 1，22 - 12 = 3，32 - 22 = 5。然后，我们计算这些结果的差：3 - 1 = 2，5 - 3 = 2。注意，这些差都是2。假设这个规律能够成立（数学上可以证明它是成立的），那么我们可以得出这样的结论：（42 - 32）和（32 - 22）之间的差也一定是2。因为（42 - 32）一定比（32 - 22）大2，所以42 - 32 = 7，因而42 = 32+7 = 16。现在，我们已经知道了4的平方，那么就可以依据12、22、32和42的值继续计算5的平方。（虽然更深入地讨论逐次差分已经超出了现在的学习范围，但是学过微积分的学生可能已观察到，前面的例子是基于“y = x2的二阶导数是一条直线”这个事实得出的。）
奥古斯塔·艾达·拜伦
奥古斯塔·艾达·拜伦（洛夫莱斯伯爵夫人）是计算界关注的焦点人物。艾达·拜伦的一生近乎悲惨，去世时还不到37岁（1815—1852）。她体弱多病，身处限制妇女从业的社会，是个不墨守成规的人。尽管她对很多科学领域都感兴趣，但最感兴趣的还是数学。1833年，目睹了查尔斯·巴贝奇的差分机样机演示后，她就被这台机器迷住了，从此对“计算科学”产生了兴趣。她把一篇讨论巴贝奇分析机设计的论文从法文翻译为英文，这是她最早对计算机科学做出的贡献。巴贝奇还鼓励她在翻译中增加一个附录，介绍该机器的应用，以及该机器如何编程实现各种任务的示例。巴贝奇对艾达·拜伦的工作十分热情，他希望这篇论文的发表能够帮他得到资金支持，建造他的分析机。（作为拜伦勋爵的女儿，艾达·拜伦具有名人的地位，在生意场上也有一定的关系。）虽然巴贝奇的期望落空了，但是艾达·拜伦的附录保存了下来，人们认为该附录包含了第一批计算机程序的例子。关于巴贝奇对艾达的工作影响有多大，研究计算机历史的历史学家一直争论不休。有些历史学家认为，巴贝奇做出了重大贡献，但另外一些历史学家则认为，巴贝奇并没有帮到艾达，从很大程度上来看反而是一种阻碍。无论如何，奥古斯塔·艾达·拜伦都被认为是世界上第一位程序员，美国国防部为了纪念这位伟大的女性，用她的名字命名了一种杰出的程序设计语言（Ada）。
通过纸卡片上的洞孔来传达算法的想法最初并不是源于巴贝奇。他是从约瑟夫·雅卡尔（Joseph Jacquard，1752—1834）那里得到这个想法的。约瑟夫·雅卡尔于1801年研制出一种织布机，它在织布过程中执行的步骤，是由宽大厚实的木制（或纸板）卡片上的洞孔样式决定的。因此，织布机的算法很容易进行修改，可以得出不同的编织设计。另一个受益于雅卡尔想法的人是赫尔曼·霍尔瑞斯（Herman Hollerith，1860—1929），他灵活运用这一概念——用纸卡片上洞孔的样式来表示信息，加速了美国1890年人口普查中的表格处理。（霍尔瑞斯的这项改造促成了IBM的诞生。）这种卡片最终被称作穿孔卡片，直到20世纪70年代，它仍是与计算机交互的流行工具。
从成本效益上来讲，19世纪的技术无法让帕斯卡、莱布尼茨和巴贝奇设计的复杂齿轮驱动机器付诸生产。但是，随着20世纪初期电子技术的进步，这个障碍被克服了。这种进步的例子包括乔治·斯蒂比兹（George Stibitz）的电子机械机器和马克一号（Mark I），前者由贝尔实验室于1940年建造，后者由霍华德·艾肯（Howard Aiken）和一组IBM工程师于1944年在哈佛大学建造。这些机器使用了大量机械式继电器，通过电流进行控制。从这个意义上说，这些机器几乎是一造出来就过时了，因为其他研究人员已在应用真空管技术建造完全电子化的计算机。第一台真空管机器显然是阿塔纳索夫-贝瑞（Atanasoff-Berry）机器，由约翰·阿塔纳索夫（John Atanasoff）和他的助手克利福德·贝里（Clifford Berry），于1937—1941年在艾奥瓦州立学院（现在的艾奥瓦州立大学）建造。另一台是称为巨人（Colossus）的机器，在汤米·弗劳尔斯（Tommy Flowers）的指导下建造于英国，该机器在第二次世界大战后期曾被用来破解德国的情报。（实际上，这类机器至少造了十余台，但是由于涉及军事机密和国家安全问题而隐瞒它们的存在，未能列入“计算机家谱”。）不久，更为灵活的机器出现了，如ENIAC（Electronic Numerical Integrator And Computer，电子数字积分计算器），它是由约翰·莫奇利（John Mauchly）和普雷斯波·埃克特（J. Presper Eckert）在宾夕法尼亚大学莫尔电子工程学院研制的（见图0-4）。
从那时起，计算机器的历史就开始和技术进步紧密相连，包括晶体管的发明（物理学家威廉·肖克利、约翰·巴丁和沃尔特·布拉顿因此获得了诺贝尔奖）和后来集成电路的开发（杰克·基尔比因此荣获了诺贝尔物理学奖）。由于这些技术，以往20世纪40年代房间大小的机器在数十年间缩小到了单机柜大小。与此同时，计算机器的处理能力每两年便会翻倍（这一趋势一直持续到了今天）。随着集成电路技术的进步，计算机中的许多元件都可封装在玩具大小的塑料块中做成芯片，在电子市场上很容易就可以买到。
图0-4 3个女人在操作莫尔学院的ENIAC主控制板。
这台机器后来搬到了美国陆军弹道研究实验室
（图片来源于美国陆军）
计算机的普及在很大程度上得益于台式计算机的发展。台式计算机的出现是计算机爱好者的功劳，他们通过芯片组合构建了家用计算机。正是在这些计算机爱好者的“地下”活动中，史蒂夫·乔布斯（Steve Jobs）和斯蒂芬·沃兹尼亚克（Stephen Wozniak）制造出了有商业价值的家用计算机，并于1976年成立了苹果计算机公司（现称苹果公司），专门制造和销售他们的产品。其他经销类似产品的公司有Commodore、Heathkit和Radio Shack。虽然这些产品在计算机爱好者中很畅销，但是并没有被商界普遍接受，商界仍然青睐久负盛名的IBM公司及其大型计算机，这些计算机满足了大多数的商用计算需求。
1981年，IBM公司推出了它的第一款台式计算机，称为个人计算机（personal computer），简称PC，其基础软件由一个新成立的称为微软（Microsoft）的公司开发。PC一经推出立即获得了极大的成功，并且奠定了这种台式计算机在商界人士心目中作为日用品的地位。今天，术语PC已被广泛用于指称整个这一类机器（来自各个不同厂商），其设计都是从IBM公司最初的台式计算机演变而来的，而且它们中的大多数还在与微软公司的软件一起销售。不过，有时候，术语PC也能与通用术语台式机（desktop）或笔记本计算机（laptop）互换使用。
在20世纪后期，因特网（Internet）的出现大大改变了人们的沟通方式，这种技术将个人计算机连成了一个全球系统。在这个背景下，英国科学家蒂姆·伯纳斯·李（Tim Berners-Lee）提出了一个系统，这个系统可以通过因特网把计算机上存储的文档链接起来形成错综复杂的链接信息网，这便是万维网（World Wide Web），简称Web。为了能够访问Web信息，人们开发了一种叫作搜索引擎（search engine）的软件系统，用于筛选Web上的信息，并对筛选结果进行“归类”，然后利用这个结果帮助用户研究特定的主题。这一领域的主要参与者有谷歌、雅虎和微软。这些公司不断地扩展其与Web相关的活动，而且经常会挑战我们的传统思维方式。
与此同时，台式计算机和笔记本计算机正在被人们所接受，并用于家庭，计算机器的微型化仍在继续。今天，大量的电器和设备中都嵌有微型计算机。现在的汽车可能就包含了几十个小型计算机，用于运行全球定位系统（Global Positioning System，GPS），监控发动机的性能，并提供控制汽车音频和电话通信系统的语音命令服务。
也许，计算机微型化最革命性的应用就是智能手机（smartphone）能力的扩展。智能手机是手持通用计算机，通话应用仅是其众多应用之一。从功能上讲，这种钱包大小的设备比几十年前的超级计算机还要强大，它配备有大量的传感器和接口，包括照相机、麦克风、指南针、触摸屏、加速计（用以检测手机的方向和动作），以及一系列无线技术（以便与其他智能手机和计算机通信）。很多人认为智能手机对全球社会的影响大于PC革命。
本书遵循自底向上的计算机科学研究方法，先从读者有亲身体验的主题开始（如计算机硬件），继而引出比较抽象的主题（如算法复杂性和可计算性）。结果是，我们的学习遵循这样的模式：随着我们对主题理解的深入，我们构建的抽象工具会越来越大。
我们先学习与设计和构造执行算法的机器有关的主题。在第1章（数据存储）中，我们学习信息是如何编码和存储在现代计算机中的。在第2章（数据操控）中，我们研究简单计算机的内部基本操作。虽然部分学习内容涉及技术，但总体上是独立于具体技术的。也就是说，像数字电路设计、数据编码与压缩系统，以及计算机体系结构这样的主题，与很多技术都相关，并且不管未来技术的发展方向如何，它们的相关性都不会变。
在第3章（操作系统）中，我们学习控制一台计算机总体操作的软件，这种软件称为操作系统。操作系统控制机器与其外部世界之间的接口：保护机器及其内部存储数据不被非授权用户访问；允许计算机用户请求执行各种程序；协调内部活动，以满足用户请求。
在第4章（组网及因特网）中，我们将学习计算机是如何连接成计算机网络的，网络又是如何连接成互联网的。这些知识涉及很多主题，如网络协议、因特网结构与内部操作、万维网以及众多安全问题。
在第5章（算法）中，我们将比较正式地学习算法研究。我们将研究如何发现算法，确定几种基本的算法结构，开发几项用于表示算法的基本技术，并介绍算法效率和正确性的主题。
在第6章（程序设计语言）中，我们讨论的主题是算法表示和程序开发过程。在这一章中，我们会发现，人们在不断改善程序设计技术的过程中，创造出了各种各样的程序设计方法学或范型，每一种都有它自己的一套程序设计语言。我们除了研究这些范型和语言，还会考虑语法和语言翻译的问题。
第7章（软件工程）将介绍计算机科学的一个分支——软件工程。软件工程处理的是开发大型软件系统时遇到的问题。底层主题是，大型软件系统的设计是一项复杂的任务，会遇到传统工程未涉及的许多问题。因此，软件工程这一学科已经成为计算机科学中一个重要的研究领域，它借鉴了诸如工程、项目管理、人事管理、程序设计语言设计，甚至是建筑学等众多领域的研究经验。
在接下来的两章中，我们将学习在计算机系统中组织数据的方法。在第8章（数据抽象）中，我们介绍传统上用于在计算机的主存储器中组织数据的技术，然后探索数据抽象的演变发展，从原语的概念一直到如今的面向对象技术。在第9章（数据库系统）中，我们介绍传统上用于在计算机海量存储器中组织数据的方法，并研究如何实现极其庞大的复杂数据库系统。
在第10章（计算机图形学）中，我们将探索图形学和动画的主题，一个涉及创建并图像化虚拟世界的领域。在计算机科学传统领域（如机器体系结构、算法设计、数据结构和软件工程）发展的基础上，图形学和动画学科取得了重大进展，业已发展成为激动人心、充满活力的学科。此外，这个领域体现了计算机科学的各个组成部分是如何与物理、艺术和摄影等学科相结合产生显著成果的。
在第11章（人工智能）中，我们将了解到，为了开发更有用的机器，计算机科学已一马当先转向研究人类智能。研究人员希望通过对自己的思维推理和认知的了解，设计出模拟这些过程的算法，从而将类似的能力转移到机器上。结果，计算机科学就有了人工智能这个领域，它非常依赖于心理学、生物学和语言学等领域的研究。
我们的学习到第12章（计算理论）结束，这一章将研究计算机科学的理论基础，这个主题会让我们了解算法（和机器）的局限性。这里我们不但明确了几个算法上无法解决的问题（因而超出了机器的能力），而且认识到许多其他问题的解决方案需要大量的时间或空间，以至于从实践的角度来看它们也是不可解的。因此，通过本章的学习，我们将能够掌握算法系统的范围和局限性。
我们的目标是，每一章主题的探讨都足够深入，使读者真正理解。我们希望所阐述的计算机科学知识对大家的工作能有所帮助——使读者了解自己身处的技术化社会，打好跟随科技进步自我学习的基础。
除了上面列出的每章的主题，我们还希望结合以下几个首要主题来拓宽读者对计算机科学的理解。计算机的微型化及其功能的扩展，已经把计算机技术推向了当今社会的最前沿。如今，计算机技术已经非常普及，熟练掌握其应用已经成为现代社会成员的基本要求。计算技术已经改变了政府施加控制的能力，对全球化经济产生了巨大的影响，导致科学研究领域出现了一些令人瞩目的成就，革新了数据收集、存储和应用的作用，为人们提供了新的通信和交互方式，不停地挑战着社会现状。结果是，围绕计算机科学的学科大量涌现，每门学科现在都成了重要的独立研究领域。此外，就像很难区分机械工程和物理一样，我们也很难在这些领域与计算机科学之间画出一条分界线。因此，为了获得正确的视角，我们的研究不仅要涉及以计算机科学为核心的中心主题，还要探索与科学应用和影响相关的各个学科领域。因此，对计算机科学的介绍是一项跨学科的任务。
探索计算领域的广度，能帮助我们记住与计算机科学相结合的主要主题。虽然“计算机科学的七大思想”（Seven Big Ideas of Computer Science）的编纂晚于本书的第10版，但这些思想与本书接下来的各章所要讲述的主题思想有很多相似之处。这“七大思想”简单地说就是算法、抽象、创新、数据、程序设计、因特网和影响。在接下来的章节中，我们将介绍各种主题，在每个主题的介绍中都会涉及这个主题的核心思想、目前的研究领域，以及推动该领域知识进步的一些技术。当我们在后面一遍又一遍地提到这些“大思想”的时候，请多留意。
数据存储容量有限，程序设计过程复杂耗时，这些限制了早期计算机器所使用的算法的复杂性。但是，随着这些局限性的消除，机器能完成的任务越来越大、越来越复杂。人们试图用算法表达这些任务，但单凭人类的智力无法做到，于是，越来越多的研究工作转向了算法和程序设计过程的研究。
正是在这种背景下，数学家的理论研究开始有了回报。由于哥德尔不完备性定理，数学家已经在研究有关算法过程的问题了，而这正是先进技术目前面临的问题。由此，孕育出了被称作计算机科学的新学科。
如今，计算机科学已经奠定了它算法科学的地位。这门科学范围很广，涉及数学、工程学、心理学、生物学、商业管理和语言学等多个学科。事实上，研究计算机科学不同分支的研究人员对计算机科学的定义也许会截然不同。例如，计算机体系结构领域的研究人员，主要关注微型电路技术，因此他们将计算机科学视为技术的进步和应用，但数据库系统领域的研究人员则认为，计算机科学就是要寻求方法来提升信息系统的有用性，而人工智能领域的研究人员则把计算机科学视为智能和智能行为的研究。
尽管如此，所有这些研究人员的工作还是都涉及了算法科学的方方面面。鉴于算法在计算机科学中扮演的核心角色（见图0-5），找出焦点问题，对学习算法会非常有益。
● 算法过程可以解决哪些问题？
● 怎样才能比较容易地发现算法？
● 如何改进表示和传达算法的技术？
● 如何分析和比较不同算法的特征？
● 如何使用算法来操作信息？
● 如何应用算法来产生智能行为？
● 算法的应用是如何影响社会的？
图0-5 算法在计算机科学中的核心地位
术语抽象（abstraction）在本书中是指一个实体的外部特征与其内部构成细节之间的分离。抽象使我们可以忽略复杂设备（如计算机、汽车或微波炉）的一些内部细节，把它们当作一个单个的、可理解的单元使用。此外，正是通过抽象这种手段，这些复杂的系统才能够被设计和生产出来。计算机、汽车和微波炉都是由若干元件构成的，其中每个元件代表一层抽象，在此层面上，该元件的使用是独立于元件的内部构成细节的。
运用抽象，我们能够构造、分析和管理大型的复杂计算机系统，但如果从细节的层面上看问题，就会不识庐山真面目。在每个抽象层面上，我们都把此系统看成由若干称为抽象工具（abstract tool）的构件组成，而忽略这些构件的内部构成。这样我们的精力就可以集中在每个构件如何与同一层面其他构件发生作用，以及这些构件如何作为一个整体构成更高级别的构件。由此，我们就可以理解该系统中与手头任务有关的那部分，而不会迷失在细节的海洋里。
需要强调的是，抽象并不局限于科学和技术领域。它是一门重要的简化技术，我们的社会形成的任何一种生活方式都离不开抽象。很少有人知道，日常生活中各种各样的便利是如何实现的：我们需要吃饭穿衣，但我们自己无法生产；我们使用电气设备和通信系统，但不了解其底层技术；我们享受其他人提供的服务，但不知道其专业细节。对于每一项新的发展，只有一小部分社会成员专职于其实现，其他人则将实现的结果作为抽象工具来使用。这样，社会的抽象工具仓库扩大了，社会进一步发展的能力也增强了。
抽象这一话题在本书中会被反复提及。我们将了解到，计算设备是通过各个层次的抽象工具构建的。我们还会看到，大型软件系统的开发是以模块化的方式完成的，其中每个模块都是较大模块中的一种抽象工具。此外，在计算机科学本身的发展中，抽象也扮演了很重要的角色，有了它，研究人员可以把精力集中在一个复杂领域中的特定范围上。实际上，本书的编排也反映了计算机科学的这种特征：每一章都围绕着计算机科学的一个特定的方面，而且往往出人意料地独立于其他章，但所有这些章合在一起，又形成了这一巨大研究领域的全面概述。
虽然计算机可能只是复杂的机器，机械地执行着机械式算法指令，但是我们应该看到，计算机科学领域本质上是一个创新性的领域。发现并应用新算法是人类的一项活动，这项活动取决于我们天生的用工具解决我们周围世界中的问题的欲望。计算机科学不仅扩展了表示形式，使其跨越了视觉、语言和音乐艺术，而且还让新的数字表示模式遍及了现代世界。
创建大型软件系统不太像照菜谱做菜，更像是构思一个宏大的新雕塑。构思雕塑的形式和功能需要仔细的规划。制造它的元件需要时间，需要注意细节，还需要熟练的技能。最终的产品体现了设计美学及其创造者的情感。
计算机能表示任何可以被离散化或数字化的信息。算法可以用各种令人眼花缭乱的方式，处理或转换这种数字表示信息。因此，计算机算法不仅能将计算机的一部分数字数据与另一部分混洗，还能让我们搜索模式、创造模拟，通过关联连接产生新知识和新见解。海量存储容量、高速计算机网络以及强大的计算工具，推动着科学、工程和人文领域中许多其他学科的发现。无论是通过模拟复杂蛋白质折叠来预测一种新药的治疗效果，统计分析横跨数个世纪的数字化图书的语言的演化，还是渲染通过非入侵式医学扫描获得的内脏的3D图像，数据都在驱动着现代发现超越人类自身的能力。
在本书中，我们会探讨一些有关数据的问题，包括：
● 计算机是如何存储那些与常见的数字人工制品有关的数据（如数字、文本、图像、声音和视频）的？
● 计算机是如何粗略估计那些现实世界中模拟人工制品的数据的？
● 计算机是如何检测和避免数据中的错误的？
● 我们现在所掌控的这个由日益增长的、互连的数据构成的数字宇宙，最后会变成什么样子？
尽管现在涌现的可用语言和工具，与20世纪50年代及20世纪60年代早期的可编程计算机没什么相似之处，但是将人类的意图翻译成可执行的计算机算法的这种行为，现在被广泛称为程序设计/编程（programming）。虽然计算机科学的组成部分并不只有计算机程序设计，还包括许多其他方面，但是通过设计可执行算法（程序）解决问题的能力依然是所有计算机科学家的一项基本技能。
计算机硬件只能执行相对简单的算法步骤，但有了计算机程序设计语言提供的抽象，人类就能针对复杂得多的问题，进行推理并制定出编码解决方案。下面这几个关键的问题为我们这个主题的讨论提供了框架。
● 如何构建程序？
● 程序中会出现哪些类型的错误？
● 如何发现和修复程序中的错误？
● 现代程序中的错误会产生什么影响？
● 如何对程序进行文档化和评估？
因特网连接着全世界的计算机和电子设备，这对我们这个技术社会存储、检索和共享信息的方式产生了深远的影响。现在，商业、新闻、娱乐和通信都越来越依赖这个由较小的计算机网络组成的互联网络。我们的讨论不仅限于把因特网的机制描述为人工制品，还会涉及人类社会业已被全球网络交织在一起的许多方面。
因特网的覆盖对我们的隐私和个人信息的安全也有着深远的影响。网络空间里有很多危险，所以在我们这个互联的世界里，密码学和网络安全正变得越来越重要。
计算机科学不仅对我们用于通信、工作和娱乐的技术有深远的影响，对我们的社会生活也有巨大的影响。计算机科学的进步正在淡化许多差别，而这些差别正是我们过去做出某些决策的基准；计算机科学的进步也向许多长久以来的社会准则提出了挑战。在法律上，它产生了某些疑问——知识产权的度以及伴随这个所有权的权利和义务。在道德上，人们面临着许多挑战传统社会行为准则的抉择。对于政府，又产生了许多争议——计算机技术及其应用应该规范到什么程度？在哲学上，人们开始争论智能行为的存在与智能本身的存在。同时，整个社会也在争论新的计算机应用是代表的是新的自由还是新的控制。
对于那些想涉足计算或者计算机相关领域的人，这种话题是很重要的。科学中的新发现有时会使许多应用产生争议，这使人们对相关的研究人员产生极大不满。进一步而言，道德上的过错足以摧毁本可以很成功的事业。
计算机技术的发展给人们提出了许多难题，而具备解决这些难题的能力对于非计算机领域的人也十分重要。的确，计算机技术已经在全社会迅速普及，几乎无人不受其影响。
本书提供了一些技术背景，有助于人们以一种理智的思维来处理计算机科学所产生的问题。然而，计算机科学的技术知识本身无法提供全部问题的解决办法。因此，本书的一些章节致力于介绍计算机科学的社会、道德和法律影响，包括安全问题、软件所有权和义务问题、数据库技术的社会影响以及人工智能发展的后果。
此外，一个问题往往没有明确的正确答案，许多有效的解决方案都是在两个对立的（也许都是有理的）观点之间进行折中的。在这些情况下寻找解决方案通常需要能够倾听、辨别其他观点、开展理性的讨论，并在获得新见解时改变自己的观点。因此，本书的每一章最后都会在“社会问题”这样一节收集一些问题，研究一系列计算机科学和社会之间的关系。这些问题不一定是需要回答的，而是需要思考的。在许多情况下，当人们发现其他答案时，就不会再满意于那个最先出现的明显答案了。简而言之，给出这些问题的目的并不是让大家找到“正确”答案，而是要提高大家的意识：要意识到一个问题会牵扯多位利益相关者，一个问题会有多个解决方案，那些解决方案都同时具有长短期效应。
哲学家在基础理论的研究中提出了许多伦理学方法，从而产生了指导决策和行为的原则。
性格伦理（有时称为德行伦理）是由柏拉图和亚里士多德提出的，他们认为“好行为”不是应用可识别规则的结果，而是“良好性格”的自然结果。然而其他伦理基础（如结果伦理、职责伦理和合同伦理）认为，一个人在解决伦理难题时，应该考虑的是：“后果是什么？”“我的职责是什么？”或者“我有什么合同？”而性格伦理考虑的是：“我想成为什么样的人？”因此，好行为是建立在好性格基础上的，而这通常得益于良好的教育以及德行习惯。
在向不同领域的专业人士教授伦理知识时，一般以性格伦理为基础。不用教授专门的伦理理论，只要举一些能够暴露该专业领域中各种伦理问题的案例即可。然后，通过讨论这些案例的利弊，让这些专业人士对职业生活中潜在的危险有一个更清醒、更深入和更敏感的认识，并将这种认识融入他们的性格中。这就是每章最后设计社会问题的精神所在。
希望下面的问题能引导读者思考一些与计算领域相关的道德、社会和法律问题。回答出这些问题还不够，还应该考虑为什么这样回答，以及你的判断是否对每个问题都标准如一。
1．“如果没有计算机革命，我们现在的社会将有很大不同。”人们已经广泛接受这种观点。与没有计算机革命的社会相比，现在的社会是更好了还是更差了？如果你在社会中的地位不同，你的答案会有所不同吗？
2．想参与到当今的技术社会中，却又不想努力了解技术的基础知识，这种做法是否可行？例如，要通过表决来决定如何支持和使用某项技术，那么表决者是否有了解该项技术的义务？你的答案是否与正在考虑的具体技术有关？例如，在考虑使用核技术时和在考虑使用计算机技术时，你的答案一样吗？
3．传统上，人们使用现金进行交易，因而处理账务时不需要支付服务费用。然而，随着经济生活中自动化程度不断提高，金融机构正在对这些自动化系统的使用收取服务费。那么，“服务收费不公正地限制了人们参与经济活动”这种说法是否正确呢？例如，假设雇主仅用支票支付员工工资，并且所有金融机构都对支票兑现和存款收取服务费，那么员工会因此受到不公正的待遇吗？如果雇主坚持只通过直接存款的方式支付工资呢？
4．在交互式电视节目中，某一个公司有可能会从孩子那里获取有关其家庭的信息（也许是通过交互式游戏的形式），那应该控制到什么程度呢？例如，应该允许公司通过孩子得知其父母的购物习惯吗？关于孩子自己的信息呢？
5．政府对计算机技术及其应用应该管制到什么程度？例如，考虑第3题和第4题中提到的问题。什么能证明政府监管是正当的？
6．对于技术，尤其是计算机技术，我们做出的决策会对我们的后代产生多大的影响？
7．随着技术的进步，美国的教育系统不断面临挑战，要重新考虑在哪些抽象层次上安排哪些主题。许多问题是类似的，如某项技能是否必要，是否应该允许学生依赖某种抽象工具等。学三角时，不再教学生如何利用函数表求三角函数的值，而是允许学生用计算器作为抽象工具来求函数值。有些人认为，长除也应该让位于抽象。还有哪些主题涉及类似的争论？现代字处理程序是否会使人们不需要练习书法？视频技术的使用是否会在将来的某一天取代阅读？
8．随着越来越多的信息通过计算机技术存储和传播，是否每一位公民都应该有权使用这项技术呢？答案如果是肯定的，那么公共图书馆是否应该为这种权力提供渠道？
9．在一个依靠抽象工具的社会里，会产生什么样的伦理问题？是否存在这样的情况，当我们使用某个产品或某项服务时，不了解它的工作原理是有悖伦理的吗？那不知道它是如何生产出来的呢？再或者，不了解其使用的副产品呢？
10．随着我们的社会变得越来越自动化，政府监督公民的活动变得越来越容易。这是好还是坏呢？
11．乔治·奥威尔（埃里克·布莱尔）在他的小说《1984》中想象出来的那些技术，其中哪些已经实现了？它们是以奥威尔预想的方式使用的吗？
12．如果你有一台时间机器，你想活在哪个历史阶段？有你想带去的现代技术吗？你选择带去的技术可以脱离其他技术而被你单独带走吗？一项技术可以在多大程度上独立于其他技术？抗议全球变暖，却又接受现代医疗，这两者一致吗？
13．假如由于工作关系，你必须生活在另一种文化氛围中。你会按照自己的本土文化的道德观习惯我行我素，还是会选择遵循当地文化的道德观？你的答案会因该问题会因跟穿衣打扮有关还是跟人权有关而不同吗？如果你是在本土文化中，但需要在因特网上与外国文化打交道，你应该遵循哪些道德标准？
14．在商业、通信或社交互动方面，社会是否过于依赖计算机应用了？例如，如果长期中断因特网或移动电话服务，会有什么后果？
15．大多数智能手机都能够通过GPS来确定手机的位置。这样一来，相关的应用程序就可以基于手机的当前位置提供与该位置相关的信息（如本地新闻、本地天气或者附近的商业机构）。然而，这些GPS功能可能也允许其他应用将手机的位置广播给其他各方。这样好吗？手机的位置（继而手机用户的位置）信息会被如何滥用？
Goldstine, H. H. The Computer from Pascal to von Neumann. Princeton, NJ: Princeton University Press, 1972.
Haigh, T., M. Priestley, and C. Rope. ENIAC in Action: Making and Remaking the Modern Computer. Cambridge, MA: The MIT Press, 2016.
Kizza, J. M. Ethical and Social Issues in the Information Age, 5th ed. London: Springer-Verlag, 2013.
Mollenhoff, C. R. Atanasoff: Forgotten Father of the Computer. Ames, IA: Iowa State University Press, 1988.
Neumann, P. G. Computer Related Risks. Boston, MA: Addison-Wesley, 1995.
Quinn, M. J. Ethics for the Information Age, 7th ed. Essex, England: Pearson, 2016.
Randell, B. The Origins of Digital Computers, 3rd ed. New York: SpringerVerlag, 1982.
Spinello, R. A. and H. T. Tavani. Readings in CyberEthics, 2nd ed. Sudbury, MA: Jones and Bartlett, 2004.
Swade, D. The Difference Engine. New York: Viking, 2000.
Tavani, H. T. Ethics and Technology: Controversies, Questions, and Strategies for Ethical Computing, 5th ed. New York: Wiley, 2016.
Woolley, B. The Bride of Science: Romance, Reason, and Byron’s Daughter. New York: McGraw-Hill, 1999.
微信扫码关注【异步社区】微信公众号，回复“e58263”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
在本章中，我们学习有关计算机中数据表示和数据存储的内容。我们要研究的数据类型包括文本、数值、图像、音频和视频。除了传统计算，本章的很多内容还涉及数字摄影、音频/视频录制和复制，以及远程通信等领域。
本章内容
1.1 位和位存储
1.2 主存储器
1.3 海量存储器
1.4 用位模式表示信息
*1.5 二进制系统
*1.6 整数的存储
*1.7 分数的存储
*1.8 数据与程序设计
*1.9 数据压缩
*1.10 通信差错
计算使人们能够使用创造性开发过程来创建用于创造性表达式的计算制品或解决问题。AP®CSP
学习成果 为创新性表达式创建计算制品。
根据二进制序列构建的各种抽象可用于表示所有数字数据。AP®CSP
学习成果 描述用于表示数据的各种抽象。
学习成果 解释如何用二进制序列来表示数字数据。
用多层抽象来编写程序或创建其他计算制品。AP®CSP
学习成果 确定编写程序时使用的多层抽象。
在将信息表示为数字数据时要有权衡。AP®CSP
学习成果 分析数据表示、存储、安全和数据传输是如何涉及信息计算操纵的。
适当的抽象能使程序设计更容易。AP®CSP
学习成果 使用抽象来管理程序复杂度。
人为不同目的开发、维护和使用程序。AP®CSP
学习成果 评估程序的正确性。
程序设计使用数学和逻辑概念。AP®CSP
学习成果 在程序设计中使用适当的数学和逻辑概念。
人类使用计算机进行创造。软件包、数字媒体、网络内容、数据集、模型和模拟——所有这些都是人们使用计算工具和抽象创建的计算制品的示例。我们首先要学习的是，信息是如何编码和存储在计算机中的。我们的第一步是讨论计算机数据存储设备的基础知识，然后研究如何对信息进行编码才能将其存储到这些系统中。这些系统的绝对复杂性需要从最简单的电子开关构建的硬件门，到我们用于将命令编码为计算机软件的最高级程序设计语言的多层次的强大抽象。
基本知识点
● 计算制品是人类用计算机创造出来的东西，可以是但不限于程序、图像、音频、视频、演示或者网页文件。
抽象允许我们表示许多种数据，但在最底层，在今天的计算机内，所有的信息是以0和1的模式编码的，这些数字称为位（bit，是binary digit的简写，意思是二进制数字）。尽管你可能倾向于把位与数值联系在一起，但它们实际上只是一些符号，其含义取决于正在处理的应用。位模式有时表示数值，有时表示字母表里的字符和标点符号，有时表示颜色和图像，还有时表示声音。
基本知识点
● 数字数据由不同层次的抽象表示。
● 在最底层，所有数字数据都由位表示。
● 在较高层，位被分组用于表示抽象，包括但不限于数、字符和颜色。
● 在抽象的最底层，数字数据只用数字0和1的组合以二进制（基数2）表示。
为了理解单个的位在计算机中是如何存储和操作的，这里我们假设位0表示假（false），位1表示真（true），这样会很方便。为了纪念数学家乔治·布尔（George Boole，1815—1864），处理真/假值的运算被称为布尔运算（Boolean operation）。乔治·布尔是逻辑数学领域的先驱。3个基本的布尔运算是AND（与）、OR（或）和XOR（异或），图1-1概述了这3种运算。（我们之所以用大写字母来表示这些布尔运算符的名字，是为了与它们对应的英语单词区分开来。）这些运算类似于算术运算的乘法和加法，因为它们都是组合一对值（运算的输入），得出第三个值（运算的输出）。不过，与算术运算不同的是，布尔运算组合的是真/假值，而不是数值。
布尔运算AND可用于计算，连接词AND和两个较小或较简单的语句组成的一条语句的真/假值。这种语句的一般形式如下：
PAND Q
其中，P代表一条语句，Q代表另一条语句。例如：
科米是一只青蛙 AND 佩吉小姐是一位演员。
AND运算的输入是复合语句分句的真/假值，输出则是复合语句本身的真/假值。因为P AND Q形式的语句的值只有在其两个分句都是真时才为真，所以可以得出结论：1 AND 1的输出值应该是1，而其他所有情况的输出值都应该是0，如图1-1所示。
图1-1 布尔运算AND、OR和XOR（异或）的可能输入值和输出值
同理，OR运算是建立在如下形式的复合语句的基础之上的：
P OR Q
其中，同样，P代表一条语句，Q代表另一条语句。在至少其中一条组成语句为真时，这种语句才为真，这与图1-1中描述的OR运算一致。
英语中没有可以单独表示XOR运算含义的连词。当两个输入中的一个为1（真）、另一个为0（假）时，XOR运算的输出为1（真）。例如，P XOR Q形式的语句的意思是“或者是P，或者是Q，但不会是两个共存。”（简言之，当两个输入不同时，XOR运算的输出为1。）
NOT（非）运算是另一个布尔运算。它与AND、OR和XOR不同，因为它只有一个输入。它的输出值与输入是相反的；如果NOT运算的输入为真，那么它的输出值就为假，反之亦然。因此，如果NOT运算的输入是下面语句的真/假值：
福齐是一只熊。
那么，其输出就是下面语句的真/假值：
福齐不是一只熊。
门（gate），有时也称逻辑门（logic gate），指的是一种设备，给定一种布尔运算的输入值，门可以得出该布尔运算的输出值。门可以通过很多种技术制造出来，如齿轮、继电器和光学设备。现在的计算机中，门通常是由称为晶体管的小型电子电路实现的，其中数字0和1由电压电平表示。不过，我们不需要关注这种细节问题。对我们来说，知道如何用门的符号形式来表示门就足够了，如图1-2所示。注意，与门、或门、异或门和非门，是由不同形状的符号表示的，输入值在一边，输出值在另一边。
基本知识点
● 逻辑门是用布尔函数建模的硬件抽象。
图1-2 与门、或门、异或门和非门的图形表示及其输入值和输出值
门为构造计算机提供了构建块。因此，布尔逻辑和运算符作为基本运算出现在程序设计语言中。图1-3中的电路描述了这个方向中的一个重要步骤。这是称为触发器（flip-flop）的元件的一个特例。触发器是计算机存储器的基本单元，它是一个可以产生0或1输出值的电路，它的值会一直保持不变，直到有另一个电路过来的脉冲（临时变成1之后再变为0）使其变换成其他值。换句话说，通过设置，可以让输出在外界刺激的控制下“记住”0或者1。例如，在图1-3中，只要电路的两个输入一直都是0，输出值（无论是0还是1）就不会变。不过，在它的上输入临时放一个1，会强制其输出为1；反之，在它的下输入临时放一个1会强制其输出为0。
图1-3 一个简单的触发器电路
基本知识点
● 逻辑概念和布尔代数是程序设计的基础。
让我们来仔细研究一下这个问题。在我们不知道图1-3中电路的当前输出的情况下，假设上面的输入变为1，而下输入仍为0（见图1-4a），那么不管或门的另一个输入是什么，它的输出都将为1。接着，因为与门的另一个输入已经为1（触发器的下输入为0时非门产生的输出），所以它的两个输入现在都将为1。于是，与门的输出将变成1，这意味着，现在或门的第二个输入将为1（见图1-4b）。这样就可以确保即使触发器的上输入变回0（见图1-4c），或门的输出也会保持为1。总之，触发器的输出已经变为1，这个输出值将在上输入变回0后仍然保持不变。
图1-4 将一个触发器的输出值设置为1
同理，在下输入上临时放一个值1会强制触发器的输出为0，并且输出在输入值变回0后保持不变。
我们介绍图1-3和图1-4中的触发器电路的目的有3个。第一，展示设备是如何通过门制造出来的，这是一个数字电路的设计过程，是计算机工程领域的一个重要课题。事实上，在计算机工程中，触发器只是诸多基础工具电路中的一种。
第二，通过触发器的概念为抽象和抽象工具的使用提供一个例子。事实上，还有很多其他的构建触发器的方法。图1-5展示了另一种方法。如果你用这个电路做实验就会发现，尽管它有不同的内部结构，但它的外部特性与图1-3中的是一样的。计算机工程师不必知晓触发器中实际使用的是哪种电路，只需理解触发器的外部特性并将其作为一个抽象工具来使用即可。一个触发器和其他定义良好的电路一起形成了一个构件的集合，工程师可以直接利用这个构件集合构造更复杂的电路。因此，计算机电路的设计就会呈现一种层次结构，其中每层都将较低层次的构件作为抽象工具使用。
图1-5 构建触发器的另一种方法
第三，触发器是现代计算机中存储二进制位的一种方法。更确切地说，可以将触发器的输出值设置为0或1。其他电路可以通过向触发器的输入端发送脉冲来调整这个值，还有一些电路可以通过将这个触发器的输出用作它们的输入来响应存储的值。因此，许多触发器（被构造成非常小的电子电路）可以用作计算机内部记录信息的一种方法，将信息编码为0和1的模式。实际上，众所周知的超大规模集成（very large-scale integration，VLSI）技术支持将数百万个电子元件构造在一个称为芯片（chip）的半导体晶片上，用于创建包含数百万个触发器及其控制电路的微型设备。因此，这些芯片被用作构建计算机系统中较高层构件的抽象工具。事实上，在某些情况下，还可以用超大规模集成技术在单块芯片上创建整个计算机系统。
基本知识点
● 二进制数据由计算硬件（包括门、芯片和元件）的物理层处理。
● 硬件采用多层抽象构建，如晶体管、逻辑门、芯片、存储器、母板、专用卡和存储设备。
考虑计算机的内部活动时，我们必须考虑位模式的处理问题，我们将位模式称为位串，有些位串相当长。长位串常被称为流（stream）。遗憾的是，人脑很难理解流。即便只是抄录位模式101101010011也会令人厌烦，且容易出错。因此，为了简化这种位模式的表示，我们常使用一种称为十六进制记数法（hexadecimal notation）的简写表示法，它是利用机器内的位模式的长度为4的倍数这样一个事实制定的。具体来说就是，十六进制记数法用一个符号表示位模式的4位。例如，一个12位的串只需要3个十六进制符号就可以表示。数学家一般使用下标来表示非十进制数的基数，因此可能会将1510的十六进制值写作F16。习惯用不支持下标的基于文本的语言进行程序设计的计算机科学家通常使用前缀来表明非十进制数的基数。为本书简洁起见，我们也将在十六进制数的前面使用公共前缀“0x”。
图1-6展示了十六进制编码系统。左边一列是所有可能的长度为4的位模式，右边一列是用于表示其左边位模式的十六进制记数法符号。使用这个系统，可以将位模式10110101表示为0xB5。具体方法是：把这个位模式拆分为长度为4的子串，然后用对应的十六进制符号代替每个子串，即用0xB表示1011，用0x5表示0101。以同样的方式，可以将16位模式1010010011001000简化成更易为人接受的形式0xA4C8。我们将在第2章中大量使用十六进制记数法，到时候你就能体会到它的效率了。
图1-6 十六进制编码系统
基本知识点
● 之所以用十六进制（基数16）表示数字数据是因为十六进制表示使用的数位比二进制的少。
1.1节问题与练习
1． 什么样的输入位模式会使下面的电路产生输出1？
2．在正文中，我们断言，在图1-3中的触发器的下输入放一个1（同时保持上输入为0）会迫使触发器的输出为0。描述一下这种情况下触发器内部发生的事件序列。
3． 假定图1-5中的触发器的两个输入都以0开始，描述一下当上输入被临时设为1时发生的事件序列。
4． a．如果一个与门的输出值传递给了一个非门，那么这个组合电路计算的布尔运算称为与非（NAND），当且仅当其两个输入都为1时，其输出为0。与非门的符号和与门的符号类似，只是在输出端有一个圆圈。下面的电路包含一个与非门。这个电路完成的是什么布尔运算？
b．如果一个或门的输出值传递给了一个非门，那么这个组合电路计算的布尔运算称为或非（NOR），当且仅当其两个输入都为0时，其输出为1。或非门的符号和或门的符号类似，只是在输出端有一个圆圈。下面的电路包含一个与门和两个或非门。这个电路完成的是什么布尔运算？
5． 用十六进制记数法来表示下面的位模式。
a．0110101011110010 b．111010000101010100010111 c．01001000
6． 下面的十六进制模式表示的是什么位模式？
a．0x5FD97 b．0x610A c．0xABCD d．0x0100
为了存储数据，计算机包含大量的电路（如触发器），每一个电路能够存储一个位。这种位存储器被称为计算机的主存储器（main memory）。
计算机的主存储器是由称为存储单元（cell）的可管理单元组成的，一个典型存储单元的容量为8位。因为一个8位的串称为一个字节（byte），所以一个典型存储单元的容量是一个字节。嵌在家用电器（如恒温器和微波炉）中的小型计算机的主存储器可能仅有几百个存储单元，但台式计算机和智能手机的主存储器可能有数十亿个存储单元。
虽然计算机中没有左或右的概念，但是我们通常假设存储单元的位是排成一行的。该行的左端称为高位端（high-order end），右端称为低位端（low-order end）。高位端的最左边的一位称作高位或最高有效位（most significant bit）。取这个名称是因为，如果把存储单元里的内容解释为数值，那么这一位就是该数的最高有效位。类似地，低位端的最右边的一位称为低位或最低有效位（least significant bit）。因此，我们可以像图1-7所示的那样描述字节型存储单元的内容。
图1-7 字节型存储单元的组织
为了区分计算机的主存储器中的各个存储单元，每个存储单元都被赋予了一个唯一的“名字”，称为地址（address）。这类似于通过地址找到城市里的一座座房屋。不过，存储单元中的地址都是用数值表示的。更准确地说，我们把所有的存储单元都看作是排成一行的，并按照这个顺序从0开始编号。这样的编址系统不仅为我们提供了唯一标识每个存储单元的方法，而且给存储单元赋予了顺序的概念（见图1-8），这样就有了诸如“下一个单元”或“上一个单元”的说法。
将主存储器中的存储单元和每个存储单元中的位都进行排序，会产生一个重要的结果：计算机的主存储器中的所有二进制位会实际排成一长行。这个长行上的片段可以存储的位模式因此比单个存储单元要长。具体来说，我们只需要两个连续的存储单元就可以存储16位的串。
为了做成一台计算机的主存储器，实际存放二进制位的电路还组合了其他电路，这个电路使得其他电路可以在存储单元中存入和取出数据。以这种方式，其他电路可以通过电信号请求从存储器中得到指定地址的内容（称为读操作），或者通过请求把某个位模式存放到指定地址的存储单元里（称为写操作）。
图1-8 按地址排列的存储单元
因为计算机的主存储器是由独立的、可编址的存储单元组成的，所以可以根据需要独立访问这些存储单元。为了体现用任何顺序访问存储单元的能力，计算机的主存储器常被称为随机存取存储器（random access memory，RAM）。主存储器的这种随机存取特性与1.3节中要讨论的海量存储系统形成了鲜明的对比，在海量存储系统中，长位串被当作合并块来操控。
尽管我们介绍说，触发器是存储二进制位的一种方法，但是在现代的大多数计算机中，RAM都是用其他类似的更复杂的技术制造的，这些技术可以让RAM更小型化、响应时间更短。其中许多技术将位存储为微小的快速消散的电荷。因此，这些设备需要附加电路（称为刷新电路），在一秒内反复补充电荷很多次。因为它的这种易失性，通过这种技术构造的计算机存储器常被称为动态存储器（dynamic memory），于是就产生了术语DRAM（读作“DEE-ram”），用来表示动态RAM（dynamic RAM）。有时动态存储器会用术语SDRAM（读作“ES-DEE-ram”）来表示同步DRAM（synchronous DRAM），采用这种附加技术可以缩短从存储单元中获取信息所需的时间。
在第2章中我们会了解到，如果主存储器中存储单元的总数是2的幂，那么主存储器设计起来会很方便。因此，早期计算机存储器的大小通常以1024（即210）个存储单元为单位来度量。因为1024接近于值1000，所以计算机界采用前缀千（kilo）来表示这个单位。也就是说，术语千字节（kilobyte，符号表示为KB）被用于表示1024字节。因此，带有4096个存储单元的机器会被说成有一个4 KB的存储器（4096 = 4 × 1024）。随着存储器容量变得越来越大，这个术语逐渐扩大到了兆字节（megabyte，符号表示为MB，又称百万字节）、吉字节（gigabyte，符号表示为GB，又称十亿字节）和太字节（terabyte，符号表示为TB，又称万亿字节）。遗憾的是，这种前缀千（kilo-）、兆（mega-）等的用法属于术语的误用，因为这些前缀已经被其他领域用于指称1000的幂。例如，在度量距离时，千米（kilometer）指的是1000米，在度量无线电频率时，兆赫（megahertz）指的是1 000 000 Hz。在20世纪90年代后期，国际标准组织为2的幂制定了专用术语：千位字节（kibi-byte）、兆位字节（mebi-byte）、吉位字节（gibi-byte）和太位字节（tebi-byte），用来表示1024的幂，而不是1000的幂。然而，尽管这种区别在世界上许多地方的当地法律里都有规定，但一直以来，普通大众和许多计算机科学家都不愿意放弃这个已经比较熟悉但会引起歧义的“兆字节”（megabyte）。因此，提醒大家：一般说来，千、兆等术语在涉及计算机度量时表示2的幂，但在其他语境中表示1000的幂。
1.2节问题与练习
1． 如果地址为5的存储单元包含值8，那么“将值5写入6号存储单元”和“将5号存储单元的内容移到6号存储单元”之间的区别是什么？
2． 假定你想交换存储在2号存储单元和3号存储单元中的值。那么下面的步骤错在哪里？
步骤1：把2号存储单元中的内容移到3号存储单元。
步骤2：把3号存储单元中的内容移到2号存储单元。
3．请设计能够正确交换这两个存储单元内容的步骤。如有必要，可以使用额外的存储单元。
4． 一台带有4 KB存储器的计算机，其存储器里有多少个二进制位？
由于计算机的主存储器的易失性和容量的限制，大多数计算机都有称为海量存储（mass storage，或者二级存储）系统的附加存储设备，包括磁盘、CD盘、DVD盘、磁带、闪存驱动器和固态驱动器（所有这些我们稍后会讨论）。相对于主存储器，海量存储系统的优点是更稳定、容量大、价格低，并且在许多情况下，能从机器上取下存储介质进行存档。
磁性和光学海量磁存储系统和海量光存储系统的主要不足是，它们一般都需要机械运动。因为主存储器的所有工作都是由电子元件实现的，所以比起计算机的主存储器来，海量存储系统的数据存取需要花费更长的时间。此外，与固态系统相比，带有移动部件的存储系统更容易出现机械故障。虽然闪存驱动器和固态硬盘不需要移动部件，但其他电子方面的考虑会限制其相对于主存储器的速度和寿命。
基本知识点
● 存储介质的选择对操纵它包含的数据的方法和成本都有影响。
多年来，磁技术已经占据了海量存储领域。最常见的例子便是我们现在使用的磁盘（magnetic disk）或者硬盘驱动器（hard disk drive，HDD），它里面是可以旋转的薄盘片，表面有用以存储数据的磁介质涂层（见图1-9）。读/写磁头安装在盘片的上面和/或下面，当盘片旋转时，每个磁头都能在盘片上面或下面相对于称为磁道（track）的圆圈转动。通过重定位读/写磁头，可以对各个同心的磁道进行存取。在很多情况下，一个磁盘存储系统由安装在公共主轴上的若干盘片组成，两个盘片之间有足够的空间供读/写磁头滑动。在这种情况下，所有读/写磁头是一起移动的。每次读/写磁头重定位时，都可以访问一组新磁道，这组磁道称为柱面（cylinder）。
因为一个磁道可以包含的信息通常比我们每次想要处理的多，所以每个磁道又被划分成若干个称为扇区（sector）的小弧区，这些扇区上记录的信息是连续的二进制位串。磁盘上所有的扇区都包含相同数目的二进制位（典型的容量是512字节到若干KB），而且在最简单的磁盘存储系统里，每个磁道包含的扇区数都相同。因此，靠近盘片外边缘的磁道扇区上的位的存储密度，要比靠近盘片中心的磁道上的小，因为外磁道比内磁道长。相反，在大容量磁盘存储系统里，靠近外边缘的磁道包含的扇区要远多于靠近中心的磁道，这种存储能力常通过一种称作区位记录（zoned-bit recording，ZBR）的技术得以应用。在使用区位记录技术时，一些相邻的磁道被统称为区，一个典型的盘片大约包含10个区。一个区内的所有磁道都有相同数目的扇区，但是靠外的区中每个磁道包含的扇区数，比靠内的区中每个磁道包含的扇区数多。采用这种方式，能够有效利用整个磁盘的表面。不管细节如何，一个磁盘存储系统都包含许多独立的扇区，每个扇区都可以作为一个独立的位串进行存取。
图1-9 磁盘存储系统
一个磁盘存储系统的容量取决于使用的盘片数以及磁道与扇区的划分密度。容量较小的系统可能只有一个盘片，尤其是在硬盘驱动器的物理尺寸必须保持紧凑的情况下。大容量磁盘系统的容量可达数TB，由安装在公共主轴上的3 ~ 6个盘片组成。此外，数据有可能存储在每个盘片的上下两面。
有4个标准可以用来评估一个磁盘系统的性能：（1）寻道时间（seek time）（读/写磁头从一个磁道移到另一个磁道所需的时间）；（2）旋转延迟（rotation delay）（盘片旋转一周所需时间的一半，也就是读/写磁头定位到期望磁道后期望数据旋转到磁头处所需的平均时间）；（3）存取时间（access time）（寻道时间和旋转延迟之和）；（4）传输速率（transfer rate）（数据传入或传出磁盘的速率）。（注意，在使用区位记录的情况下，盘片旋转一次，外区磁道通过读/写磁头的数据量要多于内区磁道，因此，数据传输速率会随使用的盘片部位的不同而有所变化。）其他用于评估海量存储器和更一般的通信系统的重要性能度量指标有：（1）带宽（bandwidth）（单位时间内传输的总位数，如每秒3兆位）；（2）等待时间（latency）（从请求数据传输到数据到达的总时间）。
限制磁盘存取时间和传输速率的一个因素是磁盘系统旋转的速度。为了支持高速旋转，这些系统里的读/写磁头并不接触盘片，而是恰好“悬浮”在盘片表面。磁头与盘片之间的空间很小，以至于一粒小小的灰尘都可能卡在其中，导致磁头和盘片损坏，这一现象便是磁头划伤（head crash）。因此，磁盘系统出厂时都密封在盒子里。凭借这样的构造，磁盘系统能够以每秒几百次的速度旋转，达到每秒数以MB的传输速率。
因为磁盘系统的操作需要物理运动，所以难以与电子电路的速度相比。电子电路的延迟时间是以纳秒（十亿分之一秒）甚至更小的时间单位度量的，而磁盘系统的寻道时间、等待时间和存取时间是以毫秒（千分之一秒）度量的。因此，与电子电路等待结果的时间相比，从磁盘系统检索信息所需要的时间非常长。
磁存储技术现在很少使用了，包括磁带（magnetic tape）和软盘驱动器（floppy disk drive）。磁带是将信息记录在一条绕在卷轴上的薄塑料带的磁涂层上，软盘驱动器则是将带有磁涂层的单个盘片封在一个为了便于从驱动器中取出而设计的便携式的盒子里。磁带驱动器的寻道时间极长（高等待时间），它和录音带、录像带一样，都要花费很长的倒带时间和快进时间。不过，低成本和大数据容量使磁带仍然适用于那些数据主要被线性读或写的应用，如存档数据备份。虽然软盘盘片的可移动特性是以比硬盘盘片低得多的数据密度和存取速度为代价的，但是，在更大容量、更耐用的闪存驱动器诞生之前的几十年里，软盘盘片的便携性还是极其有价值的。
基本知识点
● 系统带宽是位速率的度量单位，位速率是一个固定时间内发送的数据量（用位度量）。
● 系统等待时间是传输和收到请求之间所经过的时间。
另一类海量存储系统应用的是光技术。光盘（compact disk，CD）就是其中的一种。光盘的直径为12厘米（大约5英寸），由涂着光洁保护层的反射材料制成。光盘上的信息是通过在反射层上创建偏差的方法记录的，可以通过激光检测CD快速旋转时反射层的不规则反射偏差来读取。
CD技术最初是用于音频记录的，采用的记录格式叫作数字音频光盘（compact disk-digital audio，CD-DA），而现在的计算机数据存储所用的CD实质上使用的是相同的格式。具体来说，CD上的信息存储在一条磁道上，呈螺旋形缠绕在CD上，很像老式唱片上的凹槽，但与老式唱片不同的是，CD上的磁道是由内至外的（见图1-10）。这条磁道被划分为称为扇区的单元，每个扇区都有自己的标识，数据存储容量为2 KB，这个容量相当于录制音频情况下的1/75秒的音乐。
图1-10 CD存储格式
需要注意的是，盘片外边缘螺旋形磁道的距离比内部螺旋形磁道的要长。为了使CD的存储能力达到最大，信息是以均匀的线性密度存储在整个螺旋形磁道上的，这意味着，在螺旋形磁道上，外部边缘环道存放的信息比内部环道的多。所以，如果盘片旋转一整圈，激光在扫描外部螺旋形磁道时，读到的扇区个数要比扫描内部时读到的多。因此，为了获得统一的数据传输速率，CD-DA播放器要能够根据激光在盘片上的位置来调整盘片的旋转速度。不过，因为用于计算机数据存储的大多数CD系统都以较快的恒定速度旋转，所以必须适应数据传输速率的变化。
这种设计决策的结果是，CD存储系统在处理长且连续的数据串（如音乐复制）时，表现最好。但是，当一个应用需要随机存取数据项时，磁盘存储器所用的方法（单个的同心磁道被划分成独立存取的扇区）就优于CD所用的螺旋形方法。
传统CD的存储容量是600 ~ 700 MB。但是，数字多功能光碟（digital versatile disk，DVD）的存储容量能达到几GB，它由多个半透明层构成，这些层在被精确聚焦的激光查看时充当不同的表面。这种盘片能够存储冗长的多媒体信息，包括完整的电影。最后，蓝光技术（blu-ray technology）使用蓝紫色（而非红色）光谱中的激光，能够极为精确地聚焦激光束。因此，单层蓝光光碟（blu-ray disk，BD）的容量是DVD的5倍多，较新的多层BD格式容量能够达到100 GB。这个看似巨大的存储容量能满足超高清视频的需要。
基于磁技术或光技术的海量存储系统的一个共同特征是，需要通过物理运动（如旋转磁盘、移动读/写磁头和瞄准激光束）来存储和读取信息。这就意味着，其数据的存储和读取速度比电子电路的要慢。闪存（flash memory）技术有克服这个缺点的潜力。在闪存系统里，二进制位是由电子信号直接发送到存储介质中的，电子信号使得该介质中二氧化硅的微小晶格截获电子，从而改变小的电子电路的性质。因为这些微小晶格能够在没有外力的情况下保持截获的电子很多年，所以闪存技术非常适合存储便携、非易失的数据。
尽管存储在闪存系统里的数据能够像在RAM应用中一样，以小的字节型单元存取，但是当前的技术规定存储的数据应批量擦除。不过，反复的擦除会逐渐损坏二氧化硅晶格，这就意味着，当前的闪存技术不适合一般的主存储器应用，因为主存储器的内容可能一秒就改很多次。然而，在那些改变可以被控制在一个合理水平的应用（如数码相机和智能手机）中，闪存已经成为海量存储技术的一个选择。的确，因为闪存对物理震动不敏感（与磁系统和光系统相比），所以它现在正在代替便携式应用（如笔记本计算机）中的其他海量存储技术。
闪存设备称为闪存驱动器（flash drive），容量可达几百GB，可用于一般的海量存储应用。这些闪存设备被封装在越来越小的塑料盒子里，其一端有一个可以取下的帽，当驱动器处于脱机状态时，可以保护这个设备的电子连接器。因为这些便携设备容量大，并且很容易与计算机连接或断开，所以是理想的便携式数据存储器。不过，它们微小存储晶格的易损性决定了它们不像光盘那样可靠，不适合真正的长期应用。
较大的闪存驱动器称为固态驱动器（solid-state drive，SSD），是专为替代磁硬盘设计的。与硬盘相比，固态驱动器防震抗摔性能更好，能更安静地运行（因为没有移动部件），存取时间更短。不过，固态驱动器要比同等大小的硬盘贵，所以在购买计算机时，它仍然被看作高端选择。对于移动应用，如笔记本计算机和智能手机，固态驱动器有明显的优势。虽然固态驱动器扇区也受所有闪存技术所共有的寿命比较有限的影响，但通过耗损均衡（wear-leveling）技术频繁地将改变的数据块重定位到驱动器的新位置上，可以减小这个影响。
闪存技术的另一应用是安全数字（secure digital，SD）存储卡，即SD存储卡（简称SD卡）。SD卡的容量高达2 GB，它们被制成塑料封装的晶圆，有邮票大小（还有更小的小型SD卡和微型SD卡），其中，SD高容量（SD high capacity，SDHC）存储卡，即SDHC存储卡（简称SDHC卡）的存储容量可以高达32 GB，新一代的SD扩展容量（SD extended capacity，SDXC）存储卡，即SDXC存储卡（简称SDXC卡）的容量可超过1 TB。由于这些卡物理结构紧凑，可以方便地插入小型电子设备的插槽，因此它们是数码相机、音乐播放器、汽车导航系统，以及其他许多电子产品的理想选择。
1.3节问题与练习
1．我们可以从加快磁盘或CD转速中获得什么？
2．当记录数据到多盘片存储系统时，我们是应该写满一张盘片后再写另一张盘片，还是应该写满一个柱面后再写另一个柱面？
3．为什么预订系统里的那些需要经常更新的数据应该存储在磁盘里，而不是CD或DVD里？
4．哪些因素能使同一个驱动器能读包含CD、DVD以及蓝光光碟在内的所有光碟？
5．相对于本节介绍的其他海量存储系统，闪存驱动器有什么优势？
6．让磁硬盘驱动器仍具竞争力的优势是什么？
在研究了位存储的技术后，现在来了解一下如何将信息编码为位模式。我们将集中学习一些流行的文本编码方法、数值数据编码方法、图像编码方法以及声音编码方法。每个编码系统都可能会影响到典型的计算机用户。我们的目标是充分了解这些技术，以便知道应用这些技术的效果。
文本形式的信息通常通过代码方式表示，其中文本中的每个不同的符号（如英文字母和标点符号）均被赋予唯一的位模式。这样，文本就表示为一个长的位串，位串中的连续位模式表示的是原文本中的连续符号。
在20世纪的40年代和50年代，人们设计了许多这样的代码，并结合不同的设备使用，随之增加了不少通信问题。为了缓解这种情况，美国国家标准化学会（American National Standards Institute，ANSI，读作“AN–see”）采用了美国信息交换标准码（American Standard Code for Information Interchange，ASCII）。这种代码使用长度为7的位模式来表示大小写英文字母、标点符号、数字0 ~ 9以及某些控制信息（如换行、回车和制表符）。后来，ASCII码通过在每个7位位模式的最高端添加一个0，扩展为8位位模式。这个技术不仅产生了代码（其中代码的每个位模式都能方便地存入典型的字节型的存储单元中），还提供了128个附加位模式（通过给附加的位赋予值1），可以用于表示除英语字母和关联的标点符号之外的符号。
美国国家标准化学会
美国国家标准化学会（ANSI）成立于1918年，是由一些工程师协会和政府机构联合创办的非营利性联盟，致力于协调私人部门自发标准的发展。现在，ANSI成员中有1300多个企业、专业组织、行业协会和政府机构。ANSI的总部设在纽约，它是美国在ISO的代表。
其他国家/地区的类似组织包括澳大利亚标准组织（Standards Australia）、加拿大标准委员会（Standards Council of Canada）、中国国家质量技术监督局（China State Bureau of Quality and Technical Supervision）、德国标准化学会（Deutsches Institut für Normung）、日本工业标准调查会（Japanese Industrial Standards Committee）、墨西哥标准指导委员会（Dirección General de Normas）、俄罗斯国家标准计量委员会（State Committee of the Russian Federation for Standardization and Metrology）、瑞士标准化协会（Swiss Association for Standardization）和英国标准学会（British Standards Institution）。
8位位模式的一部分ASCII码在附录A中给出。利用这个附录，我们可以将位模式
01001000 01100101 01101100 01101100 01101111 00101110解码为消息“Hello.”，如图1-11所示。
国际标准化组织（International Organization for Standardization）简称ISO，这个简称来源于希腊语中的“isos”一词，意思是平等。ISO开发了大量的ASCII扩展，每种扩展都是针对某一主要语种设计的。例如，其中一个标准提供了表达大部分西欧语言文本所需的符号。在其128个附加模式中，有表示英镑和德语元音ä、ö、ü的符号。
图1-11 消息“Hello.”的ASCII或UTF-8编码
ISO——国际标准化组织
国际标准化组织（常称为ISO）建立于1947年，现在它的总部设在瑞士日内瓦，有100多个成员团体和许多通信成员。（通信成员不能直接参与标准的开发，但可以了解ISO的活动。）
ISO扩展的ASCII标准在支持全世界多语言通信方面取得了巨大进展，但是，仍有两个主要障碍。首先，扩展的ASCII中额外可用的位模式数不足以容纳许多亚洲语言和一些东欧语言的字母表。其次，因为一个特定文档只能使用一个选定标准中的符号，所以无法支持包含不同语种的语言文本的文档。实践证明，这两点严重妨碍了ASCII码的国际化使用。为弥补这一不足，Unicode在一些主要软硬件厂商的合作下诞生了，并迅速赢得了计算界的支持。这种代码采用唯一的21位模式表示每个符号。当Unicode字符集与Unicode转换格式8位（Unicode transformation format 8-bit，UTF-8）编码标准结合在一起时，原来的ASCII字符仍然可以用8位来表示，而像汉语、日语和希伯来语这样的语言所产生的数以千计的其他字符则可以用16位来表示。除了可以表示世界上所有常用语言所需的字符，UTF-8的24位或32位模式还可以表示比较鲜为人知的Unicode符号，为未来的扩展留出了充足的空间。
由一长串根据ASCII或Unicode编码的符号组成的文件常称为文本文件（text file）。区分下面两类文件很重要：一类是由称为文本编辑器（text editor，常简称为编辑器）的实用程序操作的简单文本文件；一类是由字处理程序（word processor），如微软的Word，产生的较复杂的文件。两者都是由文本材料组成的，但是，文本文件只包含文本中各个字符的编码，而由字处理程序产生的文件还包含表示字体变化、对齐信息等的附加结构。
当所记录的信息是纯数值的时，以字符编码的形式存储信息效率就会很低。为了了解其中的原因，让我们来看看值25的存储问题。如果我们坚持用ASCII编码符号来存储，每个符号1字节，那么总共需要16个二进制位。此外，用16个二进制位可以存储的最大数是99。不过，我们马上就可以看到，使用二进制记数法（binary notation），16个二进制位可以存储0 ~ 65535范围内的任何一个整数。因此，二进制记数法（或它的变体）被广泛用于计算机存储器中数值数据的编码。
二进制记数法是一种只使用数字0和1来表示数值的方法，与传统的用数字0、1、2、3、4、5、6、7、8和9表示数值的十进制记数系统不同。我们将在1.5节中更详细地学习二进制系统，现在只需要初步了解该系统。为此，我们来考虑一种老式的汽车里程表，它的显示轮只包含数字0和1，而不是传统的十进制数字0 ~ 9。里程表以全0读数开始，在汽车行驶的前几公里，最右方的滚动显示轮从0旋转至1；当这个1旋转回0时，会使其左边出现一个1，产生模式10；接着，右边的0旋转至1，产生模式11；现在，最右边的数从1旋转回0，使得它左边的1也旋转回0，这就使另一个1出现在第三位上，产生模式100。简言之，在我们驾驶汽车时，将看到下列顺序的里程表读数：
0000
0001
0010
0011
0100
0101
0110
0111
1000这个序列包括了整数0 ~ 8的二进制表示。尽管这种计数技术有些冗长乏味，但是如果我们扩展它，就会发现16个1组成的位模式表示的是值65 535，这就证实了我们的说法：0 ~ 65 535范围内的任何整数都可以用16个二进制位来编码。
由于它的高效性，数字信息通常使用某种形式的二进制记数法来存储，而不用编码符号。我们之所以说“某种形式的二进制记数法”，是因为上面描述的简单二进制系统只是机器里应用的若干数值存储技术的基础。本章后面会讨论一些二进制系统的变体。现在，我们只需要知道，称为二进制补码（two’s complement）记数法（见1.6节）的系统通常用于存储整个数，因为它提供了一种便利的表示负数和正数的方法。为了表示
或
这样带有分数部分的数，我们还要使用一种称为浮点记数法（floating-point notation）的技术（见1.7节）。
最后，无论编写数字时我们是用二进制记数法（基数2）、更熟悉的十进制记数法（基数10），还是用简短的十六进制记数法（基数16），表示的底层数字量都是一样的。也就是说，对于2加2等于4，无论我们是用二进制记数法（010 + 010 = 100）、十进制记数法（2 + 2 = 4）、十六进制记数法（0x2 + 0x2 = 0x4），还是任何其他进制来写，都是对的。对计算机来说，它只是二进制的1和0。
基本知识点
● 数字基数包括2、10和16，被用于表示和研究数字数据。
● 数字可以从任何一种基数转换为任何其他基数。
图像的一种表示方法是：将图像解释为一组点，每个点称为一个像素（pixel，是picture element的简写）；然后，对每个像素的显示进行编码，整个图像就表示成了这些编码像素的集合，这个集合称为位图（bit map）。这种方法很常用，因为许多显示设备（如打印机和显示屏）都是基于像素概念操作的。因此，位图格式的图像更便于格式化显示。
位图中的像素编码方式随着应用的不同而不同。对于简单的黑白图像，每个像素由一个位表示，位的值取决于相对应像素是黑还是白。这是大多数传真机采用的方法。对于更加精致的黑白照片，每个像素由一组位（通常是8个）表示，这使得许多灰色阴影也可以表示出来。对于彩色图像，每个像素通过更为复杂的系统来编码。表示图像的常见的方法有两种，一种是RGB编码，每个像素表示为3种颜色成分——红、绿、蓝，它们分别对应于光线的三原色。每种颜色成分的强度一般是用1字节来表示。因此，要表示原始图像中的一个单独像素，就需要3字节的存储空间。
另一种替代简单RGB编码的方法是，使用一个“亮度”成分和两个颜色成分。在这种方法中，“亮度”成分被称为像素亮度，基本上就是红、绿、蓝三种颜色成分的总和。（事实上，它是像素中白光的数量，但是现在我们不需要考虑这些细节。）其他两种成分，称为蓝色色度和红色色度，分别由像素中的像素亮度与蓝光或红光数量之间的差来决定。这3个成分合在一起就包含了再现这个像素所需的全部信息。
利用亮度和色度成分对图像进行编码这种方式的普及源自彩色电视广播领域，因为这种方法提供的彩色图像编码方式可以兼容老式黑白电视接收器。事实上，只需要利用编码彩色图像的亮度成分就可以制造出图像的灰度版本。
用位图表示图像的缺点在于，图像不能轻易调整到任意大小。基本上，放大图像的唯一途径就是变大像素，而这会使图像模糊。（这就是应用于数字照相机的“数字变焦”技术，与此相对的“光学变焦”是通过调整照相机镜头实现的。）
图像的另一种表示方法避免了这个缩放问题，将图像描述成了几何结构（如直线和曲线）的集合，这些几何结构可以用解析几何技术来编码。这种描述允许最终显示图像的设备决定几何结构的显示方式，而不是让设备再现特殊像素模式。这种方法被用在了当今的字处理系统中，用于产生可缩放的字体。例如，TrueType（由微软公司和苹果公司开发）是用几何结构描述文本符号的系统，而PostScript（由Adobe系统开发）提供了一种描述字符及更一般的图形数据的方法。这种表示图像的几何方法在计算机辅助设计（computer-aided design，CAD）系统中也很常见，用于在计算机显示屏上显示和操控三维物体的绘制。
许多绘图软件系统（如微软的画图工具）都允许用户用预先设定的形状（如矩形、椭圆形、基本线条等）画图，对这些用户来说，用几何结构表示图像与用位图表示图像之间的区别是很明显的。用户只需从菜单中选择所需的几何形状，就可以用鼠标绘制出形状。在绘制过程中，软件保存了所画形状的几何描述。当鼠标给出方向后，内部的几何表示就被修改，再转化成位图形式显示出来。这种方法方便图像的缩放和形状的改变。然而，一旦绘制过程完成，系统就会去除基本的几何描述，仅保存位图，这意味着，再做其他修改需要经历冗长的一个像素接一个像素的修改过程。另外，一些绘图系统会将描述作为几何图形保存下来，并允许在之后进行修改。有了这些系统，就可以轻松地调整图形的大小，并可按各种尺寸显示清晰图像。
为了便于计算机存储和操作，对音频信息进行编码的最常用方法是，按有规律的时间间隔对声波的振幅采样，并记录所得到的值序列。例如，序列0、1.5、2.0、1.5、2.0、3.0、4.0、3.0、0可以表示这样一种声波：它的振幅先增大，然后经短暂的减小，再升至更高的幅度，接着又减回至0（见图1-12）。这种技术采用每秒8000次的采样频率，已经在远程语音电话通信中使用了许多年。通信一端的语音被编码为数值，表示每秒8000次的声音振幅。接着，这些数值通过通信线路被传输到接收端，用来重现声音。
尽管每秒8000次的采样频率似乎是很快的速率，但它还是满足不了音乐录制的高保真需求。为了实现现在音乐CD重现声音的质量，我们需要采用每秒44 100次采样的采样频率。每次采样得到的数据要用16位的形式表示（32位用于立体声录制）。因此，录制成立体声音乐，每秒需要100多万个位。
乐器数字化接口（musical instrument digital interface，MIDI，读作“MID–ee”）是另外一种编码系统，被广泛用于电子键盘的音乐合成器、视频游戏声音，以及网站的辅助音效。MIDI是在合成器上编码产生音乐的指令，而不是对音乐本身进行编码，因此它避免了采样技术那样的大存储容量要求。更精确地说，MIDI是对什么乐器演奏什么音符以及持续时间进行编码。例如，单簧管演奏D音符2秒，可以编码为3字节，而不必按照每秒44 100次的采样频率用两百多万个二进制位来编码。
图1-12 序列0、1.5、2.0、1.5、2.0、3.0、4.0、3.0、0所表示的声波
简言之，可以把MIDI看作对演奏者乐谱进行编码的一种方式，而不是对演奏本身编码。因此，MIDI“录制”的音乐在不同合成器上演奏时声音可能是截然不同的。
1.4节问题与练习
1．下面是用ASCII编码的一条消息，每个符号8位。它的含义是什么？（见附录A）
01000011 01101111 01101101 01110000 01110101 01110100 01100101
01110010 00100000 01010011 01100011 01101001 01100101 01101110
01100011 011001012．在ASCII码中，大写字母的ASCII码和这个字母的小写字母的ASCII码之间的关系是什么？（见附录A）
3．用ASCII码对下列语句编码：
a．“Stop!” Cheryl shouted.
b．Does 2+3＝5?
4．描述一种能够呈现两种状态的日常设备，例如，旗杆上的旗帜的升降。给一种状态赋值1，另一种赋值0，请说明当以这样的位来存储时，字母b的ASCII码会怎样表示？
5．将下列二进制表示分别转化为相应的十进制形式。
a．0101 b．1001 c．1011 d．0110 e．10000 f．10010
6．将下列的十进制表示分别转化为相应的二进制形式。
a．6 b．13 c．11 d．18 e．27 f．4
7．如果每个数字采用每字节一个ASCII码的模式编码，那么3字节可以表示的最大数值是多少？如果采用二进制记数法呢？
8．除十六进制记数法以外，另一种表示位模式的方法是点分十进制记数法（dotted decimal notation），其中每个字节由相应的十进制数表示，这些字节表示之间用句点分隔。例如，12.5表示模式0000110000000101（12表示字节00001100，5表示字节00000101），而136.16.7表示模式100010000001000000000111。用点分十进制记数法表示下列位模式：
a．0000111100001111
b．001100110000000010000000
c．0000101010100000
9．相对于位图技术，用几何结构表示图像有哪些优点？位图技术相对于几何结构又有哪些优点？
10．假如采用文中所讨论的每秒44 100次采样的采样频率，对1小时音乐的立体声录音进行编码。请问这段音乐编码的大小与一张CD的存储容量相比结果如何？
在1.4节中我们看到，二进制记数法是表示数值的一种方法，它只使用数字0和1，而不用较常见的十进制记数系统中的10个数字0 ~ 9。现在，我们来深入了解一下二进制记数法。
回顾十进制系统，表示中的每个位置都与一个量值相关联。在375这个表示中，5的位置与量值1相关联，7的位置与量值10相关联，3的位置与量值100相关联（见图1-13a）。每个量是它右边量的10倍。整个表达式表示的值是每个数字的值与与其相关联的位置的量值相乘所得积之和。举例说明：模式375表示(3×100) + (7×10) + (5×1)，用更加技术性的表示法表示就是(3×102) + (7×101) + (5×100)。
图1-13 十进制和二进制系统
在二进制记数法中，每个数字的位置也与一个量值相关联，只是与每个位置相关联的那个量值是它右边量值的2倍。更精确地说，在二进制表示中，最右边的数字与量值1（即20）相关联，其左边的下一个位置与量值2（即21）相关联，下一个与量值4（即22）相关联，再下一个与量值8（即23）相关联，依次类推。例如，在二进制表示1011中，最右边的1的位置与量值1相关联，接下来的1的位置与量值2相关联，0的位置与量值4相关联，最左边的1的位置与量值8相关联（见图1-13b）。
为了求得二进制表示所表示的值，我们可以采取和十进制相同的步骤：先将每个数字的值与与其相关联的位置的量值相乘，再计算各个乘积之和。例如，100101表示的值是37，如图1-14所示。注意，因为二进制记数法仅使用数字0和1，这种求积再求和的步骤就可以简化为求数字的值为1的位置相关联的量值的和。因此，二进制模式1011表示的是十进制值11，因为3个1的位置分别与量值1、2和8相关联。
图1-14 二进制表示100101的解码
在1.4节中，我们学习了如何用二进制记数法计数，这使得我们可以对小整数进行编码。为了求得大值的二进制表示，你可能更喜欢图1-15中所描述的算法。让我们利用这个算法来求十进制值13的二进制表示（见图1-16）。首先，将13除以2，得到商6和余数1。因为这个商不是0，步骤2告诉我们还要将商（6）除以2，得到新的商3和余数0。最新的商仍然不为0，所以再除以2，得到商1和余数1。再一次，将最新的商（1）除以2，此时得到商0和余数1。因为现在的商是0，我们进入步骤3，在这一步中，我们从余数列中得到原数（13）的二进制表示1101。
图1-15 求正整数二进制表示的算法
图1-16 利用图1-15中的算法求13的二进制表示
为了理解两个用二进制表示的整数的相加过程，首先让我们回顾一下用传统十进制记数法表示的值的相加过程。例如，考虑下面这道题：
我们先把最右列的8和7相加，得到和15，把5记录在这一列的底部，向下一列进1，得到：
现在我们把下一列的5和2相加，再加上进到这一列的1，得到和8，把8记录在这一列的底部。结果如下：
简而言之，这个过程就是从右到左将每列中的数字相加，把和中的最低有效位写在列的底部，把和中的较高有效位（如果有）进位到下一列。
为了将两个用二进制表示的正整数相加，我们采用相同的步骤，只是所有和的计算都使用图1-17中展示的加法规则，而不是你在小学所学的传统的十进制加法法则。
图1-17 二进制加法法则
例如，为了解下面这道题：
首先将最右边的0和1相加，得到1，写在该列下方。接着将下一列的1和1相加，得到10。把其中的0写在该列下方，将进位1写在下一列的上方。这时，解答如下：
把下一列的1、0和0相加，得到1，将1写在该列下方。下一列的1和1总和为10，将0写在该列下方，进位1写在下一列。现在，解答如下：
下一列的1、1和1总和为11（值3的二进制表示），将低位1写在该列下方，将另外一个进位1写在下一列的上方。把进位1与那列原本的1相加，得到10。再一次，将低位0写在该列下方，将进位1写在下一列的上方。现在得到
下一列的唯一项就是1，是从上一列进位来的，所以我们将其记录在答案里。最终的答案是：
为了扩展二进制记数法，使其能够表示分数值，我们使用了基数小数点（radix point），其功能与十进制记数法中的小数点是相同的，即点左边的数字代表值的整数部分（整个部分），其解释和前面讨论的二进制系统一样。点右边的数字代表值的小数部分，其解释和其他二进制位类似，只是它们的位置被赋予了分数的量值。更确切地说，基数小数点右边第一位的量值是1/2（即2-1），下一位的量值是1/4（即2-2），再下一位是1/8（即2-3），依次类推。注意，这仅仅是前面所述规则的延续：即每位所被赋予的量值是它右边大小的两倍。利用这些赋予二进制位位置的量值，对包含基数小数点和不包含基数小数点的二进制表示进行解码的步骤基本是相同的。更精确地说，我们是把表示中的每个位的值与其对应位的位置的量值相乘。举例来说，将二进制表示101.101解码为
，如图1-18所示。
另外，应用于十进制系统的加法技术同样适用于二进制系统，即两个有基数小数点的二进制表示相加时，我们只需要对齐基数小数点，然后应用前面介绍的加法步骤进行计算即可。例如，10.011加100.11得111.001，如下所示：
图1-18 二进制表示101.101的解码
1.5节问题与练习
1．将下列二进制表示转换为相应的十进制形式。
a．101010 b．100001 c．10111 d．0110 e．11111
2．将下列十进制表示转换为相应的二进制形式。
a．32 b．64 c．96 d．15 e．27
3．将下列二进制表示转换为相应的十进制形式。
a．11.01 b．101.111 c．10.1 d．110.011 e．0.101
4．用二进制记数法表示下列值。
a. b. 
c. 
d. 
e.
5．按照二进制记数法做下列加法。
a．11011 b. 1010.001 c．11111 d. 111.11
+ 1100 + 1.101 + 0001 + 00.01
数学家长久以来就对数字记数系统很感兴趣，而且他们的许多想法已经被证实与数字电路的设计是相符的。本节，我们将研究其中两种记数系统：二进制补码记数法和余码记数法。它们都是计算设备用于表示整数值的方法。虽然这些系统都是基于二进制系统的，但是它们增加了一些其他的特性，因而与计算机设计更加兼容。尽管它们有这么多的优点，但是它们也有缺点。我们的目标是了解这些特性以及它们是如何影响计算机用法的。
模拟与数字
在21世纪之前，许多研究人员都在讨论数字技术和模拟技术的优缺点。在数字系统中，一个值会被编码成一系列数字，存储在若干设备中，每个设备代表一个数字。在模拟系统中，每个值存储在一个单独的设备中，该设备可以表示一个连续范围内的任何值。
让我们用水桶作为存储设备来比较一下这两种方法。为了模拟数字系统，我们可以约定用空桶表示数字0，用满桶表示数字1。然后我们可以使用浮点记数法（见1.7节）将一个数值存储在一排水桶中。相反，为了模拟一个模拟系统，我们用水桶的水位表示数值。乍一看，模拟系统看起来更精确，因为它不会受到数字系统固有的截断误差（见1.7节）的影响。不过，在模拟系统中，水桶的任何移动都可能导致水位检测出错，而在数字系统中，则必须有剧烈的晃动才能区分出水桶是满的还是空的。因此，数字系统对误差的敏感度低于模拟系统。这种健壮性是许多最初基于模拟技术的应用（如电话通信、音频录制和电视）都转而使用数字技术的主要原因。
现今计算机中最流行的用于表示整数的系统是二进制补码（two’s complement）记数法。这个系统采用固定数目的二进制位来表示系统中的每个值。现今设备中普遍采用二进制补码系统，其中每个值用一个32位的模式表示。这种大系统能表示很大范围的数字，但不方便演示。因此，在学习二进制补码系统的特性时，我们将着重介绍较小的系统。
图1-19列出了两种完整的二进制补码系统，一种基于长度为3的位模式，另一种基于长度为4的位模式。要构造这种系统，首先要规定一组适当长度的二进制0，接着用二进制计数，直到前面只有一个0、后面都是1的模式形成。这些模式表示值0, 1, 2, 3, …。要想获得表示负值的模式，首先要规定一组适当长度的二进制1，接着按照二进制反向计数，直到前面只有一个1、后面都是0的模式形成。这些模式表示值-1, -2, -3, …。（如果你认为利用二进制反向计数有困难，那么可以从表格底部前面只有一个1、后面都是0的模式开始，向上计数到全是1的模式。）
图1-19 二进制补码记数系统
注意，在二进制补码系统中，位模式最左边的二进制位指明了所表示的值的符号。因此，最左边的位常称为符号位（sign bit）。在二进制补码系统中，符号位为1的模式表示负值，符号位为0的模式表示非负值。
在二进制补码系统中，绝对值相同的正负值的表示模式之间有一种对应关系，从右向左读时，直到第一个二进制1（包括那个1），它们都是相同的。然后，以这个1为分界线，左面的位模式互为补码。（要得到一个模式的补码（complement），需要将所有的二进制0转换为1，并将所有的二进制1转换为0。）例如，在图1-19所示的4位系统中，表示2和-2的模式都是以10结尾，但是表示2的模式是以00开始，而表示-2的模式是以11开始。观察到这一点，我们就可以得出在表示绝对值相同的正负值的位模式之间进行来回转换的算法。我们只需要从右到左复制原始模式直到第一个1，然后在将剩余位转换为最终位模式时，对这些剩余位取反（见图1-20）。
图1-20 用4位二进制补码记数法对值6编码
理解了二进制补码系统的这些基本特性，还可以得出二进制补码表示的一个解码算法。如果要解码的模式有一个符号位0，我们只需要读这个值，就好像这个模式是一个二进制表示。例如，0110表示十进制值6，因为110是6的二进制表示。如果要解码的模式有一个符号位1，我们就知道表示的值是负的，而我们所要做的就是找到其绝对值。为了实现这个目的，我们首先要利用图1-20中的“复制和取反”步骤，然后对获得的模式进行解码，就好像它只是一个简单的二进制表示。例如，为了对模式1010解码，我们首先要认识到，因为这个符号位是1，所以表示的值是负的。因此，我们利用“复制和取反”步骤获得模式0110，认识到这是6的二进制表示之后，我们得出结论：原始模式表示的是-6。
为了把二进制补码记数法表示的值相加，我们采用二进制加法中使用的算法，只是包括答案在内的所有位模式都是一样长的。这就意味着，在二进制补码系统中做加法时，如果最后一个进位导致答案左边产生了附加位，那么这个附加位一定会被截断。因此，0101和0010“相加”得0111，0111和1011“相加”得0010（0111+1011= 10010，被截断为0010）。
根据这个理解，我们来分析一下图1-21中的3个加法题。这里的每种情况，我们都把问题转化为二进制补码记数法（采用长度为4的位模式），演示了先前描述过的加法过程，然后对结果进行解码，回到一般的十进制记数法。
图1-21 转换为二进制补码记数法的加法题
注意，图1-21中的第三道题涉及的是一个正数和一个负数的加法，它展示了二进制补码记数法的一个主要优点：有符号数的任意组合的加法，都可以使用相同的算法来完成，因而可以使用相同的电路来实现。这与人类传统上的算术运算方式截然不同。尽管小学生是先学加法，后学减法，但是使用二进制补码记数法的机器只需知道如何相加就可以了。
例如，减法问题7-5与加法问题7+（-5）是一样的。因此，如果机器被要求计算7（存储为0111）减5（存储为0101），那么它首先要将5转换为-5（表示为1011），然后执行0111+1011的加法过程，得到0010，它代表值2，如下所示：
由此可见，当用二进制补码记数法表示数值时，只需要将一个加法电路和一个取反电路组合在一起，就足以同时解决加法和减法这两个问题了。（这些电路的图示及解释详见附录B。）
我们在前面的例子中避开了这样一个问题：任何一个二进制补码系统所能表示的值大小都有限制。当使用4位模式二进制补码记数法时，可以表示的最大正整数是7，最小负整数是-8。具体来说，就是无法表示值9，这意味着我们不能指望得出5+4的正确答案。事实上，它的结果会显示为-7。这种现象称为溢出（overflow）。也就是说，溢出指的是计算得出的值超出了可以表示的值的范围。使用二进制补码记数法时，两个正值相加或两个负值相加都可能会出现这种情况。无论哪种情况，检查答案的符号位就可以发现溢出的条件。如果两个正值相加的结果是负值的模式，或者两个负值相加的结果为正，那么就发生了溢出问题。
当然，因为使用二进制补码系统的大多数计算机的位模式，都比我们上面例子中给出的长，所以在处理较大值时不会产生溢出。如今，人们普遍使用二进制补码记数法的32位模式来存储值，可以得到的最大正值是2 147 483 647。如果需要更大的值，我们可以使用更长的位模式，或者改变度量单位。例如，在解答一个问题时用英里代替英寸，所得的数就会变小，而且可以达到所需的精度。
关键问题是计算机会制造错误。因此，使用机器的人一定要意识到可能涉及的危险。其中一个问题就是，计算机程序员和使用者会自满而导致忽视一个事实——较小的值可以累加成较大的值。例如，人们过去普遍使用二进制补码记数法的16位模式表示值，这意味着，出现大于或等于215 =32 768的值时就会产生溢出。1989年9月19日，一家医院多年来运行良好的计算机出现了故障。仔细检查后发现，那天距1900年1月1日共32 768天，而计算机程序正是基于那个起始日期开始计算日期的。因此，由于溢出，1989年9月19日产生了负值——设计计算机程序时没有考虑到这种现象。
基本知识点
● 有限表示用于建模数的无限数学概念。
● 在许多程序设计语言中，用于表示字符或整数的固定位数限制了整数值的范围和数学运算；这个限制会导致溢出或其他错误。
● 整数可能会由于存储的局限性被限制在程序能表示的最大值和最小值之间。
表示整数值的另外一种方法是余码记数法（excess notation）。与二进制补码记数法相同，余码记数系统中的每个值也都是用相同长度的位模式表示的。为了建立余码系统，我们首先要选择要使用的模式长度，然后根据二进制记数呈现的顺序写下那个长度的所有位模式。接着我们发现，二进制1作为其最高有效位的第一个模式大约就在数列的中间。我们用这个模式表示0，其后的模式分别用于表示1, 2, 3, …，其前的模式就分别用于表示-1, -2, -3, …。使用长度为4的模式产生的编码如图1-22所示。我们可以看到，模式1101表示值5，模式0011表示值-5。（注意，余码系统和二进制补码系统的一个区别就是符号位相反。）
图1-22所示的系统称为余8记数法。为了了解其由来，我们先用传统二进制系统的编码解释每个模式，然后将其与余码记数法表示的值进行比较。你会发现，在每种情况下，二进制解释的值都比余码记数法解释的值大8。例如，模式1100在二进制记数法中表示值12，但在余码系统中表示4；0000在二进制记数法中表示值0，但在余码系统中表示-8。与此类似，在基于长度为5的位模式的余码系统中，模式10000表示的是0，而不是通常的值16，该记数法称为余16记数法。同样，你可以证明3位余码系统应该称为余4记数法（见图1-23）。
图1-22 余8代码转换表
图1-23 使用长度为3的位模式的余码记数系统
1.6节问题与练习
1．将下面每个二进制补码表示转换为相应的十进制形式。
a．00011 b．01111 c．11100
d．11010 e．00000 f．10000
2．用8位位模式将下列每个十进制表示转换为相应的二进制补码形式。
a．6 b．-6 c．-17
d．13 e．-1 f．0
3．假定下列位模式表示的是用二进制补码记数法存储的值，求出每个值的负值的二进制补码表示。
a．00000001 b．01010101 c．11111100
d．11111110 e．00000000 f．01111111
4．假定一台机器用二进制补码记数法存储值，如果机器分别采用下列长度的位模式，那么可以存储的最大数和最小数分别是什么？
a．4 b．6 c．8
5．在下列各题中，每个位模式表示一个用二进制补码存储的值。请执行文中所述的加法过程，按照二进制补码记数法求出它们的答案。并将题及答案转换为十进制记数法进行验证。
a．0101+0010 b．0011+0001 c．0101+1010
d．1110+0011 e．1010+1110
6．计算下列二进制补码记数法表示的题，但这次要观察溢出问题，并指出哪个答案因产生溢出而不正确。
a．0100+0011 b．0101+0110 c．1010+1010
d．1010+0111 e．0111+0001
7．将下列各题从十进制记数法转换为长度为4的位模式的二进制补码记数法，然后将每道题转换成一个相应的加法题（像机器做的那样），并执行加法。将求得的答案转换为十进制记数法进行验证。
a．6-(-1) b．3-(-2) c．4- 6
d．2-(-4) e．1- 5
8．在二进制补码记数法里，一个正数和一个负数相加时会产生溢出吗？请说明理由。
9．将下面每个余8码表示转换为相应的十进制形式（解题时不要看文中的表格）。
a．1110 b．0111 c．1000
d．0010 e．0000 f．1001
10．将下列的每个十进制表示转换为相应的余8码形式（解题时不要看文中的表格）。
a．5 b．-5 c．3
d．0 e．7 f．-8
11．值9可以用余8记数法表示吗？用余4记数法表示6呢？请说明理由。
不同于整数的存储，对于带有分数部分的值的存储，我们不仅要存储代表其二进制表示的0和1模式，还需要存储其基数小数点的位置。有一种流行的基于科学记数法的存储方法，称为浮点（floating-point）记数法。计算机的有限存储空间限制了我们能表示的分数的精度，下一节还会回到这个问题上。
基本知识点
● 实数是通过不一定有无限精度的浮点表示近似得到的。
为了解释浮点记数法，我们来看一个只用1字节来存储的例子。尽管机器通常使用更长的模式，但是这种8位格式也可以表示实际的系统，而且既可以展示重要的概念，又避免了长位模式的混乱。
首先，我们规定这个字节的高位端为符号位。再次说明，符号位中的二进制0代表存储的值为非负值，1代表值为负值。接着，我们将这个字节剩余的7个位分为两组，或称其为域：指数域（exponent field）和尾数域（mantissa field）。我们规定符号位右边的3个位为指数域，余下的4个位为尾数域。图1-24描述了如何拆分字节。
图1-24 浮点记数法成分
我们可以借助下面的例子来解释这些域的含义。假如1字节由位模式01101011组成。利用前面的格式分析这个模式，可以看出符号位是0，指数是110，尾数是1011。为了解码这个字节，我们首先要提取它的尾数，并在它的左边放一个基数小数点，得到
.1011接着，我们提取指数域（110）的内容，并将其解释为一个用3位余码方法（见图1-23）存储的整数。从而得出，我们所举例子的指数域模式表示正数2。这就要求我们将上面所得结果的基数小数点向右移动2位。（负指数域就意味着向左移动基数小数点。）因此，我们得到
10.11这就是的二进制表示（二进制中的分数的表示参见图1-18）。接着，我们注意到：示例中的符号位是0，因此所表示的值为非负值。最后我们得出结论：字节01101011表示。如果模式是11101011（除了符号位都与之前相同），表示的值将为
。
再看一个例子，考虑字节00111100。提取尾数后得到
.1100因为指数域（011）表示值-1，所以将基数小数点向左移动一位，得到
.01100这表示
。因为原始模式中的符号位是0，所以存储的值为非负值。最后我们得出结论：模式00111100表示。
在用浮点记数法存储值时，要将前面的过程反过来。例如，为了对编码，我们首先要将其用二进制记数法表示，得到1.001。接着，我们从二进制表示中最左边的1开始，从左到右将其位模式复制到尾数域。此时，这个字节看起来像下面这样：
1 0 0 1现在我们必须填充指数域。为了达到这个目的，假定尾数域的左边有一个基数小数点，然后规定位的数量以及小数点移动的方向，以此得到原始的二进制数。在这个例子中我们看到，0.1001中的基数小数点要向右移动一位才能得到1.001，指数因此为正1，所以我们将101（这在余4记数法中表示正1，见图1-23）放在指数域中。最后，因为存储的是非负值，我们用0填充符号位。完成的字节看起来像下面这样：
0 1 0 1 1 0 0 1在填充尾数域时，你可能会漏掉一个微妙的细节。这个规则是从最左边的1开始，从左到右复制以二进制表示的位模式。为阐述清楚，让我们考虑一下存储值的过程，它的二进制记数法表示为.011。这时，其尾数将是
1 1 0 0而不会是
0 1 1 0这是因为我们是从二进制表示最左边的1开始填充尾数域的。遵循这个规则的表示称为规范化形式（normalized form）。
使用规范化形式消除了同一个值有多种表示的可能性。例如，00111100和01000110都可以解码成值，但是只有第一个模式是规范化形式。遵循规范化形式也意味着，所有非0值的表示都会有一个以1开始的尾数。不过，值0是一个特例，它的浮点表示是全0的位模式。
下面我们来考虑一下，用我们的1字节浮点记数系统存储值，看看
会出现什么恼人的问题。我们首先用二进制写，得到10.101。但是，在把这个模式复制到尾数域时，我们就用尽了空间，最右边的1（表示最后的
）因此丢失了（见图1-25）。如果现在忽视这个问题，继续填充指数域和符号位，那么我们最后得到的位模式将为01101010，它表示的是
，而不是。这个现象称为截断误差（truncation error）或舍入误差（round-off error）。这意味着要存储的值的这部分会因尾数域空间不够大而丢失。
基本知识点
● 在许多程序设计语言中，用于表示实数（像浮点数一样）的固定位数限制了浮点值的范围和数学运算，这个限制会导致舍入误差和其他误差。
通过使用较长的尾数域可以显著减少这种误差。事实上，现在生产的大多数计算机都至少采用32位存储浮点记数法表示的值，而不是我们这里用的8位。这同时使得指数域也更长。不过，即使有这些较长的格式，还是会有需要更高的精度的时候。
图1-25 值的编码过程
截断误差的另一个来源是十进制记数法中比较常见的一个现象，即无穷展开式问题。例如，我们在用十进制形式表示
的时候。有些值无论我们用多少位数字都无法精确地表示。传统的十进制记数法与二进制记数法的区别在于，二进制记数法中有无穷展开式的值多于十进制。例如，值
表示为二进制时为无穷展开式。想象一下，一个粗心的人用浮点记数法存储和处理美元与美分时可能会导致什么问题？尤其是，如果用美元作度量单位，那么一角就不能被精确地存储。这种情况的一种解决方案是，以分为单位处理数据，这样所有的值就都是整数了，都可以用诸如二进制补码这样的方法来精确存储。
单精度浮点数
1.7节介绍的浮点记数法过于简单，不能用于实际的计算机中。毕竟，在全部实数中，这一记数法的8位只能表示其中256个数。虽然我们在讨论中使用了8位模式，但在保持示例简单的情况下，也涵盖了重要的基本概念。
现在的许多计算机都支持32位形式的单精度浮点（single precision floating point）记数法。这一格式用1位表示符号，用8位表示指数（余码记数法中的），用23位表示尾数。因此，单精度浮点数最多有7位十进制有效数字，可以表示极大的数（数量级为1038）直至极小的数（数量级为1037）。也就是说，给定一个十进制数，可以非常精确地存储前7位十进制有效数字（但仍有可能存在少量误差），前7位之后的数字一定会因截断误差而丢失（虽然数字的近似值会被保留下来）。
另一种形式是64位的双精度浮点（double precision floating point）记数法，最多有15位十进制有效数字。
截断误差和与之相关的问题是工作在数值分析领域的人们每天都很关注的问题。这个数学分支研究的是执行大规模、高精度有效计算所涉及的问题。
下面的例子可以激起任何一位数值分析家的兴趣。假设我们要应用前面定义的1字节浮点记数法来做这3个值的加法：
如果我们按照上述顺序将值相加，先将加到上，得到，其二进制表示为10.101，那么，很遗憾，因为这个值不能被精确地存储（如同前面所看到的），第一步的结果最后被存储为（与其中一个加数相同）。下一步是把这个结果再加到最后的上。截断误差在这里又一次出现，最后的结果是错误的。
现在让我们以相反的顺序来加这些值。先将加到上，得到
，其二进制表示为.01。于是，第一步的结果在1字节里被存储为00111000，这是精确的。然后，我们将这个加到算式中的下一个值上，得到，就可以在1字节里精确地将其存储为01101011。这次的答案是正确的。
总而言之，在浮点记数法表示的数值加法中，它们相加的顺序很重要。问题是，如果一个很大的数加上一个很小的数，那么小的数就可能被截断。因此，多个值相加的一般规则是先把较小的值加在一起，希望它们被加到一个较大的值上时，能累计成一个显著的值。这就是前面例子中反映的现象。
现在的商用软件包的设计师在这方面做得很好，他们使没有经过培训的使用者也能很好地避免这种问题的发生。在一个典型的电子表格系统中，除非相加的各个值大小差别达到1016或更多，否则所得结果都是正确的。因此，如果你认为有必要对值
10 000 000 000 000 000加1，那么会得到答案
10 000 000 000 000 000而不是
10 000 000 000 000 001这样的问题在一些应用（如导航系统）中是很严重的，微小的误差会在加法运算中累加，最终产生严重的后果。但是，对于一般的PC使用者，大多数商用软件提供的精度已经足够了。
1.7节问题与练习
1． 用文中所述的浮点格式对下列位模式进行解码。
a．01001010 b．01101101 c．00111001 d．11011100 e．10101011
2． 将下列值编码成文中所述的浮点格式。指出截断误差的出现情况。
a． 
b．
c． d．
e．
3． 根据文中所述的浮点格式，模式01001001和00111101中哪一个表示的值更大？描述一种确定哪个模式表示的值更大的简单过程。
4． 使用文中所述的浮点格式时，可以表示的最大的值是多少？可以表示的最小的正值是多少？
虽然人类发明了构成现代计算机的数据表示和基本操作，但很少有人特别擅长于直接在计算机的这个层面上工作。人们喜欢在更高的抽象层次上推理计算问题，他们依赖计算机来处理最底层的细节问题。程序设计语言（programming language）是人类创造的一个计算机系统，通过它，人们能够使用更高层次的抽象来向计算机精确地表达算法。
在20世纪，对计算机进行程序设计被认为是少数训练有素的专家们才能涉足的领域；当然，仍然有许多计算问题需要有经验的计算机科学家和软件工程师的关注。不过，到了21世纪，随着计算机和计算与我们现代生活中的方方面面交织在一起的程度的日益加深，越来越难以确定哪些职业不需要至少有某种程度的编程技能。事实上，一些人已经把程序设计或编码确定为现代读写能力中继阅读、写作及算术之后的又一个基础支柱了。
在本节以及后续章节的程序设计补充部分，我们会看到程序设计语言是如何反映本章主要内容，以及如何让人类更容易地解决涉及计算的问题的。
Python是一门程序设计语言，由吉多·范罗苏姆（Guido van Rossum）于20世纪80年代后期创立。现在它是十大最常用的语言之一，仍然深受网络应用开发领域及科学计算领域人士的喜爱，并被视为学生的入门语言。使用Python的组织范围很广，从谷歌到美国国家航空航天局（NASA），从DropBox公司到工业光魔公司（Industrial Light & Magic），横跨非正式、科学和艺术计算机用户。Python强调可读性，包括命令型程序设计范型、面向对象程序设计范型和函数式程序设计范型等三大要素，这些将在第6章中介绍。
用于编辑和运行用Python编写的程序的软件可以从Python官方网站上免费获得，这里还有很多其他的入门资源。Python语言一直在不断演变，本书的所有示例都将使用Python 3这个版本。较早的Python版本能够运行非常类似的程序，但是自Python 2版本开始有了许多细微的变化，如标点符号。
Python是一种解释型语言（interpreted language），这意味着初学者可以将Python指令键入交互提示符中，或者将Python指令存储在一个（称为“脚本”的）纯文本文件里以后运行。在下面的示例中，这两种模式都可以使用，但练习和复习题一般都要求用Python脚本来完成。
许多程序设计语言的介绍长久以来一直有一个传统，描述的第一个程序都是“Hello, World”。这个简单的程序输出一个名义上的问候，演示一种特定语言是如何产生结果以及如何表示文本的。在Python[1]中，这个程序的写法如下：
[1] 下面这个Python代码是用该语言的第3版写出来的，本书后面会直接把这个版本的Python称作“Python”。较早的Python版本并不总是需要开括号和闭括号。
print('Hello, World!')可以将这条语句键入Python的交互解释器里，也可以把它保存为Python脚本然后再执行。不管用哪一种方式，最后的结果都应该是：
Hello, World!Python会把两个引号之间的文本返回给用户。
即使是在这种简单的Python脚本里，也有几个需要注意的方面。首先，print()是一个内置函数，是Python脚本用来产生输出的一个预定义操作，输出指的是一个能够让用户看到的程序结果。这个打印函数后面有一个开括号和一个闭括号，这两个括号之间的内容就是要打印的值。
其次，Python可以使用单引号来表示文本串。大写字母H前面的引号和感叹号后面的引号，分别表示由字符组成的字符串的开头和结尾，在Python中，这个字符串会被当作值。
程序设计语言能够非常精确地完成它们的指令。即使用户只是稍微修改一下打印语句中开始引号和结束引号之间的消息，最后打印出来的文本也会相应地变化。花一点儿时间，在打印语句中试试不同的大小写、不同的标点符号，甚至不同的单词，读者会看到确实是这样。
Python允许用户给值命名以备日后使用，这是构造简洁、易懂的脚本时的一个重要抽象。这些命名的存储位置被称为变量（variable），类似于代数课程中的数学变量。下面来看一下略有增强的“Hello World”版本：
message = 'Hello, World!'
print(message)在这个脚本中，第一行是赋值语句（assignment statement）。“=”号的使用可能会让习惯了等号的代数用法的初学者感到迷惑。这个赋值语句应该读作：“变量message被赋予字符串值'Hello, World!'。”通常，赋值语句由等号左边的变量名和等号右边的值构成。
Python是一种动态类型（dynamically typed）语言，这意味着，我们不需要在建立脚本时提前创建好一个名为message的变量，或者确定什么类型的值应该存储在message中，而只需要在这个脚本中说明我们的文本串会被赋给message，接着在后面的print语句中引用这个变量message就行了。
变量的命名很大程度上取决于Python用户。Python的简单规则是：变量名必须以字母开头，可以包含任意数量的字母、数字和下划线字符（_）。虽然对一个两行的示例脚本来说，可能把变量命名为m就可以了，但有经验的程序员都会尽量为脚本中的变量起一个有意义的、具有描述性的名字。
Python变量名是区分大小写的（case-sensitive），即有大小写问题。名为size的变量，与名为Size或SIZE的变量是截然不同的。有一小部分关键字（keyword），即为Python中的一些特殊含义保留的名字，不能用作变量名。在Python的内置帮助系统里能查看到这个关键字清单。
help('keywords')变量可用于存储Python能表示的所有类型的值。
my_integer = 5
my_floating_point = 26.2
my_Boolean = True
my_string = 'characters'观察上面这些值的类型，它们与本章前面介绍的表示方法是相对应的：布尔值真和假（见1.1节）、文本（见1.4节）、整数（见1.6节）和浮点数（见1.7节）。通过Python的其他代码（超出了本书简单介绍的范围），我们还能够用Python变量存储图像和声音数据（见1.4节）。
Python使用0x前缀来表示十六进制值，如
my_integer = 0xFF
print(my_integer)不管程序员在推理过程中使用什么样的记数系统，指定一个十六进制的值都不会改变计算机存储器中该值的表示，存储器都会把整数值存储为许多个1和0。十六进制记数法仍然是人类在用的一种有助于理解脚本的快捷表示。因此，上面的print()语句打印出来的是255，即十六进制0xFF的十进制解释，因为这是print()的默认行为。用更复杂的print()语句可以输出其他表示的值，但本书只讨论我们比较熟悉的十进制表示。
Unicode字符包含着无所不在的ASCII子集中所没有的字符，当文本编辑器支持Unicode字符时，可以直接在字符串里包含Unicode字符：
print('₹1000'] # Prints ₹1000, one thousand Indian Rupees也可以用前缀'\u'和4个十六进制数字来指定Unicode字符：
print('\u00A31000') # Prints £1000, one thousand British
# Pounds Sterling字符串的'\u00A3'部分会对英镑符号的Unicode表示进行编码。'1000'紧跟在后面，这样最终输出的货币符号和数量之间就不会有空格了：£1000。
除了Unicode文本串，这些示例语句引入了另一种语言特性。#号表示注释（comment）的开始，这是一个人类可读的Python代码符号，在计算机执行时会被忽略。有经验的程序员会在他们的代码中使用注释来解释算法难懂的部分，包括历史或来源信息，或者只写些读这段代码的人应该注意的问题。脚本顶端的高级描述向人类阅读者介绍脚本的总体目标和脚本中使用的方法。#号右边一直到行尾的所有字符都会被Python忽略。
基本知识点
● 程序的解释能帮助人们理解程序的功能和用途。
Python的内置运算符允许人们以各种熟悉的方式对数值进行操作和组合。
print(3 + 4) # Prints "7", which is 3 plus 4.
print(5 - 6) # Prints "−1", which is 5 minus 6
print(7 * 8) # Prints "56", which is 7 times 8
print(45 / 4) # Prints "11.25", which is 45 divided by 4
print(2 ** 10) # Prints "1024", which is 2 to the 10th power 基本知识点
● 在程序中使用整数和浮点数时不需要理解它们是如何实现的。
● 数和数字概念是程序设计的基础。
● 使用算术运算符的数学表达式是大多数程序设计语言的一部分。
当一个运算（如45除以4）产生的是非整数结果（如11.25）时，Python会将表示类型隐式转换为浮点表示。如果希望结果是整数，就要使用另外一组运算符：
print(45 // 4) # Prints "11", which is 45 integer divided by 4
print(45 % 4) # Prints "1", because 4 * 11 + 1 = 45双斜线（//）表示整除（integer floor division）运算符，百分号（%）表示取模（modulus）或取余运算符。将这两个计算综合起来，可读作：“4除45等于11，余数为1。”在前面的示例中，我们用**表示幂运算符，这看起来可能有些奇怪，因为在打印文本甚至一些其他程序设计语言中，幂运算符一般都是用插入符号（^）表示。在Python中，^运算符是一种按位布尔运算（bitwise Boolean operation）运算符，有关按位布尔运算的内容将在下一章中介绍。
还可以用一些直观的方式对字符串值进行组合和操作。
s = 'hello' + 'world'
t = s * 4
print(t) # Prints "helloworldhelloworldhelloworldhelloworld"其中，加运算符（+）用于拼接（concatenate）字符串值，乘运算符（*）用于复制（replicate）字符串值。
基本知识点
● 字符串和字符串操作（包括拼接和某种形式的子字符串）在许多程序中很常见。
有些内置运算符的多重含义会导致混淆。下面这个脚本会产出一个错误：
print('USD$' + 1000) # TypeError: Can't convert 'int' to str implicitly这个错误指明，字符串拼接运算符不知道在第二个操作数不是字符串的情况下要怎么做。不过幸运的是，Python提供了允许将值从一种表示类型转换为另外一种表示类型的函数。int()函数能把浮点型值转换回整数表示，丢弃分数部分。如果字符串可以正确地拼出一个有效数字，那么int()函数还能将一个文本数字串转换为一个整数表示。同样，str()函数能把数字表示转换成UTF-8编码的文本串。因此，对上述print语句做如下修改就能改正错误。
print('USD$' + str(1000)) # Prints "USD$1000"下面这个完整的Python脚本示例演示了许多本节要介绍的概念。给定一定数量的美元，脚本会对其进行货币转换，转换成4种其他货币。
# A converter for international currency exchange.
USD_to_GBP = 0.76 # Today's rate, US dollars to British Pounds
USD_to_EUR = 0.86 # Today's rate, US dollars to Euros
USD_to_JPY = 114.08 # Today's rate, US dollars to Japanese Yen
USD_to_INR = 63.64 # Today's rate, US dollars to Indian Rupees
GBP_sign = '\u00A3' # Unicode values for non-ASCII currency symbols.
EUR_sign = '\u20AC'
JPY_sign = '\u00A5'
INR_sign = '\u20B9'
dollars = 1000 # The number of dollars to convert
pounds = dollars * USD_to_GBP # Conversion calculations
euros = dollars * USD_to_EUR
yen = dollars * USD_to_JPY
rupees = dollars * USD_to_INR
print('Today, $' + str(dollars)) # Printing the results
print('converts to ' + GBP_sign + str(pounds))
print('converts to ' + EUR_sign + str(euros))
print('converts to ' + JPY_sign + str(yen))
print('converts to ' + INR_sign + str(rupees))执行该脚本时，输出如下：
Today, $1000
converts to £760.0
converts to €860.0
converts to ¥114080.0
converts to 63640.0程序设计语言对初学者不是很宽容，初学者在编写软件时，需要花费大量的时间努力查找代码中的bug或者错误。定位这些bug并修正它们因此称为调试（debugging）。软件中的bug可分为3大类：语法错误（syntax error，键入时产生的符号错误）、语义错误（semantic error，程序含义的错误）和运行时错误（runtime error，程序运行时发生的错误）。
基本知识点
● 定位和修正程序中的错误被称为调试程序。
对新手来说，语法错误是最常见的，包括一些简单的错误，如忘记文本串开头或者结尾的其中一个引号，没有关闭开括号，或者拼错函数名print()。当Python解释器遇到这些错误时，通常会努力指出这些错误，显示问题代码所在行的行号以及问题描述。经过一些练习之后，初学者能很快学会识别和解释常见的错误情况。下面来看几个例子：
print(5 + )
SyntaxError: invalid syntax上述表达式在加法运算符和闭括号之间缺少一个值。
print(5.e)
SyntaxError: invalid tokenPython希望基数小数点后面是数字，而不是字母。
pront(5)
NameError: name 'pront' is not defined就像叫错一个人的名字一样，拼错已知函数或变量的名字会产生混淆和尴尬。
语义错误是算法中的缺陷，或者某种语言表达算法方式中的缺陷。这样的例子可能包括：在一个计算中使用了错误的变量名，或者弄错了复杂表达式中算术运算符的顺序。Python遵循运算符优先级的标准规则，所以在像total_pay = 40 + extra_hours * pay_rate这样的表达式中，乘法会在加法之前执行，错误地计算总工资。（除非你的工资率恰好是1美元/小时。）使用括号正确地指定复杂表达式中的运算顺序，如total_pay = (40 + extra_hours) * pay_rate，既可以避免语义错误，又可以避免写出的代码难于理解。
最后，这个层次上的运行时错误可能包括：无意识地除以0，或者使用未定义的变量。Python是从上到下读取语句的，在表达式里使用变量之前，Python必须看到变量的赋值语句。
测试（testing）是高效编写Python脚本（或者任何种类的实际程序）必不可少的一部分。在编写脚本时要频繁运行它，可能每完成一行代码就需要运行一次。这样做能尽早识别和修复语法错误，把程序设计者的注意力集中在脚本每一步应该做什么上。
基本知识点
● 知道程序应该做什么才能找出大多数程序错误。
1.8节问题与练习
1． 是什么使Python成为一门解释型程序设计语言？
2．编写Python语句输出下列内容。
a．“Computer Science Rocks”这些词，后面跟一个感叹号。
b．数42。
c. π的近似值，精确到基数小数点后第四位。
3．编写Python语句按下列描述给变量赋值。
a．将“programmer”这个词赋值给一个名为rockstar的变量。
b．将1小时的秒数赋值给一个名为seconds_per_hour的变量。
c．将人体的平均温度赋值给一个名为bodyTemp的变量。
4．编写一条Python语句，给定一个已有的名为bodyTemp的变量，单位为华氏度，将与其相等的摄氏度存储到一个名为metricBodyTemp的新变量中。
为了存储或传输数据，在保留基础信息的同时，缩小所涉及数据的大小是有益的（有时也是强制的）。用于完成这一过程的技术称为数据压缩（data compression）。本节，我们首先学习一些通用的数据压缩方法，然后了解一些为特殊应用设计的方法。
数据压缩方案有两类，一类是无损的（lossless），另一类是有损的（lossy）。无损方案在压缩过程中是不丢失信息的，有损方案在压缩过程中会丢失信息。通常有损技术比无损技术更能压缩，因此在可以容忍小错误的应用中很流行，如图像和音频压缩。
基本知识点
● 在使用有损压缩技术和无损压缩技术来存储和传输数据方面需要权衡。
对于被压缩数据由一长串相同的值组成的情况，流行使用称为行程长度编码（run-length encoding）的压缩技术，这是一种无损方法。它的过程是，将一组相同的数据成分替换成一个编码，指出重复的成分以及其在序列中出现的次数。例如，指出一个位模式包括253个1，接着118个0，接着87个1，这样要比实际列出458个位节省空间。
另外一种无损数据压缩技术是频率相关编码（frequency-dependent encoding），在这个系统里，用于表示数据项的位模式的长度与这个项的使用频率是反相关的。这种编码是变长编码的例子，意思是项由不同长度的模式表示。戴维·哈夫曼（David Huffman）的功劳是发现了一种常用于开发频率相关编码的算法，人们一般称用这种方法开发的编码为哈夫曼编码（Huffman code）。因此，现在使用的大多数频率相关编码都是哈夫曼编码。
让我们看一个频率相关编码的例子，考虑一下编码英文文本的任务。在英文中，字母e、t、a和i的使用频率要大于字母z、q和x。因此，当为英文文本编码时，如果用短位模式表示前面的字母，用长位模式表示后面的字母，就能节省空间。用这种方式编码的英文文本的表示长度要比用统一长度编码的短。
在某些情况下，要压缩的数据流由数据单元组成，每个数据单元与其前面一个的差别很小。动画的连续帧就是一个例子。在这种情况下，使用相对编码（relative encoding）——也称为差分编码（differential encoding）——技术是很有用的。这些技术记录的是两个连续数据单元之间的区别，而不是整个单元；也就是说，每个单元是根据其与前一个单元的关系被编码的。相对编码可以用无损形式实现，也可以用有损形式实现，具体取决于两个连续数据单元之间的差别是精确编码的还是近似编码的。
还有其他流行的基于字典编码（dictionary encoding）技术的压缩系统，这里的术语字典（dictionary）指的是一组构建块，压缩的消息通过它们建造起来，而消息本身被编码成字典的一系列参照。我们一般认为字典编码系统是无损系统，不过在学习图像压缩时我们将看到，有时候字典条目仅仅是正确数据成分的近似值，这就使其成了有损压缩系统。
字处理程序可以使用字典编码来压缩文本文档，因为这些字处理程序中已经包含了用于拼写检查的字典，而这些字典都是出色的压缩字典。特别值得一提的是，一个完整的单词可以编码为字典的一个单独参照符，而不是像使用UTF-8这样的系统那样编码成一系列单个字符。在字处理程序中，一个典型的字典大约有25 000个条目，这意味着，单个的字典条目可以用0到24999范围内的整数来标识。也就是说，字典中的一个特定条目用15位的模式就足可标识。与之相比，如果用到的单词包括6个字母，则它的逐字符编码在使用UTF-8时需要48位。
字典编码的一个变体是自适应字典编码（adaptive dictionary encoding，也称动态字典编码）。在自适应字典编码系统中，字典在编码过程中是可以改变的。一个流行的例子是LZW编码（Lempel-Ziv-Welsh encoding），这个编码的名称是根据它的创造者Abraham Lempel、Jacob Ziv和Terry Welsh的姓氏命名的。要用LZW对消息编码，首先要从包含基础构建块的字典开始，用字典中的构建块来构造消息。但是，当人们在消息中发现较大的单元时，会把它们加到字典中——这意味着，这些单元在未来出现时可以被编码为一个（而不是多个）字典参照。例如，当对英文文本编码时，人们首先要从包含单独字符、数字和标点符号的字典开始。但是，当消息中的单词被标识后，会被加到字典中。因此，随着消息的不断编码，字典会不断增大，而随着字典的不断增大，消息中会有更多的单词（或者重复的单词模式）被编码为单个的字典参照。
结果将是，消息用一部相当大的、完全针对本消息的字典进行编码。但是在对这条消息进行解码时，不必用这个大字典，只需用原始的小字典即可。事实上，解码过程可以与编码过程用同一个小字典。接着，随着解码过程的继续，它会遇到编码过程中发现的相同单元，进而将它们加到字典中，作为未来编码过程的参照。
举例说明，考虑对下列消息应用LZW编码：
xyx xyx xyx xyx首先从一个只有3个条目的字典开始，第一个条目是x，第二个条目是y，第三个条目是一个空格。我们先将xyx编码为121，意思是这条消息的第一个模式依次包括第一个字典条目、第二个字典条目和第一个字典条目。接着，空格被编码，产生结果1213。但是，因为有了一个空格，我们知道前面的字符串已经形成了一个单词，所以我们将模式xyx加到字典中作为第四个条目。继续使用这种编码方式，整条消息将被编码为121343434。
如果我们现在从原始的3条目字典开始对这条消息进行解码，那么我们首先要将起始的1213串解码为xyx后加1个空格。这时我们意识到字符串xyx形成了一个单词，因此将其加到字典中作为第四个条目，同编码过程中所做的一样。我们接着对这条消息解码，发现消息中的4指的是这第四个新条目，将其解码为单词xyx，产生模式
xyx xyx继续使用这种解码方式，我们最终把字符串121343434解码为
xyx xyx xyx xyx这就是原始消息。
基本知识点
● 虽然无损数据压缩会减少存储或传输的位数，但允许完整重构原始数据。
● 有损数据压缩可以大大减少存储或传输的位数，但代价是只能重构原始数据的近似值。
在1.4节中，我们已经看到如何用位图技术对图像编码。不过，得到的位图通常是非常大的。因此，人们专门为图像表示开发出了许多压缩方案。
一种称为GIF（是graphic interchange format的缩写，即图像交换格式，一些人将其读作“Giff”，还有一些人将其读作“Jiff”）的系统是CompuServe公司开发的一个字典编码系统。它处理压缩问题的方法是，将赋予一个像素的颜色数量减少到只有256个。每种颜色的“红—绿—蓝”组合都用3字节编码，这256个编码被存储在一个称为调色板的表格（字典）里。图像中的每个像素都可以用一个字节表示，该字节的值指明了这个像素的颜色是由256个调色板条目中的哪一个表示的。（回顾一下，一个字节能够包括256个不同位模式中的任意一个。）注意，在将GIF应用于任意图像时，它是一个有损压缩系统，因为调色板中的颜色可能与原始图像中的颜色不一致。
通过使用LZW技术将这个简单的字典系统扩展为自适应字典系统，GIF可以进一步压缩。尤其是，编码过程中遇到的像素模式可以被加到字典中，使这些模式在将来出现时可以被更加高效地编码。因此，最终的字典是由原始调色板和一组像素模式构成的。
GIF调色板中的某一个颜色通常会被赋予值“透明”，这意味着背景色可以透过每个被赋予该“颜色”的区域展现出来。这个选择与GIF系统的相对简便性相结合，使得GIF成为简单动画应用（这种动画应用中的多重图像只能在计算机屏幕上移动）的合理选择。另外，它只能够对256种颜色编码，这使得它不适合精度要求较高的应用，如摄影领域。
另外一种流行的图像压缩系统是JPEG（读作“JAY-peg”）。它是由ISO中的联合图像专家组（Joint Photographic Experts Group，标准因此得名）研制开发的标准。JPEG已经被证明是压缩彩色照片的一种有效标准，并被广泛用于摄影业，这一点可由大多数数码相机都将JPEG作为它们默认的压缩技术这一事实来印证。
JPEG标准实际上包含多种图像压缩方法，每种都有它自己的目标。在需要尽可能精确的情况下，JPEG可提供无损模式。不过，相对于JPEG的其他模式，JPEG的无损模式不会产生高级别的压缩。此外，JPEG的其他模式已被证明很成功，这意味着人们很少使用JPEG的无损模式。相反，称为JPEG基线标准（也称为JPEG的有损顺序模式）的JPEG模式已经成为许多应用的选择标准。
使用JPEG基线标准的图像压缩需要几个步骤，其中有一些是利用人眼的局限性设计的。尤其是，相对于颜色的变化，人眼对亮度的变化更为敏感。因此，我们首先来看一幅根据亮度成分和色度成分进行编码的图像。第一步是在一个2×2的像素方块中求色度的平均值。这能将色度信息的大小减小为1/4，同时保留所有的原始亮度信息。结果是，在没有明显损失图像质量的情况下获得了很高的压缩率。
下一步是将图像划分成多个8×8的像素块，并将每个块中的信息压缩为一个单元。这可以通过一种称为离散余弦转换的数学技术来实现，这里我们不需要关心这个转换的细节。重要的一点是，这种转换能将原始的8×8块变成了另一种块（这种块中的条目反映了原始块中的像素之间是如何相互联系的），而不是实际的像素值。在这个新块里，那些低于预订阈值的值将被替换成0，反映的事实是这些值所表示的变化非常小，人眼无法觉察。例如，如果原始块中包含一个棋盘（checkerboard）模式，那么新块就可能表现为均匀的平均色。（一个典型的8×8像素块表示的是图像中一个非常小的方块，因此人眼根本不能够识别棋盘的外观。）
这时候，可以应用更传统的行程长度编码、相对编码以及变长编码技术进行进一步的压缩。总之，JPEG基线标准一般能在没有明显质量损失的情况下，将彩色图像压缩至少10倍，有时甚至能压缩30倍。
另一个与图像相关的数据压缩系统是TIFF（tagged image file format的缩写，即标记图像文件格式）。不过，TIFF最普遍的应用不是数据压缩，而是存储照片及其相关的信息（如日期、时间以及相机设置）的一个标准格式。在存储照片时，图像本身通常会被存储为没有压缩的红、绿、蓝像素成分。
TIFF标准集合里的确有数据压缩技术，其中大多数是为在传真应用中压缩文本文档的图像设计的。为了利用文本文档包含长串的白色像素这一事实，这些标准使用了行程长度编码的变体。TIFF标准中的彩色图像压缩选择是以类似于GIF所使用的技术为基础的，因此并没有被广泛应用于摄影业。
最常用的音频及视频的编码和压缩标准是由ISO领导的运动图像专家组（Motion Picture Experts Group，MPEG）开发的，因此这些标准称为MPEG。
MPEG包含许多不同应用的各种标准。例如，高清电视（high definition television，HDTV）广播的要求与视频会议的要求就不同，广播信号必须找到在各种容量可能很有限的通信路径上传输的方式。另外，这两种应用又都不同于以可回放或跳过片断的方式存储视频的应用。
MPEG使用的技术已经超出了本书的范围，但是一般说来，视频压缩技术是以图片序列构建成的视频为基础的，与将运动图像录制到胶片上的方式基本相同。为了压缩这样的序列，只有一些称为I帧（I-frame）的图片是被整个编码的。两个I帧之间的图片是采用相对编码技术进行编码的，也就是说，不对整个图片进行编码，只记录与前一个图片的差别。I帧本身经常使用类似于JPEG的技术进行压缩。
最著名的音频压缩系统是MP3，它是在MPEG标准中开发出来的。事实上，MP3是MPEG layer 3的缩写。与其他压缩技术相比，MP3利用人耳的特性，删除了人耳觉察不到的细节。其中一个特性称为时域掩蔽（temporal masking），指的是在一次巨大声响后，短时间内人耳觉察不到本可以听见的轻柔声音。另一个称为频域掩蔽（frequency masking），指的是某一频率的声音可能掩盖相近频率的轻柔声音。利用这些特性，可以通过MP3获得显著的音频压缩，而且保持接近CD的音质。
使用MPEG和MP3压缩技术，摄像机用128 MB的存储空间就可以录制长达1小时的视频，便携音乐播放器用1 GB的存储空间就可以存储多达400首流行歌曲。但是，不同于其他压缩目的，音频和视频的压缩目的不一定是节省存储空间。真正重要的是获得编码，使信息能够通过现在的通信系统得到及时的传输。如果每个视频帧需要1 MB的存储空间，而传播帧的通信路径每秒只能中继1 KB，那么根本无法实现成功的视频会议。因此，除了被认可的复制质量，音频和视频压缩系统的选择还要看及时数据通信所需的传输速度。这些速度通常用位每秒（bits per second，bit/s）来度量。常见的单位包括Kbit/s（kilo-bps的简写，即千位每秒，等于103 bit/s）、Mbit/s（mega-bps的简写，即兆位每秒，等于106 bit/s）和Gbit/s（giga-bps的简写，即吉位每秒，等于109 bit/s）。使用MPEG技术，视频展示可以在40 Mbit/s传输速率的通信路径上成功中继。MP3录制需要的传输速率一般不超过64 Kbit/s。
1.9节问题与练习
1．列出4种通用的压缩技术。
2．如果使用LZW压缩，并且字典最初只包含x、y和一个空格（如文中所述），对下列消息编码，结果是什么？
xyx yxxxy xyx yxxxy yxxxy3．在对彩色卡通编码时，为什么GIF比JPEG要好？
4． 假设你是航天器设计团队的一员，要设计能驶向其他星球并发回照片的航天器。那么，为了减少存储和传输图像所需的资源，使用GIF或JPEG的基准标准压缩照片是否是一个好主意？
5． JPEG的基准标准利用了人眼的什么特性？
6． MP3利用了人耳的什么特性？
7． 说出一种在把数字信息、图像和声音编码为位模式时常见的麻烦现象。
当信息在一台计算机的各个部分之间来回传输，或者在月球和地球之间来回传输，又或者只是被保存在存储器中时，最终检索到的位模式有可能和原始的位模式不一致。磁记录面上的油脂或灰尘颗粒，或者出了故障的电路，都可能使数据被错误地记录或读取。传输通道上的静电干扰可能会损坏部分数据。在某些技术条件下，普通的背景辐射（background radiation）可以改变存储在机器的主存储器中的模式。
为了解决这样的问题，人们开发了许多编码技术来检测甚至校正差错。现在，由于这些技术被大规模地内置于计算机系统的内部构件中，因此计算机的使用者并不了解它们。不过，它们的存在很重要，对科学研究有重大贡献。因此，我们有必要了解其中一些使现在设备可靠的技术。
有一种简单的检测差错的方法，其依据的原则是：如果被操作的每个位模式都有奇数个1，却遇到了有偶数个1的模式，那么一定是出错了。要使用这个原则，需要编码系统中的每个模式都有奇数个1。这是很容易做到的，首先在已经可用的编码系统中的模式（也许在高位端）上添加一个称为奇偶校验位（parity bit）的附加位。根据不同情况，我们给这个新的位赋值1或0，使整个结果模式有奇数个1。一旦这样修改了编码系统，出现有偶数个1的模式就表示出现了差错，被操作的模式是不正确的。
图1-26展示了如何将奇偶校验位加到字母A和F的ASCII码上。注意，A的编码变成了101000001（奇偶校验位为1），F的ASCII码变成了001000110（奇偶校验位为0）。尽管A原始的8位模式有偶数个1，F原始的8位模式有奇数个1，但它们的9位模式都有奇数个1。如果将这种技术应用于所有的8位ASCII模式，我们就能够得到一个9位编码系统，其中任何一个9位模式有偶数个1就表示出错了。
上面描述的奇偶校验系统称为奇校验（odd parity），因为我们设计的系统中每个正确的模式都有奇数个1。另一种技术称为偶校验（even parity）。在偶校验系统中，每个模式都会被设计成包含偶数个1，因此，如果出现奇数个1，就表明出错了。
现在，在计算机的主存储器中使用奇偶校验位已经不是一件稀奇事了。尽管我们假设这些计算机存储单元是8位的，但事实上，它们可能是9位的，其中1位被用作奇偶校验位。每次存储器电路收到要存储的8位模式，都会先给其加上一个奇偶校验位，形成9位模式，然后再存储。稍后检索模式时，存储器电路会检查这个9位模式的奇偶性。如果检查没有发现差错，存储器会移除校验位，然后自信地返回余下的8位模式。否则，存储器会返回那8个数据位，并警告返回的模式可能与原本委托给存储器的模式不同。
图1-26 为奇校验调整的字母A和F的ASCII码
直接使用奇偶校验位很简单，不过它有局限性。如果一个模式最初有奇数个1，并出现了2次差错，那么它就仍然有奇数个1，这样校验系统就无法检测到这些差错。事实上，直接使用奇偶校验位并不能发现模式中的任何偶数个差错。
有时会对长位模式（如记录在磁盘扇区中的位串）应用一种方法来最大限度地减少这类问题。在这种情况下，模式都有一组奇偶校验位构成的校验字节（checkbyte）。校验字节中的每个位都是一个奇偶校验位，与散布在整个模式中的一组特殊位相联系。例如，一个奇偶校验位可能与该模式中从第一个位起的每个第8位相关联，而另一个与该模式中从第二位起的每个第8位相关联。用这种方式，更容易检测到集中在原始模式某个区域中的一些差错，因为这些差错会在一些奇偶校验位的范围内。这个校验字节概念的演变出了称为校验和（checksum）及循环冗余校验（cyclic redundancy check，CRC）的差错检测方案。
虽然使用奇偶校验位可以检测到差错，但是它不能提供纠正那个差错所需的信息。让很多人感到惊讶的是，居然有人设计出了既能够检测出差错又能够纠正差错的纠错码（error-correcting code）。毕竟，直觉告诉我们，如果不知道消息的内容就无法纠正接收到的消息中的差错，但图1-27展示了一个具有这种纠错特性的简单编码。
为了明白这个编码是如何运作的，我们先来定义汉明距离（Hamming distance），这个术语是根据R. W. Hamming的姓氏命名的，由于对20世纪40年代早期继电器缺乏可靠性的失望，他开始开创性地研究纠错码。两个位模式之间的汉明距离指的是这两个模式中不相同位的个数。例如，在图1-27的编码中，表示A和B的模式之间的汉明距离是4，而B和C之间的汉明距离是3。图1-27中的编码的重要特征是，任何两个模式之间的汉明距离至少是3。
如果图1-27所示的模式中某个位被修改了，差错就能被检测出来，因为结果不会是一个合法的模式。（我们必须至少改变任意一个模式的3个位，这个模式看起来才会像另一个合法模式。）而且，我们还能够指出原始模式是什么。毕竟，修改过的模式和其原始形式的汉明距离是1，而和其他任何合法模式的汉明距离至少是2。
因此，对最初用图1-27编码的消息解码，我们只需简单地对比每个接收到的模式和用此编码表示的模式，直到找到一个和接收到的模式之间的汉明距离是1的模式为止。我们将其视为正确的符号进行解码。例如，我们接收到位模式010100，并将其与编码中的模式相比，就会得到图1-28所示的表格。因此，我们得出结论，传输的字符一定是D，因为这是最接近的匹配。
图1-27 一个纠错码
图1-28 用图1-27中的编码对模式010100解码
通过观察可以发现，使用图1-27中的编码方法，每个模式我们最多能检测出2个差错、改正1个差错。如果我们能设计出一种编码，使每个模式和其他任何模式之间的汉明距离都至少是5，那么就能最多检测出4个差错、改正2个差错。当然，设计一种具有长汉明距离的编码并不是一件简单的事。事实上，它构成了数学分支的一部分，称为代数编码理论，它是线性代数和矩阵理论的子领域。
纠错技术被广泛用于提高计算设备的可靠性。例如，它们经常被用于大容量磁盘驱动器，以减少因磁盘表面瑕疵而损坏数据的可能性。此外，最初用于音频盘的CD格式与后来用于计算机数据存储的格式之间的主要差别是纠错的程度。CD-DA格式具有纠错功能，它能把差错率减少到2张CD中只有1个差错。这种格式非常适合于音频录制，但是对于用CD向客户交付软件的公司，若50%的盘有瑕疵是令人无法忍受的。因此，附加纠错功能被用在CD中来存储数据，将出错概率减少到20 000个盘中有1个出错。
1.10节问题与练习
1．下面的字节最初是用奇校验编码的。你知道它们中哪个有错误吗？
a．100101101 b．100000001 c．000000000 d．111000000 e．011111111
2．问题1中没发现错误的字节还会有错误吗？请解释你的答案。
3．如果将奇校验换成偶校验，那么问题1和问题2的答案又将如何？
4．通过在每一个字符编码的高位端加一个奇偶校验位，用带奇校验的ASCII码对下列语句编码。
a．“Stop!” Cheryl shouted.
b．Does 2 + 3 = 5?
5．用图1-27的纠错码解码下面的消息。
a．001111 100100 001100
b．010001 000000 001011
c．011010 110110 100000 011100
6．用长度为5的位模式，为字符A、B、C和D构造编码，使得任何两个模式之间的汉明距离至少是3。
（带*的题目涉及选学章节的内容。）
1．假设上输入为1，下输入为0，请确定下面每个电路的输出值。如果上输入为0，下输入为1呢？
2．a．下面这个电路做的是什么布尔运算？
b．下面这个电路做的是什么布尔运算？
*3．a．如果要从某个电子元件商店购买触发器电路，我们会发现它有一个额外的输入，称为反向器（flip）。当反向器的输入从0变成1时，输出将翻转状态（如果原来是0，现在就是1，反之亦然）。但是，当反向器的输入从1变为0时，什么都不会发生。虽然我们可能不知道这个电路完成这一行为的细节，但我们仍然可以将其用作其他电路的抽象工具。请考虑使用下面两个触发器的电路。如果在电路的输入端发送一个脉冲，下面的那个触发器将变换状态。但是，另一个触发器不会改变，因为其输入（这一输入是从非门的输出接收到的）从1变成了0。因此，这一电路现在的输出为0和1。在电路输入端发送第二个脉冲将翻转两个触发器的状态，并产生输出1和0。如果在电路输入端发送第三个脉冲，将会产生什么输出呢？发送第四个脉冲呢？
b．计算机中不同元件的活动一般是需要协调的。只需将脉冲信号（称为时钟）连接到类似a中的电路即可。额外的门（如图所示）以协同的方式发送信号到其他连接的电路。研究这一电路时，你应该能够确认这样一个事实，即在第1个、第5个、第9个……时钟脉冲下，输出端A将发送1。哪些时钟脉冲将使输出端B发送1？哪些时钟脉冲将使输出端C发送1？在第4个时钟脉冲下，哪个输出端的输出为1？
4．假设下面电路的两个输入都是1。请描述如果上输出暂时变为0，会发生什么。如果下输入暂时变为0，又会发生什么。用与非门重新绘制这个电路。
5．下面表格显示的是（采用十六进制记数法表示的）机器的主存储器某些单元的地址和内容。根据这个存储排列，按照下列指令，记录下这些存储单元的最终内容。
| 地 址 |
内 容 |
|---|---|
| 0x00 |
0xAB |
| 0x01 |
0x53 |
| 0x02 |
0xD6 |
| 0x03 |
0x02 |
步骤1：将地址为0x03的单元的内容移入地址为0x00的单元中。
步骤2：将值0x01移入地址为0x02的单元。
步骤3：将地址0x01中存储的值移入地址为0x03的单元。
6．如果每个单元地址都可以用2个十六进制数字表示，那么一台计算机的主存储器中可以有多少个单元？如果用4个十六进制数字呢？
7．什么位模式可以用下面的十六进制记数法表示？
a．0xCD b．0x67 c．0x9A
d．0xFF e．0x10
8．下列用十六进制记数法表示的位模式中，最高有效位的值是什么？
a．0x8F b．0xFF
c．0x6F d．0x1F
9．用十六进制记数法表示下面的位模式。
a．101000001010
b．110001111011
c．000010111110
10．假设一个数码相机的存储容量是256 MB。如果一张照片每行每列都有1024像素，而且每个像素需要3字节的存储空间，那么这个数码相机可以存储多少张这样的照片？
11．假设显示屏上的一张图片是由一个768行×1024列的像素矩阵表示的。如果每个像素的颜色需要用8位进行编码，并且亮度需要用另外8位进行编码，那么要保存整幅图片需要多少字节的存储单元？
12．a．指出主存储器优于磁盘存储器的两个优点。
b．指出磁盘存储器优于主存储器的两个优点。
13．假设你个人计算机上的120 GB的硬盘只剩下50 GB是空闲的，那么用CD备份硬盘上的所有资料是否合理？用DVD呢？
14．如果磁盘的每个扇区包含1024字节，而且每个字符用2字节的Unicode字符表示，那么存储一页文本（如50行，每行100个字符）需要多少扇区？
15．如果用ASCII码，那么存储一本400页、每页3500个字符的小说需要多少字节的存储空间？如果用2字节的Unicode字符又需要多少字节？
16．一个典型硬盘驱动器的转速为每秒3600转，那么它的等待时间是多少？
17．如果一个硬盘驱动器的转速为每秒360转，寻道时间是10 ms，那么它的平均存取时间是多少？
18．假设一个打字员每天打字24小时，每分钟打60个字，那么这个打字员要多久才能填满容量为640 MB的CD？假定一个单词由5个字符构成，每个字符需要1字节的存储空间。
19．下面是用ASCII编码的消息。内容是什么？
01010111 01101000 01100001 01110100
00100000 01100100 01101111 01100101
01110011 00100000 01101001 01110100
00100000 01110011 01100001 01111001
00111111
20．下面的消息是使用ASCII编码的，每个字符1字节，并用十六进制记数法表示出来。这条消息的内容是什么？
0x686578206E6F746174696F6E
21．用ASCII对下面的句子编码，每个字符1字节。
a．Does 100/5 = 20?
b．The total cost is $7.25.
22．将前面问题的答案用十六进制记数法表示出来。
23．列出整数8到18的二进制表示。
24．a．通过用ASCII表示2和3，写出数23。
b．用二进制表示写出数23。
25．什么值的二进制表示只有一个位为1？列出具有这个特性的最小的6个值的二进制表示。
*26．将下面的每个二进制表示转换成相应的十进制表示。
a．1111 b．0001 c．10101
d．1000 e．10011 f．000000
g．1001 h．10001 i．100001
j．11001 k．11010 l．11011
*27．将下面每个十进制表示转换成相应的二进制表示。
a．7 b．11 c．16
d．17 e．31
*28．将下面的每个余16表示转换成相应的十进制表示。
a．10001 b．10101 c．01101
d．01111 e．11111
*29．将下面的每个十进制表示转换成相应的余4表示。
a．0 b．3 c．-2
d．-1 e．2
*30．将下面的每个二进制补码表示转换成相应的十进制表示。
a．01111 b．10100 c．01100
d．10000 e．10110
*31．将下面的每个十进制表示转换成相应的二进制补码表示，其中每个值用7位表示。
a．13 b．-13 c．-1
d．0 e．16
*32．假定下面这些位串都是用二进制补码记数法表示的值，执行下面这些加法运算。指出哪一个加法的答案是由于溢出而不正确的。
a．00101+01000 b．11111+00001
c．01111+00001 d．10111+11010
e．11111 +11111 f．00111 +01100
*33．解答下面的每个问题：将这些值翻译成二进制补码记数法（用5位模式），把减法问题转换成相应的加法问题，并执行那个加法运算。将所得答案转换成十进制记数法进行验证。（观察溢出现象。）
a．5+1 b．5-1 c．12-5
d．8-7 e．12+5 f．5-11
*34．将下面的每个二进制表示转换成相应的十进制表示。
a．11.11 b．100.0101 c．0.1101
d．1.0 e．10.01
*35．用二进制记数法表示下面每个值。
a．
b．
c．
d．
e．
*36．用图1-24中描述的浮点格式对下面的位模式解码。
a．01011001 b．11001000 c．10101100
d．00111001
*37．用图1-24中描述的8位浮点格式对下面的值编码。指出出现截断误差的每个情形。
a．
b．
c．
d．
e．
*38．假定你不受使用标准化格式的限制，用图1-24中描述的浮点格式列出所有可以用于表示值的位模式。
*39．用图1-24中描述的8位浮点格式，求可以表示的最近似于2的平方根的值。如果机器利用这一浮点格式对这个数做平方，实际得到的值是什么？
*40．用图1-24所示的8位浮点格式可以表示的最近似于的值是什么？
*41．当用浮点记数法记录使用公制系统的度量时，误差是怎么产生的？例如，如果用米制单位记录110 cm会怎样？
*42．位模式01011和11011表示的是同一个值，一个是用余16记数法存储的，另一个是用二进制补码记数法存储的。
a．关于这个公共的值可以确定的是什么？
b．分别用二进制补码记数法和余码记数法存储同一个值，并且这两个系统采用相同的位模式长度，那么表示此值的这两种模式是一种什么关系？
*43．3个位模式10000010、01101000和00000010表示的是同一个值，采用的是3种不同的表示法：二进制补码记数法、余码记数法和图1-24所示的8位浮点格式。但这3个位模式和这3个表示法的顺序不一定是一一对应的。它们共同表示的那个值是什么？哪个模式对应哪个记数法？
*44．在下面的值中，哪一个不能用图1-24所示的浮点格式精确地表示？
a．
b．
c．9
d．
e．
*45．如果用于表示二进制整数的位串长度由4变成6，那么能够表示的最大整数的值会发生什么变化？用二进制补码记数法又将如何呢？
*46．如果一个4 MB的存储器每个单元可以存储1字节，那么其最大存储地址的十六进制表示是什么？
*47．如果使用LZW压缩，从只包含x、y和一个空格（如1.8节所述）的字典开始，对下列消息编码，结果是什么？
xxy yyx xxy xxy yyx
*48．下面的消息是使用LZW压缩的，其字典的第一、第二、第三个条目分别是x、y和空格。这条消息的解压缩结果是什么？
22123113431213536
*49．如果消息
xxy yyx xxy xxyy
是用LZW压缩的，并且最初字典的第一、第二、第三个条目分别是x、y和空格，那么最后的字典里有哪些条目？
*50．我们将在第2章学到，通过传统电话系统传输位的一种方法：首先将位模式转换成声音，然后通过电话线传输声音，最后再将声音转换回位模式。这种技术的传输速率最高可达57.6 Kbit/s。如果视频采用MPEG压缩，那么这种技术能否满足远程会议的需要？
*51．使用ASCII对下面的句子编码，使用偶校验，在每个字符编码的高位端添加一个奇偶校验位。
a．Does 100/5 = 20?
b．The total cost is $7.25.
*52．下面的消息的每个短位串最初都是用奇校验传输的。哪一个位串肯定会出现差错？
11001 11011 10110 00000 11111
10001 10101 00100 01110
*53．假如一个24位的编码是这样产生的：将一个符号的ASCII表示连续复制3次，用得到的结果表示该符号（例如，符号A用位串010000010100000101000001
表示）。这个新编码有哪些纠错特性？
*54．用图1-28的纠错码对下面的词语进行解码。
a．111010 110110
b．101000 100110 001100
c．011101 000110 000000 010100
d．010010 001000 001110 101111
000000 110111 100110
e．010011 000000 101001 100110
*55．国际货币汇率变化很频繁。研究一下货币汇率，并相应地更新1.8节的货币转换器脚本。
*56．找出一种1.8节的那个货币转换器里没有的货币。得到它的当前汇率，并在网络上找到它的Unicode货币符号。扩展货币转换器脚本，让它能够转换这种新货币。
*57．如果你的网络浏览器和文本编辑器能很好地支持Unicode和UTF-8，那么请把实际的国际货币符号复制/粘贴到1.8节的转换器脚本中，替换掉'\u00A3'这样的复杂代码。（如果你的软件处理Unicode有困难，那么当你尝试这样做时，你的文本编辑器里可能会出现奇怪的符号。）
*58．1.8节的货币转换器脚本在执行每个乘法之前，用变量dollars存储了要转换的金额。这使得脚本中每个乘法代码行的长度，比直接键入整数数量1000的长度要长。提前创建这个额外的变量有什么好处？
*59．编写并测试一个Python脚本，给定一个字节数，输出与其相等的千字节数、兆字节数、吉字节数和太字节数。再编写并测试一个互补脚本，给定一个太字节数，输出与其相等的GB数、MB数、KB数以及字节数。
*60．编写并测试一个Python脚本，给定一个录音的分秒数，计算对这个时长的未压缩的CD品质的立体声音频数据进行编码所用的位数。（复习1.4节的必要参数和公式。）
*61．指出下面Python脚本中的错误。
days_per_week = 7
weeks_per_year = 52
days_per_year = days_per_week **
weeks_per_year
PRINT(days_per_year)希望下面的问题能引导读者思考一些与计算领域相关的道德、社会和法律问题。回答出这些问题还不够，还应该考虑为什么这样回答，以及你的判断是否对每个问题都标准如一。
1．某个截断误差出现在一个关键时刻，引起了巨大的损失和人身伤亡。如果需要有人对此负责，那么是谁？是硬件设计者？软件设计者？实际编写那段程序的程序员？还是决定在那个特定应用中使用这个软件的人？如果最初开发这个软件的公司已经修正过这个软件，但是用户没有为那个关键应用购买并应用这个升级版，又将如何？如果这个软件是盗版的呢？
2．对个人来讲，在开发他自己的应用时忽略截断误差的可能性以及它们的后果，是可以接受的吗？
3．20世纪70年代开发的软件只用2个数字表示年（如用76表示1976年），忽视了这个软件在即将到来的世纪之交会有缺陷这个事实，这道德吗？若现在只用3个数字表示年（如用982表示1982年，用015表示2015年）又是否道德呢？如果只用4个数字呢？
4．许多人认为，对信息进行编码经常会削弱或歪曲该信息，因为这实质上迫使信息必须被量化。他们认为，若一份调查问卷要求调查对象只能用给定的5个等级来发表他们的意见，那么这份问卷本身就是有缺陷的。信息可以量化到什么程度？垃圾处理场选址的利弊可以量化吗？关于核能源及核废料的辩论是可量化的吗？将结论建立在平均值和其他统计分析上的做法危险吗？如果新闻通讯社在报道调查结果时不使用问题的准确措辞，这道德吗？能够量化一个人的生命值吗？一家公司在明知附加投资可以减少产品使用的危险性的情况下，仍然停止产品的改进投资，这是可以接受的吗？
5．收集和散发数据的权利是否应该根据数据形式的不同而有所差别？也就是说，收集和散发照片、音频或者视频的权利是否应该与收集和散发文本的一样？
6．无论是有意的还是无意的，记者的报道中通常都会反映出记者本人的偏见。一般只要改几个词语，一个故事就可能被赋予正面或负面的含义。（比较“大多数受访者都反对公民投票。”与“受访者中有相当一部分支持公民投票。”）修改一个故事（删掉某些观点或者仔细选词）和修改一张照片有区别吗？
7．假设数据压缩系统的使用会导致一些微小但重要的信息项的丢失。这会产生什么样的责任问题？应该如何解决？
Drew, M. and Z. Li. Fundamentals of Multimedia, 2nd ed. Cham, Switzerland: Springer, 2014.
Halsall, F. Multimedia Communications. Boston, MA: Addison-Wesley, 2001.
Hamacher, V. C., Z. G. Vranesic, S. G. Zaky, and N. Manjikian. Computer Organization and Embedded Systems, 6th ed. New York, NY: McGraw-Hill, 2011.
Knuth, D. E. The Art of Computer Programming, Vol. 2, 3rd ed. Boston, MA: Addison-Wesley, 1998.
Long, B. Complete Digital Photography, 8th ed. Boston, MA: Cengage Learning, 2015.
Miano, J. Compressed Image File Formats. New York: ACM Press, 1999.
Petzold, C. CODE: The Hidden Language of Computer Hardware and Software. Redman, WA: Microsoft Press, 2000.
Saloman, D., and G. Motta. Handbook of Data Compression, 5th ed. London, England: Springer, 2010.
Sayood, K. Introduction to Data Compression, 5th ed. Cambridge, MA: Morgan Kaufmann, 2017.
微信扫码关注【异步社区】微信公众号，回复“e58263”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
