算法心得-算法的奥秘-(原书第2版)

内容简介

在本书中，作者给我们带来了一大批极为诱人的知识，其中包括各种节省程序运行时间的技巧、算法与窍门。学习了这些技术，程序员就可写出优雅的软件，同时还能洞悉其中原理。这些技术极为实用，而且其问题本身又有趣，有时甚至像猜谜解谜一般，需要奇思妙想才行。简而言之，软件开发者看到这些改进程序效率的妙计之后，定然大喜。
 
　　本书较第1版增补了大量内容
　　新增了循环冗余校验（CRC）一章，其中讲解了常用的CRC-32校验码
　　新增了纠错码（ECC）一章，其中讲解了汉明码
　　详解了除数为常数的整数除法，增补了仅含移位操作和加法操作的算法
　　不计算商而直接求余数
　　扩充了与种群计数和前导0计数有关的知识
　　数组种群计数
　　执行压缩与扩展操作的新算法
　　LRU算法
　　浮点数与整数互化
　　估算浮点数的平方根倒数
　　一系列离散函数图像
　　各章均配有习题与参考答案

目录

译者序
　
序（第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.

摘要与插图

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