补码运算

1. 补码的定义

补码是计算机中最常用的有符号整数表示方法。对于 n 位二进制数（含 1 位符号位）：

• 正数的补码：与原码相同，符号位为 0。
• 负数的补码：方法一（定义法）$[x]_补 = 2^n + x$（$-2^{n-1} \le x < 0$）；方法二（取反加一）符号位不变、数值位各位取反、末位加 1；方法三从右向左找到第一个 1，该位及其右边不变，左边各位取反。

补码的表示范围（n 位含符号位）：最大正数 $2^{n-1} - 1$，最小负数 $-2^{n-1}$，共 $2^n$ 个数（+0 与 -0 统一为全 0）。

2. 补码加法规则

$$[x+y]_补 = [x]_补 + [y]_补 \pmod{2^n}$$

1. 将两个操作数转换为补码。
2. 直接做二进制加法（包含符号位一起运算）。
3. 舍弃最高位的进位（模运算）。
4. 判断是否溢出。

3. 补码减法规则

$$[x-y]_补 = [x]_补 + [-y]_补 \pmod{2^n}$$

减法转化为加法，关键是求 $[-y]_补$（变补/取补操作）：将 $[y]_补$ 的所有位（包括符号位）取反，末位加 1。注意：变补是对整个补码（含符号位）操作，不同于原码求补码。

4. 溢出判断

溢出发生在：两个同号数相加，结果的符号与操作数符号不同。

条件	溢出情况
正 + 正 = 负	正溢出（上溢）
负 + 负 = 正	负溢出（下溢）
正 + 负	不可能溢出

方法一 · 单符号位法：$V = A_s B_s \overline{S_s} + \overline{A_s}\, \overline{B_s} S_s$，其中 $A_s, B_s$ 为操作数符号位，$S_s$ 为结果符号位。

方法二 · 双符号位法（变形补码/模 4 补码）：两位符号位 00 正、11 负。

双符号位结果	含义
00	正数，无溢出
01	正溢出（上溢）
10	负溢出（下溢）
11	负数，无溢出

溢出判断：$V = S_{s1} \oplus S_{s2}$（两个符号位不同即溢出）。

方法三 · 进位判断法：设符号位产生的进位为 $C_s$，最高数值位产生的进位为 $C_1$：

$$V = C_s \oplus C_1$$

• $C_s = 0, C_1 = 1$ → 正溢出；$C_s = 1, C_1 = 0$ → 负溢出；$C_s = C_1$ → 无溢出。

概念	说明
原码	符号位 + 绝对值，正负数表示对称
反码	正数同原码；负数符号位不变，数值位取反
补码	正数同原码；负数 = 反码 + 1
移码	补码的符号位取反，用于浮点数阶码
变补	由 $[y]_补$ 求 $[-y]_补$，所有位取反加 1
模	补码运算溢出的自然丢弃值，n 位定点整数模为 $2^n$
溢出	运算结果超出了补码能表示的范围
上溢/正溢出	正数 + 正数结果为负，超出最大正数
下溢/负溢出	负数 + 负数结果为正，超出最小负数

操作	时间复杂度	硬件实现
补码加法	O(n)，n 为字长	并行加法器（行波进位/超前进位）
补码减法	O(n)	加法器 + 变补电路（取反 + 1）
变补操作	O(n)	取反器 + 加 1（可复用加法器）
溢出判断	O(1)	仅需最高位进位比较，硬件开销极小

• 变补 vs 求负数的补码：变补对整个补码（含符号位）取反加 1；原码求补码只对数值位取反加 1、符号位保留。两者不同！
• 补码中 0 的表示唯一：+0 与 -0 的补码都是全 0。
• 最小负数没有对应正数：8 位补码中 -128 表示为 10000000，但 +128 无法表示。
• 舍弃最高进位：补码加法的进位自然丢弃，这不是溢出。
• 溢出 vs 进位：溢出是有符号数概念，进位是无符号数概念，两者独立。
• 双符号位法数据位少一位：有效数据位减少一位。

1. 补码加减法统一为加法：$[x \pm y]_补 = [x]_补 + [\pm y]_补 \pmod{2^n}$。
2. 溢出的本质：结果超出 n 位补码表示范围 $[-2^{n-1}, 2^{n-1}-1]$。
3. 溢出只可能发生在同号数相加时。
4. 三种溢出判断方法等价：单符号位、双符号位、进位异或。
5. 补码中符号位参与运算，不需要单独处理符号。
6. n 位补码可表示 $2^n$ 个值，范围 $[-2^{n-1}, 2^{n-1}-1]$。
7. 模运算性质：加法结果取模后自动正确（除溢出情况）。