算法心得：高效算法的奥秘（原书第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各种离散函数图像
参考文献