本书适合程序库、编译器开发者及追求优美程序设计的人员阅读，适合用作计算机专业高年级学生及研究生的参考用书。
　　本书直观明了地讲述了计算机算术的更深层次的更隐秘的技术，汇集了各种编程小技巧，包括常见任务的小算法、2的幂边界和边界检测、位和字节的重排列、整数除法和常量除法、针对整数的基本函数、Gray码、Hilbert空间填充曲线、素数公式等。

无

用户注意：软件维护成本的增加与程序设计人员的创造力的平方成正比。
　　“程序员创造力第一法则”，Robert D. Bliss, 1992

　　本书是我多年来所收集的程序设计小技巧的集成，它们大部分只能应用于以2的补码的形式表示整数的计算机上。尽管当这些技巧与寄存器的长度相关时，我们假设机器是32位的，但是我们很容易将这些技巧运用到其他寄存器长度的计算机上。
　　本书不涉及大型的编程技巧，例如高级排序技术和编译器优化技术等；相反，它所讨论的是诸如计算一个字中值为1的位的数目这样的与计算机的字或指令相关的小技巧，这样的技巧通常是算术指令和逻辑指令的混合物。
　　本书自始至终都假设整数溢出中断被屏蔽，所以不会发生溢出中断。C语言、Fortran语言、Java语言运行在这样的环境下，但是Pascal语言和ADA语言的用户则要小心。
　　本书的描述是非形式化的。只有当算法不是显然的时才给出证明（有些也不证明）。我们使用计算机算术、“地板”函数、算术和逻辑操作的混合等来描述这些小技巧。在这些领域，证明通常相当困难并且难以表述。
　　为了减少印刷错误和疏忽，我们实际运行了很多算法。因此，尽管每一种计算机语言都有不尽人意的一面，但我们还是使用程序设计语言给出了这些算法。由于C语言的高知名度，我们把它作为高级语言使用，它既允许整数操作，也允许位串操作，并且我们有产生高质量目标代码的C编译器。
　　偶尔我们也使用机器语言。它使用三地址格式，主要是为了可读性。我们使用的汇编语言是RISC虚拟计算机的汇编语言。
　　我们尽量使用无分支代码。因为在许多机器上，分支会减慢指令提取，抑制指令的并行执行。分支的另一个问题是它们可能会抑制编译器的优化，例如指令调度、指令公用以及寄存器分配。也就是说，编译器可能会更有效地优化由若干大的基本块组成的程序，而对于由许多小基本块组成的程序进行优化的效果则可能不显著。
　　代码序列中也常出现小的立即值、与零的比较（而不是与其他数相比较）以及指令级的并行。尽管通过（从内存）查表可以使大部分代码更简洁，但本书不常提及查表法。这是因为相对于算术指令，其装入的代价越来越大，而且查表法通常不是很有趣（尽管它们通常很实用）。当然也有例外的情况。
　　最后，我要说明的是，书名中的“HACKER”一词指的是计算机狂热爱好者—是一些喜欢使用计算机做新鲜事或用更新更聪明的方法做一些旧事情的人。这些计算机狂热爱好者们通常技艺高超，但很可能并非专业的计算机程序员或程序设计者。他们的工作也许很有用，也许仅仅是一种游戏。不少坚定的计算机迷们写出这样的程序，在执行这个程序时它会生成自己的一份拷贝。这就是我们通常所说的电脑黑客。如果你是在找如何侵入他人电脑的技巧的话，在本书中是找不到的。

H. S. Warren, Jr.
约克镇，纽约
2002年2月

大约30年前，当我第一次在麻省理工学院的MAC项目中得到一份暑期工作时，我为能够使用DEC PDP-10计算机而兴奋不已。毫无疑问，在这类计算机上使用汇编语言编程比在其他计算机上更有趣，因为它具有完成位测试、位屏蔽、字段操作和整数操作所需的丰富易用的指令集。尽管PDP-10计算机已停产多年，但它仍拥有不少狂热的推崇者，他们仍然运行着PDP-10的硬件和软件，他们使用个人计算机模拟它的指令集，运行它的操作系统和相关的应用程序。他们甚至编写新软件；现在，至少有一家网站是用PDP-10的模拟器来维护网页的（不要笑，这并不比使陈旧的汽车跑起来更愚蠢）。
　　就是在这时，在1972年的夏天，我有幸看到了麻省理工学院被称为HAKMEM的最新研究备忘录，这是一本奇妙而不拘一格的技术小文集。这些课题的内容涉及到电路、数论等广泛领域。而其中最令我感兴趣的是那些具有独创性的编程小技巧一览表。这些小技巧通常描述一些漂亮而与众不同的对整数和位串的操作（例如计算一个字中值为1的位的数目），这些操作原本是使用长长的机器指令序列或循环来实现的，而这些小技巧展示了如何仅用两三个精心筛选的指令就能更聪明地完成同样工作；同时探索、揭示出这些指令间的相互关系。我犹如吃玉米花一样，而不是像吃糖果那样，如饥似渴地阅读这些编程小珍宝—这些小技巧充满着华美，充满着智慧，充满着诗一般的优雅。我想，“一定是这样的，还有许多这样的小技巧。”多年来我的确收集了许多，也发现了一些。“应该把它们写成一本书。”
　　当我看到Hank Warren的手稿时真是欣喜若狂。他系统地收集了许多编程小技巧，对它们分门别类，并做了详尽的解释。虽然有一些小技巧是用机器指令的形式描述的，但这本书不仅仅适用于汇编语言程序员。本书论述计算机整数和位串的基本结构关系，给出对它们进行有效操作的高效技术。这些技术对C语言和Java语言同样有用。
　　许多关于算法和数据结构的书籍对于排序和搜索、维护散列表和二叉树、记录和指针的处理讲了许多非常复杂的技巧，但它们忽视了微小的数据块—位和位数组—所能完成的工作。仅仅使用二进制加法、减法和按位操作就可以完成的工作令人惊讶；进位链使一个位可以对它左边的所有位产生影响，这一事实使加法操作成为一个非常强大的数据处理操作，而对此我们没有给予足够的认识。
　　是的，应该有一本关于这些技巧的书。现在，它就在你的手中，它非常神奇。如果你要编写最优化编译器或者高性能的代码，就必须阅读这本书。也许不是每天都能用上这些技巧，但是如果发现自己某一天陷入了困境，似乎需要按一个字中的位做循环操作，或者需要对整数进行操作而觉得难以编码，或者真的需要让整数计算或位计算的内循环速度成倍提高，这时就需要查看这些小技巧。当然也可能纯粹是为了欣赏而读这本书。

Guy L. Steele, Jr.
马萨诸塞州，柏灵顿
2002年4月

(美)Henry S.Warren,Jr.：Henry S.Warren,Jr.: Henry S. Warren, Jr.在IBM任职四十余年，经历了从IBM 704时代到PowerPC时代的变化。他曾在纽约大学在Jack Schwartz领导下从事各种军事指令/控制系统和SETL项目的开发。1973年起，他开始在IBM从事研究工作，致力于编译器和计算机体系结构的研究。他目前从事蓝基因千万亿浮点计算机项目。他拥有纽约大学库朗研究院计算机科学博士学位。

冯速：暂无简介

本书也许会激起某些读者的怀旧情感，特别是那些经历过或曾向往在早期的Z80等计算机上用汇编语言或Basic语言编程的人们；那些竭尽全力、苦思冥想，仅仅是为了能够写出更简短、更高效程序的人们；那些以编写一行高效Basic程序而自我陶醉的人们。
　　IBM资深程序员、蓝基因千万亿浮点计算机项目参与者Henry S. Warren，Jr.给所有程序员带来一本他们到处寻觅、实实在在、具有现实意义的程序设计技巧指南。本书是一本有特色的算法参考书，它不像现今多数算法书那样讨论大型的程序设计技术和系统的程序设计方法，而是向读者展示了计算机代码与指令，以及指令间的令人惊叹的内在关联，并通过这样的内在关联向读者揭示计算机运行的某些奥秘，揭示通过这样的关联更有效地实现基本操作的精湛技巧，以及这些技巧在优化编译器、图形学、密码学乃至数学中的应用。
　　本书适用于那些想要编写及欣赏巧妙、高效代码的读者，特别适合于希望把计算机软件和硬件有机地结合在一起的读者。本书值得每一位认真的计算机硬件设计者，每一位希望编写高效、优雅的嵌入式程序、编译器及优化编译器的设计者，以及每一位希望提高程序设计技艺的读者仔细斟酌和品味。
　　为了方便我国读者，我们尽量以通俗的语言翻译原文，并对难以理解的部分适当做了补充说明。翻译过程中译者得到机械工业出版社华章分社的大力支持。由于本书覆盖的内容较广，翻译时间仓促、水平有限，难免有疏漏与错误之处，请读者不吝指教。

冯　 速
2003年12月
于北京师范大学

第1章　 介绍 1
1.1　 记法 1
1.2　 指令集和运行时间模型 3
第2章　 基础 9
2.1　 操作最右侧位 9
2.2　 结合逻辑操作的加运算 12
2.3　 逻辑和算术表达式中的不等式 13
2.4　 绝对值函数 14
2.5　 符号扩展 14
2.6　 用无符号右移位实现带符号右移位 14
2.7　 符号函数 15
2.8　 三值比较函数 15
2.9　 符号传递 16
2.10　 对“0意味着2n”字段的解码 16
2.11　 比较谓词 16
2.12　 溢出检测 20
2.13　 加、减、乘的特征码结果 25
2.14　 循环移位 26
2.15　 双字长加、减法 26
2.16　 双字长移位 27
2.17　 多字节加、减、绝对值 28
2.18　 doz、max、min函数 29
2.19　 交换寄存器 30
2.20　 两个或更多值之间的交换 32
第3章　 2的幂边界 35
3.1　 上舍入、下舍入到已知的2的幂的倍数 35
3.2　 上舍入、下舍入到下一个2的幂 35
3.3　 检测2的幂的边界跨越 38
第4章　 算术边界 41
4.1　 整数的边界检测 41
4.2　 通过加和减传播边界 43
4.3　 逻辑操作的边界传播 46
第5章　 位计数 51
5.1　 1位计数 51
5.2　 奇偶性 58
5.3　 前导0计数 60
5.4　 后缀0计数 65
第6章　 字搜索 71
6.1　 寻找第一个0字节 71
6.2　 寻找第一个给定长度的1位串 75
第7章　 位和字节的重排列 79
7.1　 位和字节的反转 79
7.2　 混洗位 82
7.3　 转置位矩阵 84
7.4　 压缩或广义提取 90
7.5　 一般置换，分羊操作 95
7.6　 重排列和索引变换 98
第8章　 乘法 99
8.1　 多字乘法 99
8.2　 64位积的高阶位部分 101
8.3　 无符号积高阶位与带符号积高阶位间的转换 101
8.4　 常量乘法 102
第9章　 整数除法 105
9.1　 预备知识 105
9.2　 多字除法 107
9.3　 从带符号除法到无符号短除法 111
9.4　 无符号长除法 113
第10章　 整数常量除法 119
10.1　 除以一个2的已知幂的带符号除法 119
10.2　 除以一个2的已知幂的除法的带符号余数 120
10.3　 非2的幂的带符号除法和余数 121
10.4　 除数≥2的带符号除法 123
10.5　 除数≤-2的带符号除法 129
10.6　 并入编译器 131
10.7　 其他主题 133
10.8　 无符号除法 136
10.9　 除数≥1的无符号除法 138
10.10　 并入编译器（无符号） 140
10.11　 其他论题（无符号） 140
10.12　 模除法和地板除法的适用性问题 143
10.13　 类似的方法 144
10.14　 魔术数示例 145
10.15　 除以常数的精确除法 146
10.16　 除以常数的除法的零余数检测 151
第11章　 初等函数 155
11.1　 整数平方根 155
11.2　 整数的立方根 161
11.3　 整数求幂 162
11.4　 整数对数 164
第12章　 数制中的特殊底 171
12.1　 以-2为底 171
12.2　 以-1+i为底 176
12.3　 其他底 178
12.4　 最有效的底是什么 178
第13章　 Gray码 181
13.1　 Gray码 181
13.2　 递增Gray码整数 183
13.3　 负二进制Gray码 184
13.4　 简史及应用 184
第14章　 Hilbert曲线 187
14.1　 生成Hilbert曲线的递归算法 187
14.2　 从Hilbert曲线的路长求坐标 191
14.3　 Hilbert曲线上坐标到路长的转换 196
14.4　 递增Hilbert曲线上点的坐标 198
14.5　 非递归生成算法 200
14.6　 其他空间填充曲线 200
14.7　 应用 201
第15章　 浮点 203
15.1　 IEEE格式 203
15.2　 利用整数操作进行浮点数比较 205
15.3　 前导数字分布 206
15.4　 各种各样的值的列表 207
第16章　 素数公式 211
16.1　 介绍 211
16.2　 Willans公式 212
16.3　 Wormell公式 215
16.4　 求其他比较麻烦的函数的公式 216
附录A　 四位计算机的算术表 221
附录B　 牛顿方法 225
参考文献 227
索引 233