VIP会员

本书适合程序库、编译器开发者及追求优美程序设计的人员阅读，适合用作计算机专业高年级学生及研究生的参考用书。 本书直观明了地讲述了计算机算术的更深层次的、更隐秘的技术，汇集了各种编程小技巧，包括常见任务的小算法、2的幂边界和边界检测、位和字节的重排列、整数除法和常量除法、针对整数的基本函数、Gray码、Hilbert空间填充曲线、素数公式等。 Henry S．Warren，Jr．在IBM任职四十余年，经历了从IBM 704时代到PowerPC时代的变化。他曾在纽约大学在Jack Schwartz领导下从事各种军事指令／控制系统和SETL项目的开发。1973年起，他开始在IBM从事研究工作，致力于编译器和计算机体系结构的研究。他目前从事蓝基因千万亿浮点计算机项目。他拥有纽约大学库朗研究院计算机科学博士学位。 译者序 文艺复兴以降，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的各个领域取得了垄断性的优势；也正是这样的传统，使美国在信息技术发展的六十多年间名家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅擘划了研究的范畴，还揭橥了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会因年月的流逝而减退。 近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略上显得举足轻重。在我国信息技术发展时间较短、从业人员较少的现状下，美国等发达国家在其计算机科学发展的几十年间积淀的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计算机教材将对我国计算机教育事业的发展起积极的推动作用，也是与世界接轨、建设真正的世界一流大学的必由之路。 机械工业出版社华章图文信息有限公司较早意识到“出版要为教育服务”。自1998年开始，华章公司就将工作重点放在了遴选、移译国外优秀教材上。经过几年的不懈努力，我们与Prentice Hall，Addison-Wesley，McGraw-Hill，Morgan Kaufmann等世界著名出版公司建立了良好的合作关系，从它们现有的数百种教材中甄选出Tanenbaum，Stroustrup，Kernighan，Jim Gray等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者学习、研究及庋藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。 “计算机科学丛书”的出版工作得到了国内外学者的鼎力襄助，国内的专家不仅提供了中肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品在中国的传播，有的还专诚为其书的中译本作序。迄今，“计算机科学丛书”已经出版了近百个品种，这些书籍在读者中树立了良好的口碑，并被许多高校采用为正式教材和参考书籍，为进一步推广与发展打下了坚实的基础。 随着学科建设的初步完善和教材改革的逐渐深化，教育界对国外计算机教材的需求和应用都步入一个新的阶段。为此，华章公司将加大引进教材的力度，在“华章教育”的总规划之下出版三个系列的计算机教材：除“计算机科学丛书”之外，对影印版的教材，则单独开辟出“经典原版书库”；同时，引进全美通行的教学辅导书“Schaum’s Outlines”系列组成“全美经典学习指导系列”。为了保证这三套丛书的权威性，同时也为了更好地为学校和老师们服务，华章公司聘请了中国科学院、北京大学、清华大学、国防科技大学、复旦大学、上海交通大学、南京大学、浙江大学、中国科技大学、哈尔滨工业大学、西安交通大学、中国人民大学、北京航空航天大学、北京邮电大学、中山大学、解放军理工大学、郑州大学、湖北工学院、中国国家信息安全测评认证中心等国内重点大学和科研机构在计算机的各个领域的著名学者组成“专家指导委员会”，为我们提供选题意见和出版监督。 这三套丛书是响应教育部提出的使用外版教材的号召，为国内高校的计算机及相关专业的教学度身订造的。其中许多教材均已为M．I．T. ，Stanford，U．C．Berkeley，C. M．U．等世界名牌大学所采用。不仅涵盖了程序设计、数据结构、操作系统、计算机体系结构、数据库、编译原理、软件工程、图形学、通信与网络、离散数学等国内大学计算机专业普遍开设的核心课程，而且各具特色——有的出自语言设计者之手、有的历经三十年而不衰、有的已被全世界的几百所高校采用。在这些圆熟通博的名师大作的指引之下，读者必将在计算机科学的宫殿中由登堂而入室。 本书也许会激起某些读者的怀旧情感，特别是那些经历过或曾向往在早期的Z80等计算机上用汇编语言或Basic语言编程的人们；那些竭尽全力、苦思冥想，仅仅是为了能够写出更简短、更高效程序的人们；那些以编写一行高效Basic程序而自我陶醉的人们。 IBM资深程序员、蓝基因千万亿浮点计算机项目参与者Henry S．Warren，Jr.给所有程序员带来一本他们到处寻觅、实实在在、具有现实意义的程序设计技巧指南。本书是一本有特色的算法参考书，它不像现今多数算法书那样讨论大型的程序设计技术和系统的程序设计方法，而是向读者展示了计算机代码与指令，以及指令间的令人惊叹的内在关联，并通过这样的内在关联向读者揭示计算机运行的某些奥秘，揭示通过这样的关联更有效地实现基本操作的精湛技巧，以及这些技巧在优化编译器、图形学、密码学乃至数学中的应用。 本书适用于那些想要编写及欣赏巧妙、高效代码的读者，特别适合于希望把计算机软件和硬件有机地结合在一起的读者。本书值得每一位认真的计算机硬件设计者，每一位希望编写高效、优雅的嵌入式程序、编译器及优化编译器的设计者，以及每一位希望提高程序设计技艺的读者仔细斟酌和品味。 为了方便我国读者，我们尽量以通俗的语言翻译原文，并对难以理解的部分适当做了补充说明。翻译过程中译者得到机械工业出版社华章分社的大力支持。由于本书覆盖的内容较广，翻译时间仓促、水平有限，难免有疏漏与错误之处，请读者不吝指教。 冯 速 北京师范大学 前言 用户注意：软件维护成本的增加与程序设计人员的创造力的平方成正比。“程序员创造力第一法则”，Robert D．Bliss，1992 本书是我多年来所收集的程序设计小技巧的集成，它们大部分只能应用于以2的补码的形式表示整数的计算机上。尽管当这些技巧与寄存器的长度相关时，我们假设机器是32位的，但是我们很容易将这些技巧运用到其他寄存器长度的计算机上。 本书不涉及大型的编程技巧，例如高级排序技术和编译器优化技术等；相反，它所讨论的是诸如计算一个字中值为1的位的数目这样的与计算机的字或指令相关的小技巧，这样的技巧通常是算术指令和逻辑指令的混合物。 本书自始至终都假设整数溢出中断被屏蔽，所以不会发生溢出中断。C语言、Fortran语言、Java语言运行在这样的环境下，但是Pascal语言和ADA语言的用户则要小心。 本书的描述是非形式化的。只有当算法不是显然的时才给出证明(有些也不证明)。我们使用计算机算术、“地板”函数、算术和逻辑操作的混合等来描述这些小技巧。在这些领域，证明通常相当困难并且难以表述。 为了减少印刷错误和疏忽，我们实际运行了很多算法。因此，尽管每一种计算机语言都有不尽人意的一面，但我们还是使用程序设计语言给出了这些算法。由于C语言的高知名度，我们把它作为高级语言使用，它既允许整数操作，也允许位串操作，并且我们有产生高质量目标代码的C编译器。 偶尔我们也使用机器语言。它使用三地址格式，主要是为了可读性。我们使用的汇编语言是RISC虚拟计算机的汇编语言。 我们尽量使用无分支代码。因为在许多机器上，分支会减慢指令提取，抑制指令的并行执行。分支的另一个问题是它们可能会抑制编译器的优化，例如指令调度、指令公用以及寄存器分配。也就是说，编译器可能会更有效地优化由若干大的基本块组成的程序，而对于由许多小基本块组成的程序进行优化的效果则可能不显著。 代码序列中也常出现小的立即值、与零的比较(而不是与其他数相比较)以及指令级的并行。尽管通过(从内存)查表可以使大部分代码更简洁，但本书不常提及查表法。这是因为相对于算术指令，其装入的代价越来越大，而且查表法通常不是很有趣(尽管它们通常很实用)。当然也有例外的情况。 最后，我要说明的是，书名中的“HACKER”一词指的是计算机狂热爱好者——是一些喜欢使用计算机做新鲜事或用更新更聪明的方法做一些旧事情的人。这些计算机狂热爱好者们通常技艺高超，但很可能并非专业的计算机程序员或程序设计者。他们的工作也许很有用，也许仅仅是一种游戏。不少坚定的计算机迷们写出这样的程序，在执行这个程序时它会生成自己的一份拷贝。这就是我们通常所说的电脑黑客。如果你是在找如何侵入他人电脑的技巧的话，在本书中是找不到的。 H．S．Warren，Jr． 约克镇，纽约 序言回到顶部↑大约30年前，当我第一次在麻省理工学院的MAC项目中得到一份暑期工作时，我为能够使用DEC PDP-10计算机而兴奋不已。毫无疑问，在这类计算机上使用汇编语言编程比在其他计算机上更有趣，因为它具有完成位测试、位屏蔽、字段操作和整数操作所需的丰富易用的指令集。尽管PDP-10计算机已停产多年，但它仍拥有不少狂热的推崇者，他们仍然运行着PDP-10的硬件和软件，他们使用个人计算机模拟它的指令集，运行它的操作系统和相关的应用程序。他们甚至编写新软件；现在，至少有一家网站是用PDP-10的模拟器来维护网页的 (不要笑，这并不比使陈旧的汽车跑起来更愚蠢)。 就是在这时，在1972年的夏天，我有幸看到了麻省理工学院被称为HAKMEM的最新研究备忘录，这是一本奇妙而不拘一格的技术小文集。这些课题的内容涉及到电路、数论等广泛领域。而其中最令我感兴趣的是那些具有独创性的编程小技巧一览表。这些小技巧通常描述一些漂亮而与众不同的对整数和位串的操作(例如计算一个字中值为1的位的数目)，这些操作原本是使用长长的机器指令序列或循环来实现的，而这些小技巧展示了如何仅用两三个精心筛选的指令就能更聪明地完成同样工作；同时探索、揭示出这些指令间的相互关系。 我犹如吃玉米花一样，而不是像吃糖果那样，如饥似渴地阅读这些编程小珍宝——这些小技巧 充满着华美，充满着智慧，充满着诗一般的优雅。 我想，“一定是这样的，还有许多这样的小技巧。”多年来我的确收集了许多，也发现了一些。“应该把它们写成一本书。” 当我看到Hank Warren的手稿时真是欣喜若狂。他系统地收集了许多编程小技巧，对它们分门别类，并做了详尽的解释。虽然有一些小技巧是用机器指令的形式描述的，但这本书不仅仅适用于汇编语言程序员。本书论述计算机整数和位串的基本结构关系，给出对它们进行有效操作的高效技术。这些技术对C语言和Java语言同样有用。 许多关于算法和数据结构的书籍对于排序和搜索、维护散列表和二叉树、记录和指针的处理讲了许多非常复杂的技巧，但它们忽视了微小的数据块——位和位数组——所能完成的工作。仅仅使用二进制加法、减法和按位操作就可以完成的工作令人惊讶；进位链使一个位可以对它左边的所有位产生影响，这一事实使加法操作成为一个非常强大的数据处理操作，而对此我们没有给予足够的认识。 是的，应该有一本关于这些技巧的书。现在，它就在你的手中，它非常神奇。如果你要编写最优化编译器或者高性能的代码，就必须阅读这本书。也许不是每天都能用上这些技巧，但是如果发现自己某一天陷入了困境，似乎需要按一个字中的位做循环操作，或者需要对整数进行操作而觉得难以编码，或者真的需要让整数计算或位计算的内循环速度成倍提高，这时就需要查看这些小技巧。当然也可能纯粹是为了欣赏而读这本书。 Guy L．Steele，Jr． 马萨诸塞州，柏灵顿 第1章 介绍 1．1 记法 1．2 指令集和运行时间模型 第2章 基础 2．1 操作最右侧位 2．2 结合逻辑操作的加运算 2．3 逻辑和算术表达式中的不等式 2．4 绝对值函数 2．5 符号扩展 2．6 用无符号右移位实现带符号右移位 2．7 符号函数 2．8 三值比较函数 2．9 符号传递 2．10 对"0意味着2"字段的解码 2．11 比较谓词 2．12 溢出检测 2．13 加、减、乘的特征码结果 2．14 循环移位 2．15 双字长加、减法 2．16 双字长移位 .2．17 多字节加、减、绝对值 2．18 doz、max、min函数 2．19 交换寄存器 2．20 两个或更多值之间的交换 第3章 2的幂边界 3．1 上舍入、下舍入到已知的2的幂的倍数 3．2 上舍入、下舍入到下一个2的幂 3．3 检测2的幂的边界跨越 第4章 算术边界 4．1 整数的边界检测 4．2 通过加和减传播边界 4．3 逻辑操作的边界传播 第5章 位计数 5．1 1位计数 5．2 奇偶性 5．3 前导0计数 5．4 后缀0计数 第6章 字搜索 6．1 寻找第一个0字节 6．2 寻找第一个给定长度的1位串 第7章 位和字节的重排列 7．1 位和字节的反转 7．2 混洗位 7．3 转置位矩阵 7．4 压缩或广义提取 7．5 一般置换，分羊操作 7．6 重排列和索引变换 第8章 乘法 8．1 多字乘法 8．2 64位积的高阶位部分 8．3 无符号积高阶位与带符号积高阶位间的转换 8．4 常量乘法 第9章 整数除法 9．1 预备知识 9．2 多字除法 9．3 从带符号除法到无符号短除法 9．4 无符号长除法 第10章 整数常量除法 10．1 除以一个2的已知幂的带符号除法 10．2 除以一个2的已知幂的除法的带符号余数 10．3 非2的幂的带符号除法和余数 10．4 除数≥2的带符号除法 10．5 除数≤-2的带符号除法 10．6 并入编译器 10．7 其他主题 10．8 无符号除法 10．9 除数≥1的无符号除法 10．10 并入编译器(无符号) 10．11 其他论题(无符号) 10．12 模除法和地板除法的适用性问题 10．13 类似的方法 10．14 魔术数示例 10．15 除以常数的精确除法 10．16 除以常数的除法的零余数检测 第11章 初等函数 11．1 整数平方根 11．2 整数的立方根 11．3 整数求幂 11．4 整数对数 第12章 数制中的特殊底 12．1 以-2为底 12．2 以-1+i为底 12．3 其他底 12．4 最有效的底是什么 第13章 Gray码 13．1 Gray码 13．2 递增Gray码整数 13．3 负二进制Gray码 13．4 简史及应用 第14章 Hilbert曲线 14．1 生成Hilbert曲线的递归算法 14．2 从Hilbert曲线的路长求坐标 14．3 Hilbert曲线上坐标到路长的转换 14．4 递增Hilbert曲线上点的坐标 14．5 非递归生成算法 14．6 其他空间填充曲线 14．7 应用 第15章 浮点 15．1 IEEE格式 15．2 利用整数操作进行浮点数比较 15．3 前导数字分布 15．4 各种各样的值的列表 第16章 素数公式 16．1 介绍 16．2 Willans公式 16．3 Wormell公式 16．4 求其他比较麻烦的函数的公式 附录A 四位计算机的算术表 附录B 牛顿方法 参考文献 索引