02 数据的表示与运算
进制转换、原码补码、浮点数、字符编码这些"地基"在 信息的表示与处理 已经讲透（重点回顾：02-原码反码补码 和 04-浮点数）。本篇只补计组特有的三块：移码、定点/浮点的硬件级运算（加法器、乘除法器怎么干活）、以及检错纠错的海明码。
一、补码的兄弟：移码
移码 = 补码的符号位取反（仅对定点整数，且用于浮点数的阶码）。
| 十进制 | 8位补码 | 8位移码 |
|---|---|---|
| -128 | 1000 0000 | 0000 0000 |
| -1 | 1111 1111 | 0111 1111 |
| 0 | 0000 0000 | 1000 0000 |
| +127 | 0111 1111 | 1111 1111 |
💡 为什么浮点阶码用移码：移码下，机器数的大小顺序 == 真值的大小顺序（无符号比较器直接比大小），浮点数对阶、比较时硬件不用管符号，一比就对。这也是 04-浮点数 里 IEEE 754 阶码有"偏置值 127"的根源——其实就是移码思想。
⚠️ 移码唯一的表示：0 = 1000 0000，没有 ±0 之分。
二、加法器：所有运算的基石
1. 一位全加器
输入两个加数位 + 低位进位，输出本位和 + 进位。逻辑上就是两个异或（求和）+ 两个与（求进位）。
2. 串行进位加法器（行波进位）
把 n 个全加器串起来，高位等低位的进位"一波一波传过去"。缺点：进位延迟逐级累积，位数越多越慢——这是串行/并行一切讨论的原点。
3. CLA 超前进位加法器（并行进位）
思路：不等着进位逐级传，直接用输入算出每一级进位。定义两个辅助函数：
- 进位生成：\(G_i = A_i \cdot B_i\)（本位俩都是 1，必然向前进位）
- 进位传播：\(P_i = A_i \oplus B_i\)（本位有一个 1，就把低位进位传上去）
于是每一位进位都能展开成输入的表达式，如 4 位加法器：
| 方案 | 延迟 | 硬件成本 |
|---|---|---|
| 串行进位（行波） | O(n)，逐级传播 | 小 |
| CLA 超前进位 | O(1)（4 位一片，位扩展时片间仍串行） | 大（门数爆炸） |
⚠️ 考点：CLA 用"增加硬件"换"减少延迟"——全加器数量不变，增加的是进位逻辑。
4. 补码加减 + 溢出判断三法
硬件只配一个加法器：减法 = 加上"取负后的补码"（全位取反 +1）。溢出判断三法（任选其一，结论相同）：
| 方法 | 判据 | 直觉 |
|---|---|---|
| ① 单符号位 | 最高数值位进位 ⊕ 符号位进位 = 1 → 溢出 | 两股进位不一致 = 侵入了符号位 |
| ② 双符号位（变形补码） | 两位符号位 01 → 正溢出，10 → 负溢出，00/11 正常 | 看符号位"越界"没有 |
| ③ 操作数符号 | 同号相加，结果符号不同 → 溢出（异号相加必不溢出） | 同号相加才可能超出绝对值范围 |
💡 例：8 位补码，(+73) + (+85)。0110 1001 + 0101 0101 = 1011 1110 → 两个正数加出了负数，溢出（真值 138 > 127）。用双符号位看：01 0111 1100… 等价地符号位进位与数值位进位不一致，判溢出。
5. ALU 与标志位
ALU（算术逻辑单元）= 组合逻辑 + 控制端（选择做算术还是逻辑运算）。它每次运算顺手吐出 4 个标志位：
| 标志 | 含义 | 判法 |
|---|---|---|
| ZF | 结果为 0 | 全 0 → 1 |
| OF | 有符号溢出 | 上述任一方法；⚠️ 硬件按补码规则判 |
| SF | 结果符号位 | 最高位是什么就是什么 |
| CF | 无符号进/借位 | 最高位向外进位（加法）或需借位（减法） |
⚠️ 408 高频坑：OF 管"有符号"，CF 管"无符号"。127 + 1 = -128 在硬件眼里 OF=1、CF=0；而 255 + 1（按 8 位）CF=1、OF=0。同一串二进制，读的人解释不同。
三、定点乘法：原码一位乘
核心思想：加法 + 右移。模拟手工竖式——从乘数最低位开始，是 1 就加被乘数、是 0 就加 0，然后整体右移一位。
先验证一个完整的例子：x = 0.1101，y = 0.1011，求 x·y（符号位单独处理：正×正=正，数值部分绝对值相乘）。
部分积 乘数 说明
00.0000 1011 初值
+ 00.1101 乘数末位=1 → +|x|
= 00.1101
→ 00.0110 1101 1 右移，移出的"1"进入乘数寄存器
+ 00.1101 末位=1 → +|x|
= 01.0011
→ 00.1001 1110 1 右移
+ 00.0000 末位=0 → +0
→ 00.0100 1111 0 右移
+ 00.1101 末位=1 → +|x|
= 01.0001
→ 00.1000 1111 1 右移（最后一次不进乘数）
结果 = 0.1000 1111
验证：0.1101 = 13/16，0.1011 = 11/16，13 × 11 = 143，143/256 = 0.55859375 = 0.10001111₂ ✅（0.10001111 = 128+8+4+2+1 = 143/256）
要点（背这 4 条）：
- 符号位单独异或处理，数值部分用绝对值
- 部分积初值 0，做 n 次"加 + 右移"
- 加法可能暂时溢出（双符号位 01），右移后恢复
- 右移是逻辑右移（绝对值运算无负数问题，高位补 0）
💡 Booth 算法（补码一位乘）概念：补码直接乘，不用先转绝对值。技巧是看"当前位 − 上一位"的差值：10 加 [−x]补、01 加 [x]补、00/11 不加，同样加法+右移 n 次。408 主要考概念和"何时加 −x"这个点。
四、定点除法：试减思想
手工竖式除法的硬件版：够减商 1、不够减商 0，然后左移。
以恢复余数法概念为例：x/y（都用绝对值），每次拿被除数（或余数）试减除数——结果为正商 1、为负商 0 并把除数加回去（恢复），然后余数左移一位再试。改进版加减交替法：余数为负就下一步直接"加除数"，省去恢复步骤。
⚠️ 408 只需掌握：① 原码除法符号单独异或；② 加减交替法的"负了就加回去"直觉；③ 除法是"左移"，乘法是"右移"——方向别记反。
五、浮点运算：对阶 → 尾数 → 规格化
04-浮点数 已讲格式与舍入，这里补 408 喜欢的对阶与规格化步骤：
- 对阶：小阶向大阶看齐（小阶的尾数右移——左移会丢高位，右移只丢低位）
- 尾数加减：用补码加法器直接算
- 规格化：结果不是 ±1.x 形式就移
- 右规：尾数溢出（双符号位 01/10）→ 尾数右移 1 位，阶码 +1
- 左规：尾数是 0.0xxx 或 1.1xxx → 尾数左移，阶码减 1
- 舍入：0 舍 1 入 / 恒置 1
- 溢出判断：看阶码溢出（阶码上溢 → 真溢出；阶码下溢 → 按机器零处理）
⚠️ 一句话考点：浮点溢出看阶码，尾数溢出只算"需要右规"——这是浮点和定点溢出最大的不同。
六、海明码：会检错也能纠错
原理
在数据位中插入 k 个校验位（放在 2 的幂次位置：1、2、4、8…），每组校验位负责一组位置——出错时把各组校验结果拼起来，直接得到出错位置的下标（"syndrome 校验子"）。
位数关系需满足：\(2^r \ge n + r + 1\)（n 个数据位、r 个校验位）。纠 1 位错；若再加 1 位全校验位可"纠 1 检 2"。
手算例题（数据 1010）
4 位数据 1010 放入 7 位海明码的 3、5、6、7 号位（按从左到右顺序），校验位占 1、2、4 号位：
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 角色 | P1 | P2 | D1=1 | P4 | D2=0 | D3=1 | D4=0 |
（数据 1010 依次填入 3、5、6、7 号位：D1=1, D2=0, D3=1, D4=0）
- P1 管位置二进制的第 1 位是 1 的位置：1, 3, 5, 7 → 0⊕1⊕0⊕0 = 1
- P2 管第 2 位是 1 的位置：2, 3, 6, 7 → 0⊕1⊕1⊕0 = 0
- P4 管第 3 位是 1 的位置：4, 5, 6, 7 → 0⊕0⊕1⊕0 = 1
（校验位本身填 0 参与运算，算出的值再写回对应位置。）
所以 码字 = P1 P2 D1 P4 D2 D3 D4 = 1 0 1 1 0 1 0，即 1011010 ✅
验错演示
假设第 5 位在传输中翻转（1→0），收到 1010110。校验：
- S1（管 1,3,5,7）：1⊕1⊕1⊕0 = 1
- S2（管 2,3,6,7）：0⊕1⊕1⊕0 = 0
- S4（管 4,5,6,7）：1⊕1⊕1⊕0 = 1
S4 S2 S1 = 101₂ = 5 → 第 5 位错了，翻回来即纠出 ✅（校验子全 0 = 无错）
⚠️ 考点：① 海明码是纠错码（CRC 是检错码，见 03-数据链路层）；② 校验位在 2^i 位置；③ syndrome 拼出来就是错位编号；④ 数据 n 位最少校验位满足 2^r ≥ n + r + 1（如 n=4 → r=3；n=8 → r=4，验证 2⁴=16 ≥ 8+4+1=13 ✅）。
七、奇偶校验与 CRC（一句话回链）
- 奇/偶校验：加 1 位让 1 的个数为奇/偶。只能检奇数个错，不能纠错，成本最低
- CRC 循环冗余：模 2 除法求余数做校验，检错强但只检不纠——详见 数据链路层 的完整手算例题
- 海明/CRC/奇偶是一家人：冗余换可靠——传更多位，换检出/纠正错误的能力
八、盲点自测
- 移码和补码的关系？浮点阶码为什么用移码？（符号位取反；保持大小顺序可直接比较）
- CLA 比串行进位快在哪？代价是什么？（进位并行生成，不逐级传；硬件门数增加）
- OF 和 CF 分别管什么？
0x7F + 0x01的 OF/CF？（OF 有符号溢出、CF 无符号进位；OF=1, CF=0） - 原码一位乘：部分积做 n 次"______ + ______"？（加法 + 右移）
- 浮点运算结果什么时候"真溢出"？（阶码上溢；尾数溢出只是右规）
- 数据 1010 的 7 位海明码是多少？收到 1011110 时错在哪？（1011010；syndrome=111=7，第 7 位错——D4 翻转）
九、动手玩
# 用 Python 验证海明码编码与纠错
def hamming_encode(data): # data: 4 位字符串
bits = [None] * 8 # 1..7 号位
d = iter(data)
for i in (3, 5, 6, 7):
bits[i] = int(next(d))
bits[1] = bits[3] ^ bits[5] ^ bits[7]
bits[2] = bits[3] ^ bits[6] ^ bits[7]
bits[4] = bits[5] ^ bits[6] ^ bits[7]
return ''.join(str(b) for b in bits[1:])
print(hamming_encode('1010')) # → 1011010
# 纠错：把收到 7 位按位分组算 syndrome
def hamming_syndrome(bits):
b = [0] + [int(c) for c in bits] # 1-based
s1 = b[1] ^ b[3] ^ b[5] ^ b[7]
s2 = b[2] ^ b[3] ^ b[6] ^ b[7]
s4 = b[4] ^ b[5] ^ b[6] ^ b[7]
return s4 * 4 + s2 * 2 + s1 # 0 = 无错，否则为错位编号
print(hamming_syndrome('1010110')) # → 5
💬 评论