《高效程序的奥秘》（Hacker’s Delight）
作者：[美] Henry S. Warren, Jr.（IBM 资深程序员，参与蓝基因千万亿浮点计算机项目） 译者：冯速 出版社：机械工业出版社 页数：255 页
一、书籍定位与核心价值
本书是计算机领域独一无二的位操作与底层算术技巧合集，被誉为”编程界的武功秘籍”。它不讲解大型程序设计方法、数据结构或算法设计模式，而是聚焦于计算机字级别的高效小技巧——如何用最少的指令、最快的速度完成整数与位串操作。
核心特色
- 源自 HAKMEM 传统：受 MIT 1972 年著名技术备忘录《HAKMEM》启发，系统收集整理了大量精妙的编程小技巧
- 填补空白：多数算法书忽视了”位”这个最小数据单元的威力，本书专门填补了二进制位操作领域的空白
- 实用导向：所有算法都经过实际运行验证，用 C 语言描述，可直接用于优化编译器、图形学、密码学、数学计算等领域
- 无分支偏好：尽量使用无分支代码，因为分支会拖慢指令提取、抑制指令并行、影响编译器优化
适用读者
- 想要编写、欣赏巧妙高效代码的程序员
- 编译器/优化编译器设计者
- 嵌入式程序开发者
- 计算机硬件设计者
- 希望提升程序设计技艺的爱好者
书名中的 “Hacker” 指计算机狂热爱好者——用更巧妙的方法处理事务、技艺高超的人，而非入侵他人电脑的人。
二、全书知识体系
全书共 16 章 + 2 个附录，按主题可分为以下几大板块：
板块一：基础位运算（第 1–4 章）
| 章节 | 主题 | 核心内容 |
|---|---|---|
| 第1章 | 介绍 | 记法约定、指令集模型、C 语言与计算机代数运算符优先级表 |
| 第2章 | 基础 | 操作最右侧位、逻辑+算术恒等式、绝对值/符号扩展/符号函数/比较谓词/溢出检测/循环移位/双字长运算/交换寄存器（20 节） |
| 第3章 | 2 的幂边界 | 上/下舍入到 2 的幂倍数、上/下舍入到下一个 2 的幂、检测 2 的幂边界跨越 |
| 第4章 | 算术边界 | 整数边界检测、加减操作的边界传播、逻辑操作的边界传播 |
板块二：位操作核心技术（第 5–7 章）
| 章节 | 主题 | 核心内容 |
|---|---|---|
| 第5章 | 位计数 | 1 位计数（popcount）、奇偶性、前导 0 计数、后缀 0 计数 |
| 第6章 | 字搜索 | 寻找第一个 0 字节、寻找第一个给定长度的 1 位串 |
| 第7章 | 位和字节的重排列 | 位反转/字节反转、混洗位、转置位矩阵、压缩/广义提取、一般置换（分羊操作）、重排列和索引变换 |
板块三：算术运算优化（第 8–11 章）
| 章节 | 主题 | 核心内容 |
|---|---|---|
| 第8章 | 乘法 | 多字乘法、64 位积的高阶位、无符号/带符号积高阶位转换、常量乘法 |
| 第9章 | 整数除法 | 预备知识（多种除法定义差异）、多字除法、带符号→无符号短除法转换、无符号长除法 |
| 第10章 | 整数常量除法 | 除以 2 的幂、非 2 的幂的带符号除法、魔术数算法、并入编译器、无符号除法、精确除法、零余数检测（16 节全章重点） |
| 第11章 | 初等函数 | 整数平方根、整数立方根、整数求幂、整数对数 |
板块四：特殊数制与编码（第 12–14 章）
| 章节 | 主题 | 核心内容 |
|---|---|---|
| 第12章 | 数制中的特殊底 | 以 -2 为底（负二进制）、以 -1+i 为底、其他底、最有效的底是什么 |
| 第13章 | Gray 码 | Gray 码定义与转换、递增 Gray 码整数、负二进制 Gray 码、简史及应用 |
| 第14章 | Hilbert 曲线 | 递归生成算法、路长→坐标转换、坐标→路长转换、非递归生成算法、其他空间填充曲线、应用 |
板块五：杂项主题（第 15–16 章）
| 章节 | 主题 | 核心内容 |
|---|---|---|
| 第15章 | 浮点 | IEEE 格式、利用整数操作进行浮点数比较、前导数字分布、值列表 |
| 第16章 | 素数公式 | Willans 公式、Wormell 公式、其他复杂函数的公式 |
附录
- 附录 A：四位计算机的算术表
- 附录 B：牛顿方法
- 参考文献
- 索引
三、经典技巧精选
1. 操作最右侧位（第 2 章）
- 清除最右侧的 1：
x & (x - 1)— Brian Kernighan 算法的核心 - 提取最右侧的 1：
x & (-x) - 右传播最右侧的 1：
x | (x - 1)
2. 加法的位运算表示（第 2 章）
经典恒等式（出自 HAKMEM）：
x + y = (x ⊕ y) + 2(x & y)— 异或得无进位和，与左移得进位x + y = (x | y) + (x & y)x - y = (x ⊕ y) - 2(¬x & y)
3. 位计数分治算法（第 5 章）
最经典的无分支 popcount 算法，核心是分治位并行思想：
每 2 位计数 → 每 4 位计数 → 每 8 位计数 → 每 16 位 → 32 位
使用掩码 0x55555555、0x33333333、0x0F0F0F0F 等实现分组相加，O(log n) 时间常数级操作。
4. 检测 2 的幂边界跨越（第 3 章）
判断地址区间 [a, a+l-1] 是否跨越 2 的幂次块边界：
- IBM System/370 经典实现：
(a | -块大小) + l后判断进位 - RISC 适配：
-(a | -块大小) < l（利用¬x < y等价于x + y进位）
5. 整数常量除法优化（第 10 章，全书重点）
核心思想：将除以常量转化为乘法 + 移位，大幅提升除法性能。
- 魔术数（magic number）算法：对每个除数 d，找到一个魔术数 M 和移位量 s，使得
n ÷ d = (n × M) ≫ s - 支持带符号和无符号除法
- 可直接并入编译器后端优化
- 精确除法（已知余数为 0 时）有更简单的实现
6. 位反转与混洗（第 7 章）
- 位反转：分治交换法、查表法
- 字节反转
- 转置位矩阵（bit matrix transpose）
- 压缩/广义提取（compress/extract，类似 BMI2 的 PEXT/PDEP）
- 一般置换（“分羊操作” / sheep and goats）
7. Gray 码（第 13 章）
- 二进制 → Gray 码：
G = B ⊕ (B ≫ 1) - Gray 码 → 二进制：逐位异或传播
- 递增 Gray 码整数的高效算法
- 应用：位置编码、错误校正、数模转换等
8. Hilbert 曲线（第 14 章）
空间填充曲线的经典实现：
- 递归生成算法
- 路长 ↔ 坐标双向转换
- 非递归生成算法
- 应用：多维索引、图像压缩、空间数据结构
四、关键概念与术语
| 概念 | 说明 |
|---|---|
| 2 的补码 | 本书默认的整数表示方式，所有技巧基于此 |
| 截取除法 | 向零取整的除法（C 语言默认），本书统一约定 |
| 地板除法 | 向负无穷取整的除法（Python 默认） |
| popcount / 种群计数 | 统计二进制中 1 的位数 |
| nlz | number of leading zeros，前导 0 计数 |
| ntz | number of trailing zeros，后缀 0 计数 |
| HAKMEM | MIT 1972 年技术备忘录，编程技巧的经典源头 |
| 魔术数算法 | 常量除法转乘法+移位的优化技术 |
| 负基数 | 以负数为底的数制（如 -2 进制），无需符号位 |
| Gray 码 | 相邻两个数只有一位不同的编码 |
| Hilbert 曲线 | 连续填充二维空间的一维曲线，保持空间局部性 |
五、与其他知识的关联
- 《程序设计实践》-The-Practice-of-Programming-Kernighan-Pike — 同为实践导向的编程经典，TPoP 偏高层风格与设计，本书偏底层技巧与位运算
- 《程序员的自我修养》-链接、装载与库 — 本书关注指令级优化，《自我修养》关注程序的编译链接装载，互补
- 《结构化计算机组成》-Structured-Computer-Organization-第6版-Tanenbaum — 理解计算机的层次结构，能更好地应用本书的底层优化技巧
- 《计算机体系结构》-量化研究方法-第5版-Hennessy-Patterson — 从体系结构角度理解为什么无分支代码更快、为什么位操作高效
- 《SICP》-计算机程序的构造和解释-第二版 — SICP 关注抽象与高阶，本书关注底层与细节，是编程光谱的两端
- 《实现模式》-Implementation%20Patterns-Kent%20Beck — 实现模式关注代码设计层面的模式，本书关注机器指令层面的模式
六、阅读建议
- 按需查阅：本书更像手册而非需要通读的教材，遇到位运算/算术优化问题时查阅对应章节
- 动手验证：每个技巧都值得自己写代码验证一遍，加深理解
- 从第 2 章开始：第 2 章”基础”包含了全书最常用的 20 个核心技巧，是全书基础
- 第 10 章重点精读：整数常量除法是全书技术含量最高的章节之一，编译器开发者必看
- 第 14 章拓展视野：Hilbert 曲线展示了位运算与几何/空间数据结构的奇妙联系
“程序员创造力第一法则：软件维护成本的增加与程序设计人员的创造力的平方成正比。” —— Robert D. Bliss, 1992