高效程序的奥秘.PDF 中文版

本书也许会激起某些读者的怀旧情感，特别是那些经历过或曾向往在早期的Z80等计算机上用汇编语言或Basic语言编程的人们；那些竭尽全力、苦思冥想，仅仅是为了能够写出更简短、更高效程序的人们；那些以编写一行高效Basic程序而自我陶醉的人们。 本书适用于那些想要编写及欣赏巧妙、高效代码的读者，特别适合于希望把计算机软件和硬件有机地结合在一起的读者。本书值得每一位认真的计算机硬件设计者，每一位希望编写高效、优雅的嵌入式程序、编译器及优化编译器的设计者，以及每一位希望提高程序设计技艺的读者仔细斟酌和品味。 为了减少印刷错误和疏忽，我们实际运行了很多算法。因此，尽管每一种计算机语言都有不尽人意的一面，但我们还是使用程序设计语言给出了这些算法。由于C语言的高知名度，我们把它作为高级语言使用，它既允许整数操作，也允许位串操作，并且我们有产生高质量目标代码的C编译器。 偶尔我们也使用机器语言。它使用三地址格式，主要是为了可读性。我们使用的汇编语言是RISC虚拟计算机的汇编语言。 本书是我多年来所收集的程序设计小技巧的集成，它们大部分只能应用于以2的补码的形式表示整数的计算机上。尽管当这些技巧与寄存器的长度相关时，我们假设机器是32位的，但是我们很容易将这些技巧运用到其他寄存器长度的计算机上。 我们尽量使用无分支代码。因为在许多机器上，分支会减慢指令提取，抑制指令的并行执行。分支的另一个问题是它们可能会抑制编译器的优化，例如指令调度、指令公用以及寄存器分配。也就是说，编译器可能会更有效地优化由若干大的基本块组成的程序，而对于由许多小基本块组成的程序进行优化的效果则可能不显著。 本书不涉及大型的编程技巧，例如高级排序技术和编译器优化技术等；相反，它所讨论的是诸如计算一个字中值为1的位的数目这样的与计算机的字或指令相关的小技巧，这样的技巧通常是算术指令和逻辑指令的混合物。 本书自始至终都假设整数溢出中断被屏蔽，所以不会发生溢出中断。C语言、Fortran语言、Java语言运行在这样的环境下，但是Pascal语言和ADA语言的用户则要小心。 本书的描述是非形式化的。只有当算法不是显然的时才给出证明(有些也不证明)。我们使用计算机算术、“地板”函数、算术和逻辑操作的混合等来描述这些小技巧。在这些领域，证明通常相当困难并且难以表述。 代码序列中也常出现小的立即值、与零的比较(而不是与其他数相比较)以及指令级的并行。尽管通过(从内存)查表可以使大部分代码更简洁，但本书不常提及查表法。这是因为相对于算术指令，其装入的代价越来越大，而且查表法通常不是很有趣(尽管它们通常很实用)。当然也有例外的情况。 IBM资深程序员、蓝基因千万亿浮点计算机项目参与者Henry S．Warren，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 牛顿方法 参考文献 索引