逻辑位、乘法以及除法指令 — 位模式手术与乘除法的寄存器芭蕾Copy Anchor Link

这一章讲什么: 程序的组织学完了,本章转向「计算」本身。四件事: 位掩码(用 AND/OR/XOR 直接改写某个位)、移位(乘除 2 的幂的高速公路, 也是进制转换的主角)、乘法(imul 五种形态,以及为什么单操作数形态要霸占一对寄存器)、 除法(div/idiv 的隐式寄存器约定,和 C/Python 有符号除法规则之差)。 主线例子: 一个完整的往返——键盘敲下 "123",decToUInt 把它变成整数 123(用 imul); 加 123 得 246,intToUDec 再把 246 变回字符串 "246"(用 div)。 字符串与二进制之间怎么互相翻译,全在这两个函数里。

1. 位掩码:把数据当位模式,而不是当数Copy Anchor Link

活教材:大小写字母只差一个位Copy Anchor Link

ASCII 表里大小写字母的唯一区别是位 5(从右数第 6 位):1 是小写,0 是大写。 m = 0x6d = 0110 1101,M = 0x4d = 0100 1101——差的正是那个 32(0x20)¹。

所以「转大写」不用减 32,也不用判断当前大小写,一张掩码 + 一次 AND 就完事:

掩码 = 1101 1111 = 0xdf     ← 位 5 是 0,其余全是 1
0x6d ∧ 0xdf = 0x4d   m → M
0x4d ∧ 0xdf = 0x4d   M → M(大写的怎么按都还是大写)

AND 的真值表决定了它的掩码语义:1 是「透明窗」(原样通过),0 是「抹除」。 由此推出三种标准手法,记住这一张表,位操作就全会了²:

toUpper 的 C 与汇编对照Copy Anchor Link

C 版 toUpper(清单 16-3)对每个字符做 *destPtr = *srcPtr & UPMASK;, 指针各自 +1,直到撞上 NUL——循环骨架是第 13 章的,新东西只有那一个 &³。 gcc 的汇编(清单 16-4)里,掩码以立即数 −33 出现:and eax, -33—— −33 的补码恰好是 0xffffffdf,低 8 位 0xdf,效果一样⁴。

手写版(清单 16-6)用 al 直接处理字符,一个细节:操作 al 时 rax 的高 56 位保持原样, 所以只碰 al 是安全的——但别忘了循环终止用 cmp al, NUL,以及循环后把 NUL 也写进 目标串(忘了它是最经典的隐藏 bug:测试时碰巧下一个字节是 0 而蒙混过关,改天换个 长度就以随机方式暴雷)⁵。

顺带收两条指令卡:and / or(形态与 xor 同族,结果存目标;只设 SF/ZF/PF, OF、CF 清零)⁶。

2. 移位:乘除 2 的幂,与进制转换的发动机Copy Anchor Link

核心事实:移一位 = 乘/除 2Copy Anchor Link

把一个整数的所有位左移一位,等于乘 2;右移一位,等于除以 2—— 移位指令是机器上最快的乘除法,因为进位链本来就是硬件里现成的⁷。

主线例子第一站:hexToInt,"2a" 怎么变成 0x2aCopy Anchor Link

程序读入十六进制字符串(如 "2a"),要把它变成 long int。算法对每个字符做两件事: 把 ASCII 字符转成 4 位整数,然后把 64 位累加值左移 4 位,腾出空当,OR 进新 4 位⁸:

读 '2':ASCII 0x32,本身就是数字字符,& 0x0f → 0x02
  累加值: 0x00 << 4 | 0x02 = 0x02
读 'a':ASCII 0x61,比 '9' 大,先减 0x07 得 0x5a,& 0x0f → 0x0a
  累加值: 0x02 << 4 | 0x0a = 0x2a    ← 字符串 "2a" 现在是数 42

两个掩码细节都值得停:减 0x07 补字母和数字之间的 ASCII 间隙('9' 是 0x39, 'A' 是 0x41,差 7);减完再 & 0x0f 取低 4 位——大小写无所谓, 因为 'a' 减完得 0x5a、'A' 减完得 0x3a,低 4 位都是 0x0a⁸。

移位指令家族:三个成员,两种右移Copy Anchor Link

移位次数来自 cl 寄存器或立即数;32 位移位只用计数器的低 5 位,64 位用低 6 位⁹:

书里的「小心」一句话:sar 移负数永远移不成 0(−1 右移任意位还是 −1), 因为最高位的 1 会被无限复制——想要「越移越小直到 0」的直觉,那是 shr 的世界¹⁰。

movsx / movsxd:宽窄转换的两条桥Copy Anchor Link

hexToInt 的 C 版要把 8 位的 current 和进 64 位累加值,编译器用了 movsx (符号扩展移动):把符号位(位 7)复制到目标的高 56 位。这里因为有 0x0f 掩码护体, 符号位必是 0,扩展无害;但若无掩码,movsx 与 movzx 的选择直接决定正负¹¹。 配套还有 movsxd(32 位 → 64 位符号扩展)。三条桥合记: movzx 补 0、movsx 补符号、movsxd 专管 32→64¹¹。

3. 乘法:imul 的五种形态与 rdx:rax 的「双人舞」Copy Anchor Link

主线例子第二站:decToUInt,"123" 怎么变成 123Copy Anchor Link

十进制串不能靠移位(10 不是 2 的幂),得真乘。算法:每读一个数字字符, 累加值 × 10,加上新数字¹²:

读 '1':0 × 10 + 1 = 1
读 '2':1 × 10 + 2 = 12
读 '3':12 × 10 + 3 = 123

书里有个容易被问住的观察:转换的是 unsigned int,编译器却用了有符号的 imul。 为什么?看下面指令的语义就明白¹³。

imul:一个助记符,五种形态Copy Anchor Link

imul(有符号乘法)可以带 1~3 个操作数¹⁴:

• imul reg(单操作数):被乘数在 rax(按操作数宽度取 al/ax/eax/rax), 2n 位乘积摊在两个寄存器上:8 位 → ah:al,32 位 → edx:eax,64 位 → rdx:rax;
• imul reg1, reg2(双操作数):reg1 = reg1 × reg2,n 位 × n 位只留低 n 位;
• imul reg1, reg2, imm(三操作数):reg1 = reg2 × imm(imm 限 −128~+127)。

mul(无符号乘法)只有单操作数形态,寄存器约定同上,但高位不补符号¹⁴。 两表合一句话(表 16-1):乘数在「rax 或内存」,积的低位落回 rax 系、高位落 rdx 系—— 这两个寄存器从不出现在指令的操作数里,全靠约定¹⁵。

「高位丢了」的报警器:CF 和 OFCopy Anchor Link

双/三操作数形态截断到 n 位时,若真积放得下,CF=OF=0;放不下,高位静默丢弃, CF=OF=1 报警——这是乘法版的「溢出标志」,和第 15 章 seto 正好接得上¹⁶。 回头看 decToUInt 之谜:只要积不超 32 位,imul 和 mul 的低 32 位结果完全相同 (补码的环性质),编译器顺手用形态更灵活的 imul,无必要再选 mul; 「无符号」是 main 里使用方式的事,与指令无关¹⁷。

手写版:三操作数 imul 的干净用法Copy Anchor Link

清单 16-18 的手写 decToUInt 展示了最顺手的一式:imul ecx, ecx, DECIMAL ——累加值在 ecx,乘 10,结果回 ecx,一行搞定,无需碰 rdx:rax¹⁸。

4. 除法:div/idiv 的隐式约定与符号的坑Copy Anchor Link

主线例子第三站:intToUDec,246 怎么变回 "246"Copy Anchor Link

除法是乘法的逆运算,但多了余数这个「副产品」。C 版 intToUDec 的算法: 反复 digit = theInt % 10(余数,即最低位数字)、theInt /= 10(砍掉最低位), 数字逆序生成后再整体反转¹⁹。汇编版(清单 16-24)利用了一个关键事实: 一次 div 同时产出商和余数——商在 eax、余数在 edx,% 和 / 两个 C 运算符 背后是同一指令²⁰。

246 ÷ 10:商 24(eax),余 6(edx)→ '6' 入串
 24 ÷ 10:商  2,      余 4      → '4' 入串
  2 ÷ 10:商  0,      余 2      → '2' 入串
商为 0,停;串是逆序的 "642",反转 → "246"

div / idiv:被除数天生是 2n 位Copy Anchor Link

除法指令永远拿一个 2n 位被除数除以 n 位除数:32 位除法里,被除数是 edx:eax 拼成的 64 位(edx 高 32 位 + eax 低 32 位),除数是指令的操作数; 商落 eax,余数落 edx——又是两个不出现在操作数里的寄存器(表 16-2)²¹。

经典事故由此而来:除之前必须按语义填满高位。

• div(无符号):把 edx 清零(mov edx, 0 或更省事的 xor edx, edx);
• idiv(有符号):要把符号位扩展进 edx——cdq 指令(eax → edx:eax 符号扩展, 同族还有 cbw/cwd/cqo,表 16-3)。忘了这步,−10 会被当成 0x00000000fffffff6 = 4294967286 来除,结果天差地别²²。

两个附加条款:除数为 0、或商放不进目标寄存器,会触发异常(第 21 章细讲, 表现是操作系统一句没头没尾的错误消息杀掉程序);除完后所有标志位未定义, 别指望它们²¹。

有符号除法的语言地雷:C vs PythonCopy Anchor Link

指令只管向零截断;「负的商怎么取整」是语言政策,各语言不同。C:-27/4 = -6 (向零),余数 −3(随被除数);Python:-27//4 = -7(向下取整),余数 1(随除数)。 两者都满足 r = a − b×q,截断方向不同,余数的符号就跟着不同(表 16-4 四行对照)²³。 作者的设计心得原话级别实用:「我在设计算法时尝试避免有符号除法, 并在计算结果后调整符号」——避开这个地雷场的最省事实践²⁴。

尾声:除以常数的魔法Copy Anchor Link

书里最后提了一笔优化界的经典技巧:除以 10 可以改写成 x/10 = (x × (2^n/10)) >> n——乘加移代替除法,因为移位远比除法快。 细节超出本书,但建议用 -O1 编译 intToUDec 自己看²⁵。 这是「读懂编译器输出能白捡优化知识」的又一实证。

判断(我们的,不是书里的): 本章所有指令家族有个共同的教学法价值: 「隐式寄存器约定」是 x86 的传统艺能——mul/div 用 rdx:rax、 移位用 cl、字符串指令(本书未讲)用 rsi/rdi/rcx。 读懂这类代码的钥匙从来不是背操作数,而是背「谁和谁搭档、谁从不出现在操作数里」。 如果错,会错在: 这套约定是 x86 的历史包袱,ARM/RISC-V 的乘除干净得多 (显式三操作数,无隐式配对)——以 x86 学概念时,别把「隐式约定」当成计算机的常态。

判断(我们的,不是书里的): decToUInt/intToUDec 这对往返函数, 是全书最被低估的主线例子——它把第 2 章(ASCII/位模式)、第 3 章(算术)、 第 13 章(循环)、本章(掩码/移位/乘除)全部串成一条线,而且每个程序员每天都在用 (printf/scanf 内部就是这套)。学会这两百行,胜过背十张指令表。 如果错,会错在: 真实标准库的转换函数要处理溢出、空白、符号、locale 等 大量边界,教学版一概省略——拿它当「完整实现」会摔得很惨,当「机制演示」则刚刚好。

5. 作者的判断与证据Copy Anchor Link

6. 边界与局限Copy Anchor Link

• 只覆盖整数乘除。 浮点乘除在第 19 章(SSE2),且本书不展开精度问题。
• 单操作数 mul 的高位语义只讲到「不扩符号」,双倍宽度乘积的实际用途(大数乘法) 没展开;idiv 的溢出异常只说「第 21 章」。
• 除以常数的魔法数优化只给式子不给推导——这是编译器构造的深水区, 想深入要看 Hacker's Delight 类文献(补充,不在书里)。
• 教学版转换函数不查输入合法性(非数字字符会算出垃圾),真实工程必须加校验。

7. 可带走的Copy Anchor Link

1. AND 掩码:0 抹除、1 通过;置位用 OR、反转用 XOR——一张掩码三手法;
2. 大小写转换 = & 0xdf(或 | 0x20 转小写),不用判断、不用减法;
3. 左移乘 2、右移除 2;sar 保号(填最高位副本)、shr 填 0;
4. 进制转换的通用骨架:每读一字符 → 清成数值(掩码)→ 累加值腾位(移位或 ×radix)→ 并入;
5. movzx 补 0 / movsx 补符号 / movsxd 32→64——宽窄转换三条桥;
6. imul 五种形态:单操作数摊 rdx:rax,双/三操作数留低 n 位;mul 只有单操作数;
7. 乘积超宽时 CF=OF=1 报警——编译器不替你查,乘大数前想想宽度;
8. div/idiv:被除数 2n 位(edx:eax),商 eax、余数 edx,操作数只写除数;
9. div 前 xor edx, edx;idiv 前 cdq(或 cbw/cwd/cqo)——忘了必错;
10. C 整数除法向零截断、余数随被除数;Python 向下取整、余数随除数——混用语言时先想这行;
11. 能避开有符号除法就避开,算完再调符号;
12. 除以常数可被编译器改写成乘+移位;想看就 -O1 再读汇编。

8. 原文地图Copy Anchor Link