溢出和进位是一回事吗?
初学二进制算术的人几乎都在这里绊过一下:两个数相加,最高位顶出一个 1,有人喊「进位了」,也有人喊「溢出了」,听起来像同一件事。硬件却老老实实给出两个独立的标志位——进位标志 CF(Carry Flag)和溢出标志 OF(Overflow Flag),它们在同一笔加法上各自生成、互不代班。二进制加法与进位讲过进位怎样逐位传播,为什么现代芯片几乎只用补码?给过补码溢出的判据和两笔同号算例,本篇把视角拉到标志位本身:先把两个标志的服务对象和判据彻底分开,再用四笔 4 位算例证明它们的取值两两无关,最后落到减法借位、C 语言语义和查表决策上。
本文要回答的问题
- 进位和溢出描述的到底是不是同一种「装不下」?
- CF 和 OF 各自由加法器的哪根线生成,判据能不能手算复核?
- 同一笔加法有没有可能「进位但不溢出」或「溢出但不进位」?
- 做减法时 CF 为什么又叫借位,不同指令集的极性约定差在哪?
- 写 C 程序时碰到无符号回绕和有符号溢出,编译器为什么区别对待?
一、两个标志,服务两套数的解释约定
n 位容器里只有一个位模式,比如 4 位的 1001,既可解释成无符号数 9,也可解释成补码 −7。加法器做的事与解释无关:按位相加、逐位进位、留下低 n 位。但「结果对不对」依赖解释——无符号合法范围是 0 到 2ⁿ−1,补码合法范围是 −2ⁿ⁻¹ 到 +2ⁿ⁻¹−1。范围不同,越界事件就要分开报告,这就是 CF 与 OF 并存的根本原因。
进位标志 CF 为无符号数服务。无符号加法的真值和一旦达到 2ⁿ,容器装不下,最高位向外顶出一个进位,CF 置 1;留在容器里的低 n 位仍然是真值对 2ⁿ 取模的结果。4 位下 1000 + 1001 = 10001,无符号真值是 17,低 4 位留 0001,丢掉的那个 1 就由 CF 记录。
溢出标志 OF 为有符号补码数服务。它不关心最高位有没有向外进位,只关心按补码解释的真值是否落在 −2ⁿ⁻¹ 到 +2ⁿ⁻¹−1 之内。4 位下 0110 + 0011 = 1001,没有任何向外进位,CF 为 0,但补码视角是 +6 加 +3 得到 −7,真值 +9 越过了 +7 上界,OF 置 1。
| 对比维度 | 进位标志 CF | 溢出标志 OF |
|---|---|---|
| 服务对象 | 无符号整数 | 有符号补码整数 |
| 4 位合法范围 | 0 ~ 15 | −8 ~ +7 |
| 触发事件 | 真值和 ≥ 16,最高位向外进位 | 真值超出 −8 ~ +7 |
| 直接观测点 | 加法器最高位的进位输出 | 符号位进位输入与输出的关系 |
| 结果寄存器 | 低 n 位为真值模 2ⁿ | 低 n 位为错误补码,需丢弃或扩位重算 |
读这张表抓住一句话:CF 回答「无符号视角丢没丢高位」,OF 回答「有符号视角结果还能不能信」。同一个加法器、同一份位模式,因为解释约定不同,挂出两块各自独立的牌子。
二、两个判据:一根出线对一个异或门
CF 的判据直接得近乎平凡:最高位那一级的进位输出是 1,CF 就是 1,不需要任何额外组合逻辑。减法稍特殊,通过 A + (~B) + 1 实现,x86 语义下把进位输出取反作为借位报告,下一节细讲。
OF 的判据在补码选型篇已经推导过:符号位的进位输入与进位输出做异或,结果为 1 即溢出。直觉上,两个正数相加却得到负数,或者两个负数相加却得到正数,唯一的机制就是符号位被低位来的进位「顶翻」或本该顶翻却没顶翻,这恰好表现为进出不一致。等价的说法是双符号位法(变形补码):用两位符号位参与运算,结果为 01 表示正向上溢、10 表示负向下溢,与异或判据在硬件上等价。还有一个好用的旁路判据:只有两个同号数相加才可能溢出,异号相加的真值必落在两操作数之间,OF 恒为 0。
两个标志的完整画像放在一张对照卡里,写代码和看波形时可以直接查。
读这张卡先分服务对象,再记判据形态:CF 是一根出线的直接扇出,OF 是符号位进出两个信号喂给一个异或门。门级电路怎样从全加器接线生成这两个标志,由加法器与算术电路:从半加器到 ALU展开,状态寄存器怎样统一收纳 CF、OF、ZF、SF,则在ALU 标志位与状态寄存器里讲。
三、2×2 四笔算例:证明两个标志两两无关
道理讲完,最硬的证据是把四种取值组合各算一遍。下面固定 4 位字长(无符号 0~15、补码 −8~+7),每笔逐位推演并做十进制回算。
组合一,CF=0 且 OF=0,两视角都正确,计算 3 + 2。
0011 (无符号 3,补码 +3)
+ 0010 (无符号 2,补码 +2)
-------
0101
最高位无向外进位 → CF=0
符号位进位输入=0、进位输出=0,异或=0 → OF=0
回算:无符号 3+2=5,补码 +3+(+2)=+5,均在范围内组合二,CF=1 但 OF=0,无符号丢了高位、有符号结果依然正确,计算 10 + 7。
1010 (无符号 10,补码 −6)
+ 0111 (无符号 7, 补码 +7)
-------
10001 容器只留低 4 位 0001
最高位向外进位 1 → CF=1
逐位:b1 产生进位,b2 消化后进位继续传到 b3,
符号位进位输入=1、进位输出=1,异或=0 → OF=0
回算:无符号 10+7=17,模 16 得 1,与 0001 吻合;
补码 −6+(+7)=+1,在 −8~+7 内,结果正确这一笔是破除「进位即溢出」直觉的关键:位模式 1010 在补码眼里是负数 −6,一正一负相加,真值 +1 安稳落在范围内,OF 理所当然为 0;可在无符号眼里 10 加 7 实打实越过了 16,CF 必须置 1。两个标志各说各话,而且都说对了。
组合三,CF=0 但 OF=1,没有向外进位、有符号却翻车,计算 6 + 3。
0110 (无符号 6,补码 +6)
+ 0011 (无符号 3,补码 +3)
-------
1001 按补码解释是 −7
最高位无向外进位 → CF=0
逐位:b1、b2 连续产生进位,低位进位顶进符号位,
符号位进位输入=1、进位输出=0,异或=1 → OF=1
回算:无符号 6+3=9,未超 15,CF 确为 0;
补码 +6+(+3)=+9,越过 +7 上界,补码结果 −7 作废组合四,CF=1 且 OF=1,两套视角同时越界,计算 8 + 9。
1000 (无符号 8,补码 −8)
+ 1001 (无符号 9,补码 −7)
-------
10001 容器只留低 4 位 0001
最高位向外进位 1 → CF=1
符号位进位输入=0、进位输出=1,异或=1 → OF=1
回算:无符号 8+9=17,模 16 得 1;
补码 −8+(−7)=−15,低于 −8 下界,补码结果 +1 作废四笔凑齐一张 2×2 全表,每个格子都有真实算例支撑,这就是「两个标志两两无关」的完整证据。
| 组合 | 算例(4 位) | 位模式运算 | CF | OF | 两个视角的回算 |
|---|---|---|---|---|---|
| 都不置位 | 3 + 2 | 0011+0010=0101 | 0 | 0 | 无符号得 5;补码 +5,均正确 |
| 只进位 | 10 + 7 | 1010+0111=10001 | 1 | 0 | 无符号 17 回绕为 1;补码 −6+7=+1 正确 |
| 只溢出 | 6 + 3 | 0110+0011=1001 | 0 | 1 | 无符号得 9 正确;补码 +9 越上界 |
| 都置位 | 8 + 9 | 1000+1001=10001 | 1 | 1 | 无符号 17 回绕为 1;补码 −15 越下界 |
四、减法里 CF 兼任借位:极性是 ISA 约定
减法在补码机器上复用加法通路:A − B = A + (~B) + 1。标志照常生成,但 CF 的语义切换成借位。以 x86 的 SUB 为例,CF=1 表示无符号视角下被减数不够减、发生了借位。硬件实现上,加法器最高位的进位输出恰好与借位反相,所以 x86 把该进位输出取反后上报 CF。手算验证 3 − 5:
0011 − 0101 = 0011 + (~0101) + 1 = 0011 + 1011
0011
+ 1011
-------
1110 最高位进位输出 = 0,取反 → CF=1(发生借位)
符号位进位输入=0、输出=0,异或=0 → OF=0
回算:无符号 3−5 = −2,模 16 得 14,与 1110 吻合;
补码视角 1110 即 −2,在范围内,OF=0借位极性不是跨平台统一的。x86 约定 CF=1 为发生借位;ARM 的 SUB 系列让 C 标志在无借位时置 1,极性相反;RISC-V 干脆不设条件标志,比较结果写进通用寄存器供跳转消费。移植底层汇编时先查该 ISA 对借位的明文约定,不要把 x86 习惯带过去。多精度大数运算统一依赖这个标志:x86 的 ADC(带进位加)和 SBB(带借位减)把低字 CF 接进高字的进位输入,任意长度的整数加减就靠它一字一字拼起来。
五、软件视角:一个是未定义行为,一个是良定义回绕
标志位的分工向上传导到高级语言,最典型的是 C 语言对两类越界的不对称处理。
无符号整数溢出在 C 标准里根本不叫溢出,而是良定义的模 2ⁿ 回绕:uint8_t 容器里 255u + 1u 的结果确定为 0,CF 记录的正是这次回绕。大量惯用法建立在这条保证之上,比如用无符号回绕实现环形缓冲区下标、用 (size_t)-1 表达最大值。
有符号整数溢出则是未定义行为(Undefined Behavior):INT_MAX + 1 产生什么结果、是否截断、是否触发陷阱,标准统统不承诺。编译器据此做激进优化——既然有符号溢出不可能发生,i + 1 > i 可被视为恒真,循环边界分析和向量化都依赖这个假设;真写出溢出代码,优化版行为可能与调试版完全不同。常见对策包括 GCC 的 -fwrapv(按补码回绕定义)、-ftrapv(溢出落陷阱),或用 __builtin_add_overflow 在运算前显式探测;若要求越界时钳到边界而非回绕,则属于饱和运算,见饱和运算与限幅:溢出的另一种处理方式。
| 软件场景 | 无符号回绕 | 有符号溢出 |
|---|---|---|
| C 标准定性 | 良定义,结果模 2ⁿ | 未定义行为 |
| 对应硬件标志 | CF 置 1 | OF 置 1,但标准不保证可观测 |
| 编译器态度 | 保留回绕语义,可被惯用法依赖 | 假设永不发生,据此优化 |
| 典型应对 | 环形缓冲、模运算直接用 | 扩位、边界检查、内建探测或 -fwrapv |
六、什么时候查哪个标志:一张决策表
写汇编或调试 ALU 时,按「数据被解释成哪类数」选标志,再配合零标志 ZF 处理相等分支。x86 的条件跳转指令已把这些组合固化在助记符里,查表即可对号入座。
| 任务场景 | 查的标志 | 判定与典型指令(x86) |
|---|---|---|
| 无符号加法是否丢高位 | CF | CF=1 表示真值 ≥ 2ⁿ,需用高位字补救 |
| 无符号比较 a < b | CF | 相减后 CF=1 即小于,JB/JC 跳转 |
| 无符号比较 a > b | CF + ZF | CF=0 且 ZF=0,JA 跳转 |
| 有符号加法结果是否有效 | OF | OF=1 表示补码结果不可信 |
| 有符号比较 a < b | OF 与 SF | OF 异或 SF 为 1 即小于,JL 跳转 |
| 有符号比较 a > b | OF、SF、ZF | OF 异或 SF 为 0 且 ZF=0,JG 跳转 |
| 相等判断 | ZF | 相减为零则 ZF=1,JE 跳转 |
| 多字长大数加减 | CF | ADC/SBB 逐字传递进位或借位 |
表中最容易记混的是有符号小于判定:不能只看符号位 SF,因为溢出会翻转结果符号,必须用 SF 与 OF 的异或还原真实大小关系。这也再次说明 OF 与 CF 是两条平行的语义轨道——无符号分支走 CF,有符号分支走 OF 加 SF,谁也不替代谁。
这一篇在知识体系里的位置
本篇回答「进位和溢出是不是一回事」,是数制与逻辑代数阶段承接补码三篇的标志位专题。进位的逐位传播机制来自二进制加法与进位,三种编码对负数的表示与补码「取反加一」来自原码、反码、补码到底差在哪?,补码加减法通路与溢出判据的选型论证来自为什么现代芯片几乎只用补码?,本篇新增的是无符号视角、CF 与 OF 的 2×2 独立组合以及软件语义。向电路层下沉,两个标志的门级生成在加法器与算术电路:从半加器到 ALU,标志在状态寄存器中的收纳与条件跳转消费在ALU 标志位与状态寄存器,溢出后钳位而非回绕的路线在饱和运算与限幅;编码家族全景见数制与编码:二进制、补码、格雷码与奇偶校验。
总结
进位和溢出不是一回事:CF 为无符号数服务,盯住最高位的向外进位,报告真值是否越过 0 到 2ⁿ−1;OF 为有符号补码数服务,由符号位进位输入与进位输出异或生成,报告真值是否超出 −2ⁿ⁻¹ 到 +2ⁿ⁻¹−1。同一笔加法在同一个加法器上并行挂出这两块牌子,四笔 4 位算例凑齐了它们的 2×2 全部组合——3+2 两个都不置位、10+7 只进位不溢出、6+3 只溢出不进位、8+9 两个都置位,证明二者取值两两无关。减法复用加法通路时 CF 兼任借位,但极性是指令集约定,x86 取 CF=1 为借位、ARM 措辞相反、RISC-V 不设标志,移植须查手册。到了 C 语言层,无符号回绕是良定义的模 2ⁿ 运算,有符号溢出则是未定义行为,编译器可假设它永不发生并据此优化,工程上要靠扩位、内建探测或编译选项主动设防。决策主线一句话:无符号比较与多精度拼接看 CF,有符号结果有效性与比较看 OF 并联合符号位 SF。