本书介绍了构建更优雅、更有效的软件的更省时技术、算法和技巧。这些方法都非常实用，而且很有趣，有时候会让人觉得意想不到，就像在解好玩的谜题一样。相信任何想要得到提高的程序员都能从本书中受益匪浅。

“这是第一本宣称能讲解计算机算法隐晦细节的书，而且讲得还真不错。我知道的每一条技巧书里都提到了，而且还讲了好多好多我不知道的。不论是在开发程序库或编译器，还是在极力搜求优雅算法，此书都可谓天赐良册，应放在高德纳所著《计算机程序设计艺术》那套书旁边。本书第一版刊印后的10年间，它对我在Sun和Google的工作大有裨益，而第二版所添加新内容亦令我惊羡不已。”
—— Joshua Bloch

“初看本书书名时，我想，这是教人怎么入侵计算机系统的书吗？不太可能吧。嗯，那就肯定是一本编程小技巧的集锦。看了之后发现，没错，这就是一本编程秘籍，然而却是一本包罗万象的秘籍。第二版新增了两个大主题，并用数十个小技巧丰富了本书内容，其中有个小绝招是如何在不溢出的情况下求两数均值，我写二分查找算法时直接就把这条拿来用了。这真是本令算法爱好者开怀畅读的书啊！”
—— Guy Steele

在本书中，作者给我们带来了一大批极为诱人的知识，其中包括各种节省程序运行时间的技巧、算法与窍门。学习了这些技术，程序员就可写出优雅高效的软件，同时还能洞悉其中原理。这些技术极为实用，而且其问题本身又非常有趣，有时甚至像猜谜解谜一般，需要奇思妙想才行。简而言之，软件开发者看到这些改进程序效率的妙计之后，定然大喜。

本书较第1版增补了大量内容
新增了循环冗余校验（CRC）一章，其中讲解了常用的CRC-32校验码
新增了纠错码（ECC）一章，其中讲解了汉明码
详解了除数为常数的整数除法，增补了仅含移位操作和加法操作的算法
不计算商而直接求余数
扩充了与种群计数和前导0计数有关的知识
数组种群计数
执行压缩与扩展操作的新算法
LRU算法
浮点数与整数互化
估算浮点数的平方根倒数
一系列离散函数图像
各章均配有习题与参考答案


作者简介
Henry S. Warren, Jr.　 计算机科学家，在IBM供职50余年，经历了IBM704时代、PowerPC时代及其后种种更迭。曾参与多个军事指挥与控制系统工程，并且参加了由Jack Schwarz领衔的“SET语言”项目。自1973年起，Henry就职于IBM研发部，努力探索编译器和计算机架构。当前正研究一种旨在每秒执行百亿亿次运算的超级计算机。他拥有纽约大学柯朗数学科学研究所计算机科学博士学位。

译者简介
爱飞翔　 资深软件开发工程师，擅长Web开发、移动开发和游戏开发，有10余年开发经验，曾主导和参与了多个手机游戏和手机软件项目的开发，经验十分丰富。业余爱好文学和历史，有一定的文学造诣。翻译并出版了多本计算机著作，如《NoSQL精粹》、《Effective Objective-C 2.0：编写高质量iOS与OS X代码的52个有效方法》、《测试驱动的iOS开发》和《JavaScript应用开发实践指南》等。


由在IBM工作50余年的资深计算机专家撰写，Amazon全五星评价，算法领域最有影响力的著作之一
Google公司首席架构师、Jolt大奖得主Joshua Bloch和Emacs合作创始人、C语言畅销书作者Guy Steele倾情推荐
算法的艺术和数学的智慧在本书中得到了完美体现，书中总结了大量高效、优雅和奇妙的算法，并从数学角度剖析了其背后的原理

程序员创造力第一定律：软件维护成本与程序员创造力的平方成正比。
　　　　——Robert DBliss，1992年
　　本书收集了笔者多年来总结的一些编程小技巧，其中大部分都必须运行在以二进制补码来表示整数的电脑上。尽管本书假设寄存器长度是32位，但在寄存器长度不是32位的电脑中，这些技巧基本上仍能适用。
　　本书不打算讲高深的排序算法或是编译器的优化技术等大话题，而是着重来谈涉及单个计算机字组或指令的小技巧，比如怎样统计字组中值为1的位元数。此类技巧通常需要混用算术与逻辑指令。
　　我们还需假定整数溢出中断已经屏蔽，这样的话，就算整数运算溢出了，也不会出问题。C、Fortran、Java等程序都是如此，但使用Pascal与Ada语言的程序员一定要注意这一点！
　　在本书语境中，电脑、计算机(computer)、机器(machine)、处理器(processor)等词常常都指代中央处理器(CPU)，故译文在不致混淆的情况下，将其视为互相通用的概念。——译者注
　　integer overflow，指算术运算时由于结果过大或过小而超出存储范围的情形。详情参见：https：//enwikipediaorg/wiki/Integer_overflow。——译者注
　　书中以通俗的语言来讲述各技巧，只有算法含义不明显时才会给出证明，有时甚至略去证明。算法中将会出现计算机算术指令、“地板”函数、算术与逻辑操作混搭等内容，它们要证明起来通常比较困难，而且也不易表述。
　　 floor function，又叫向下取整函数或最低值函数，返回不大于自变量的最大整数，也常称为“高斯函数”。详情参见：https：//zhwikipediaorg/wiki/地板函数。——译者注
　　笔者把很多算法都写成了程序代码，在电脑上执行并验证，以减少笔误及疏忽。用实际存在的编程语言来描述算法，就有这个好处；然而即便如此，每一种计算机语言也还是各有其缺陷。我使用很多人能看懂的C代码来描述高级语言部分，因为它可以直接把整数与位串操作写在一起，而且很多C语言编译器都能产生高质量的目标代码。
　　object code，又叫“目的码”，是编译器处理源代码后的产物，一般由机器码或近于机器语言的代码组成。存放此类代码的文件叫目标文件(object code)，也叫二进制文件。详情参见：https：//zhwikipediaorg/wiki/目标代码。——译者注
书中偶尔也会用到机器语言，它们都以“三地址格式”出现，这样读起来更方便。其中的汇编语言是笔者参照当下的RISC指令集虚构出来的。
　　threeaddress format，即three address code，缩写为TAC或3AC，又叫“三位址码”、“三地址码”。它把通常的算式“运算结果=操作数1 操作符 操作数2”写成“操作符 操作数1，操作数2，运算结果”的形式，因其中牵涉3个变量(即操作数1、操作数2、运算结果)而得名。例如z=x+y用TAC格式来写就是add x，y，z。详情参见：https：//enwikipediaorg/wiki/Three_address_code。——译者注
　　RISC，Reduced Instruction Set Computing的缩写，是一种设计CPU的模式，该设计思路精简了指令数目及定址方式，使CPU的制作更为容易，也有助于提升其并行能力与执行效率。使用此种指令集的CPU目前主要应用于智能手机和平板电脑等移动设备上，与之相对的是x86等处理器所用的“复杂指令集”(CISC，C表示Complex)。详情参见：https：//zhwikipediaorg/wiki/精简指令集。——译者注
大家应该尽量编写没有分支的代码(branchfree code)，因为分支代码会拖慢很多电脑的指令获取速度，并阻止CPU并发执行。此外，它还会妨碍一些编译器优化措施，如指令调度、重复子表达式消除、寄存器分配等。也就是说，编译器优化大段的简单代码要比优化很多小代码块的效果更好。
　　常见的编译器优化技法请参考：https：//enwikipediaorg/wiki/Category：Compiler_optimizations。——译者注
　　instruction scheduling，是通过指令流水线(instruction pipeline)技术提升指令并发执行效果的优化手法。详情参见：https：//enwikipediaorg/wiki/Instruction_scheduling。——译者注
　　commoning，即common subexpression elimination(CSE)，是通过消减重复的表达式来提升执行速度的优化技术。详情参见：https：//enwikipediaorg/wiki/Common_subexpression_elimination。——译者注
　　register allocation，该技术让众多变量共用一个CPU寄存器，以优化执行速度。详情参见：https：//enwikipediaorg/wiki/Register_allocation。——译者注
此外，编码时还应该多用数值较小的常量，多与0比较(少与非0值比较)，尽量写出易于并发执行的指令序列。如果改写书里很多代码，让它们从内存中查表，其结果会更精确，然而笔者通常不提这种做法。因为与算术指令相比，从内存中加载数据反而更耗时。虽说查表法的确很实用，但是一般来说都比较乏味。当然还有些特例不属于上述情况。
　　immediate value，也叫“立即值”。——译者注
　　instructionlevel parallism，缩写为ILP，意为指令级并行度，用于度量指令序列的并发执行程度。例如某段指令在非并发方式下需要3个时间单位来执行，而并发执行只需2个时间单位，那么其ILP就是3/2。详情参见：https：//enwikipediaorg/wiki/Instructionlevel_parallelism。书中还用该词表示CPU并发执行指令的能力。——译者注
最后要说的是，本书书名本书英文书名为Hackers Delight。——译者注中的“hacker”用的是本意，也就是指痴迷于计算机的人。这种人喜欢拿电脑开发点新玩意儿，或是用新潮而有创意的办法来实现原有的功能。他们都挺会用电脑，但却很可能不是一名专职电脑程序员或设计师，这些电脑极客开发出来的东西，有些有用，有些只是玩玩而已。说到此类纯属玩乐的戏作，让我想起很多资深编程票友都写过一段小程序，它可以把自己照原样打印出来比方说，下面这段用C语言写的程序代码：
　　本书语境中的“hacker”可理解成“电脑极客”、“程序玩家”、“编程票友”、“编程达人”、“技术发烧友”等意思，以便与容易引发歧义的“骇客”、“黑客”等通俗叫法区分开。本来hacker指计算机技术狂热爱好者，而cracker指破坏计算机安全的人，但后者的词义逐渐侵蚀了前者，导致cracker、hacker及“骇客、黑客、怪客、刽客”等译名全都成了“计算机安全破坏者”，令hacker一词丧失了原意。详情参见：https：//zhwikipediaorg/wiki/骇客。——译者注
main(){char*p="main(){char*p=%c%s%c；(void)printf(p，34，p，34，10)；}%c"；(void)printf(p，34，p，34，10)；}。这才是我使用“hacker”一词的初衷，在书里可别想找到教你怎样入侵他人电脑的把戏哦。
致谢
首先要感谢Bruce Shriver与Dennis Allison两位先生鼓励我写作本书，然后还要对IBM诸位同仁致意，参考文献中也提到了其中一些同事的名字。尤其感谢Martin E.Hopkins先生，他可谓IBM的“活编译器”(MrCompiler)。Hopkins先生在编码工作中一丝不苟，认真优化每一个循环——这种敬业精神深深感染了我。仰赖AddisonWesley各位评审，本书内容有了极大改观。他们的姓名笔者大多不了解，我唯一记住的是大名鼎鼎的Guy LSteele，Jr。在50页书评中，Guy补充了一些我当时没有谈到的新问题，如位元的打乱与复原，“绵羊与山羊分离操作”(分羊法，sheep and goats operation)，等等，而且他提出的一些算法也比我原来用的更高明。Guy是个非常仔细的人，比方说，我曾把十六进制数AAAAAAAA的质因子分解式错写为2×3×17×257×65 537，而他发现其中的3应该是5。此外，他还提了一些旨在改善写作风格的建议，并且从不回避书里的细节问题。读者若发现文中有疑似他人捉刀之处，那恐怕得归功于Guy了。
　　原文为parallel prefix，意为“并行前置式算法”、“平行前缀算法”，是一套分组归并形式的速算流程。详情参见：https：//wwwwikipediaorg/wiki/Prefix_sum。作者在此处以之比喻他与Guy四手联弹的佳话。——译者注

H.S.Warren，Jr
2012年6月于纽约州约克镇

本书英文版相关资料请查阅
www.HackersDelight.org

计算机\程序设计

“这是第一本宣称能讲解计算机算术隐晦细节的书，而且讲得还真不错。我知道的每一条技巧书里都提到了，而且还讲了好多好多我不知道的。不论是在开发程序库或编译器，还是在极力搜求优雅算法，此书都可谓天赐良册，应放在高德纳所著《计算机程序设计艺术》那套书旁边。本书第一版刊印后的10年间，它对我在Sun和Google的工作大有裨益，而第二版所添加新内容亦令我惊艳不已。”
——Joshua Bloch

“初看本书书名时，我想，这是教人怎么入侵计算机系统的书吗？不太可能吧。嗯，那就肯定是一本编程小技巧的集锦。看了之后发现，没错，这就是一本编程秘籍，然而却是一本包罗万象的秘籍。第二版新增了两个大主题，并用数十个小技巧丰富了本书内容，其中有个小绝招是如何在不溢出的情况下求两数均值，我写二分查找算法时直接就把这条拿来用了。这真是本令算法爱好者开怀畅读的书啊！”
——Guy Steele

在本书中，作者Hank Warren先生给我们带来了一大批极为诱人的知识，其中包括各种节省程序运行时间的技巧、算法与窍门、学习了这些技术，程序员就可写出优雅高效的软件，同时还能洞悉其中原理。这些技术极为实用，而且其问题本身又非常有趣，有时甚至像猜谜解谜一般，需要奇思妙想才行。简而言之，软件开发者看到这些改进程序效率的妙计之后，定然大喜。

本书较第1版增补了大量内容

■ 新增了循环冗余校验（CRC）一章，其中讲解了常用的CRC-32校验码
■ 新增了纠错码（ECC）一章，其中讲解了汉明码
■ 增补了常除数整数除法的相关内容，讲解了只需移位和加法操作的算法
■ 不计算商而直接求余数
■ 扩充了与种群计数和前导0计数有关的知识
■ 数组种群计数
■ 执行压缩与扩展操作的新算法
■ LRU算法
■ 浮点数与整数互化
■ 估算浮点数的平方根倒数
■ 一系列离散函数图像
■ 各章均配有习题与参考答案

（美）Henry S. Warren, Jr. 著：暂无简介

爱飞翔 译：暂无简介

写代码总会遇到难题，时而苦于乘法操作频繁溢出，时而苦于开方算法太过笨拙，于是，程序员之间口耳相传的那些代码秘籍，这些时候就该大显身手了。有些小程序，仅两三行代码即能解决平常数十行代码方能实现的功能；还有些小程序，只用0x24924925这般神奇的数字，即能成倍提升运算速度。读者若对此感兴趣，则本书定能令你开怀畅读。
　　作者从事计算机研发工作数十年，他将期间所得之大量技巧融于书中。本书不但讲授算法技巧，而且还会剖析背后的数学原理，令你在学会某个奇妙算法后，可举一反三，推出很多类似技巧，以运用于不同场合。
　　在研究这些高效而优雅的算法时，作者还会如数家珍地列出许多变体，并旁征博引地讲述可以解决同一问题的其他思路，铺陈完毕后，更会将各自优劣娓娓道来。实际应用中，经常需要权衡各算法之轻重，嵌入式开发、硬件编程、图形渲染、游戏智能等领域尤其如此，若是平素能像作者这样勤于总结、善于对比，那么在需要用到相关技巧时必能信手拈来，左右逢源。
　　从培养兴趣、锻炼思维、付诸实践三个角度观之，本书皆为精彩而思辨的智慧书。既可静心品读代码之诗意，又能细致体味数学之美感，何其乐哉！
　　作者乃业界翘楚，学识渊博而思维开阔，文中部分词句与日常用语及数学、计算机等领域一般用法不甚相同，故译文或加注释或添引号，以强调其特殊含义。
　　翻译过程中，得到机械工业出版社华章分社诸君勉励，于此深表谢意。
　　本书主要由爱飞翔翻译，舒亚林、张军、王鹏亦参与部分翻译工作。小弟乐意与各位朋友通过个人网站(www.agilemobidev.com)及电子邮件(eastarstormlee@gmailcom)探讨算法问题。由于时间仓促，水平有限，错误与疏漏在所难免，敬请读者不吝赐教。

爱飞翔
2014年2月

译者序
序（第1版序）
前言
第1章概述
1.1记法
1.2指令集与执行时间模型
1.3习题
第2章基础知识
2.1操作最右边的位元
2.1.1德摩根定律的推论
2.1.2从右至左的可计算性测试
2.1.3位操作的新式用法
2.2结合逻辑操作的加减运算
2.3逻辑与算术表达式中的不等式
2.4绝对值函数
2.5两数平均值
2.6符号扩展
2.7用无符号右移模拟带符号右移操作
2.8符号函数
2.9三值比较函数
2.10符号传递函数
2.11将值为0的位段解码为2的n次方
2.12比较谓词
2.12.1利用进位标志求比较谓词
2.12.2计算机如何设置比较谓词
2.13溢出检测
2.13.1带符号的加减法
2.13.2计算机执行带符号数的加减法时如何设置溢出标志
2.13.3无符号数的加减法
2.13.4乘法
2.13.5除法
2.14加法、减法与乘法的特征码
2.15循环移位
2.16双字长加减法
2.17双字长移位
2.18多字节加减法与求绝对值
2.19doz、max、min函数
2.20互换寄存器中的值
2.20.1交换寄存器中相应的位段
2.20.2交换同一寄存器内的两个位段
2.20.3有条件的交换
2.21在两个或两个以上的值之间切换
2.22布尔函数分解公式
2.23实现16种二元布尔操作
2.24习题
第3章2的幂边界
3.1将数值上调/下调为2的已知次幂的倍数
3.2调整到上一个/下一个2的幂
3.2.1向下舍入
3.2.2向上舍入
3.3判断取值范围是否跨越了2的幂边界
3.4习题
第4章算术边界
4.1检测整数边界
4.2通过加减法传播边界
4.3通过逻辑操作传播边界
4.4习题
第5章位计数
5.1统计值为“1”的位元数
5.1.1两个字组种群计数的和与差
5.1.2比较两个字组的种群计数
5.1.3统计数组中值为“1”的位元数
5.1.4应用
5.2奇偶性
5.2.1计算字组的奇偶性
5.2.2将表示奇偶性的位元添加到7位量中
5.2.3应用
5.3前导0计数
5.3.1浮点数算法
5.3.2比较两个字组前导0的个数
5.3.3与对数函数的关系
5.3.4应用
5.4后缀0计数
5.5习题
第6章在字组中搜索位串
6.1寻找首个值为0的字节
6.1.10值字节位置函数的
一些简单推广
6.1.2搜索给定范围内的值
6.2寻找首个给定长度的全1位串
6.3寻找最长全1位串
6.4寻找最短全1位串
6.5习题
第7章重排位元与字节
7.1反转位元与字节
7.1.1位元反转算法的推广
7.1.2奇特的位元反转算法
7.1.3递增反转后的整数
7.2乱序排列位元
7.3转置位矩阵
7.4压缩算法(广义提取算法)
7.4.1用“插入”、“提取”指令实现压缩操作
7.4.2向左压缩
7.5展开算法(广义插入算法)
7.6压缩与展开操作的硬件算法
7.6.1压缩
7.6.2展开
7.7通用置换算法及分羊操作
7.8重排与下标变换
7.9LRU算法
7.10习题
第8章乘法
8.1多字乘法
8.264位积的高权重部分
8.3无符号与带符号的高权重积互化
8.4与常数相乘
8.5习题
第9章整数除法
9.1预备知识
9.2多字除法
9.3用带符号除法计算无符号短除法
9.3.1用带符号长除法计算无符号短除法
9.3.2用带符号短除法计算无符号短除法
9.4无符号长除法
9.4.1用硬件实现移位并相减算法
9.4.2用短除法实现无符号长除法
9.5用长除法实现双字除法
9.5.1无符号双字除法
9.5.2带符号双字除法
9.6习题
第10章除数为常量的整数除法
10.1除数为2的已知次幂的带符号除法
10.2求与2的已知次幂相除的带符号余数
10.3在除数不是2的幂时求带符号除法及余数
10.3.1除以3
10.3.2除以5
10.3.3除以7
10.4除数大于等于2的带符号除法
10.4.1算法
10.4.2算法可行性证明
10.4.3证明乘积正确
10.5除数小于等于-2的带符号除法
10.6将除法算法集成至编译器中
10.7其他主题
10.7.1唯一性
10.7.2可生成最佳程序代码的除数
10.8无符号除法
10.8.1除数为3的无符号除法
10.8.2除数为7的无符号除法
10.9除数大于等于1的无符号除法
10.9.1无符号版算法
10.9.2算法可行性证明
10.9.3证明无符号版算法的乘积正确
10.10将无符号除法算法集成至编译器中
10.11与无符号除法相关的其他话题
10.11.1可生成最佳无符号除法代码的除数
10.11.2带符号乘法与无符号乘法互化
10.11.3更简单的无符号除法生成算法
10.12余数非负式除法与向下取整式除法的适用性
10.13类似算法
10.14神奇数字示例
10.15用Python语言编写的简单代码
10.16除数为常量的精确除法
10.16.1用欧几里得算法计算乘法逆元素
10.16.2用牛顿法计算乘法逆元素
10.16.3乘法逆元素示例
10.17检测除以常数后是否余0
10.17.1无符号除法
10.17.2除数大于等于2的带符号除法
10.18不使用Multiply High指令的除法算法
10.18.1无符号除法
10.18.2带符号除法
10.19合计各数位求余数
10.19.1求无符号除法的余数
10.19.2求带符号除法的余数
10.20用乘法及右移位求余数
10.20.1求无符号除法的余数
10.20.2求带符号除法的余数
10.21将普通除法化为精确除法
10.22计时测试
10.23用电路计算除数为3的除法
10.24习题
第11章初等函数
11.1整数平方根
11.1.1用牛顿法开平方
11.1.2二分查找
11.1.3硬件算法
11.2整数立方根
11.3求整数幂
11.3.1用n的二进制分解式计算xn
11.3.2用Fortran语言计算2n
11.4整数对数
11.4.1以2为底的整数对数
11.4.2以10为底的整数对数
11.5习题
第12章以特殊值为底的数制
12.1以-2为底的数制
12.2以-1+i为底的数制
12.3以其他数为底的数制
12.4最高效的底是什么
12.5习题
第13章格雷码
13.1简介
13.2递增格雷码整数
13.3负二进制格雷码
13.4格雷码简史及应用
13.5习题
第14章循环冗余校验
14.1简介
14.2理论
14.3实现
14.3.1硬件实现
14.3.2软件实现
14.4习题
第15章纠错码
15.1简介
15.2汉明码
15.2.1SECDED码
15.2.2校验位个数的最小值
15.2.3小结
15.3适用于32位信息的软件SECDED算法
15.4广义错误修正
15.4.1汉明距离
15.4.2编码论的主要问题
15.4.3n维球面
15.5习题
第16章希尔伯特曲线
16.1生成希尔伯特曲线的递归算法
16.2根据希尔伯特曲线上从起点到某点的途经距离求其坐标
16.3根据希尔伯特曲线上的坐标求从起点到某点的途经距离
16.4递增希尔伯特曲线上点的坐标
16.5非递归的曲线生成算法
16.6其他空间填充曲线
16.7应用
16.8习题
第17章浮点数
17.1IEEE格式
17.2整数与浮点数互化
17.3使用整数操作比较浮点数大小
17.4估算平方根倒数
17.5前导数位的分布
17.6杂项数值表
17.7习题
第18章素数公式
18.1简介
18.2Willans公式
18.2.1Willans第二公式
18.2.2Willans第三公式
18.2.3Willans第四公式
18.3Wormell公式
18.4用公式来描述其他难解的函数
18.5习题
参考答案
附录A4位计算机算术运算表
附录B牛顿法
附录C各种离散函数图像
参考文献