前置知识: 计算机基础

数据表示与运算

6 min中级

数据表示与运算：数值编码、浮点标准、定点运算、溢出检测与校验码

1. 数值编码

1.1 原码

最高位为符号位（0正1负），其余位为绝对值：

[X]原={X0≤X<2n−12n−1+∣X∣−2n−1<X≤0[X]_{\text{原}} = \begin{cases} X & 0 \leq X < 2^{n-1} \\ 2^{n-1} + |X| & -2^{n-1} < X \leq 0 \end{cases}

8 位原码范围：−127∼+127-127 \sim +127，0 有两种表示（+0 和 -0）。

1.2 反码

正数与原码相同，负数符号位为1，数值位按位取反：

[X]反={XX≥02n−1+XX<0[X]_{\text{反}} = \begin{cases} X & X \geq 0 \\ 2^n - 1 + X & X < 0 \end{cases}

1.3 补码

计算机中最常用的整数表示法：

[X]补={XX≥02n+XX<0[X]_{\text{补}} = \begin{cases} X & X \geq 0 \\ 2^n + X & X < 0 \end{cases}

关键性质：

  • 补码 = 反码 + 1（负数）
  • 0 的补码唯一
  • nn 位补码范围：−2n−1∼2n−1−1-2^{n-1} \sim 2^{n-1}-1
  • 补码加减法统一为加法

快速求补码：从最低位到第一个1保持不变，其余位取反。

1.4 移码

补码的符号位取反，用于浮点数的阶码表示：

[X]移=2n−1+X[X]_{\text{移}} = 2^{n-1} + X

移码保持了数值的大小顺序，便于比较大小。

2. 定点运算

2.1 补码加法

[X+Y]补=[X]补+[Y]补[X+Y]_{\text{补}} = [X]_{\text{补}} + [Y]_{\text{补}}

符号位参与运算，进位自然丢弃。

2.2 补码减法

[X−Y]补=[X]补+[−Y]补[X-Y]_{\text{补}} = [X]_{\text{补}} + [-Y]_{\text{补}}

其中 [−Y]补[-Y]_{\text{补}} 为 [Y]补[Y]_{\text{补}} 的各位取反加1。

2.3 溢出检测

单符号位法：

V=As⊕Bs⊕SsV = A_s \oplus B_s \oplus S_s

  • V=0V = 0：无溢出
  • V=1V = 1：溢出

双符号位法（变形补码）：

  • Ss1Ss2=00S_{s1}S_{s2} = 00：结果为正，无溢出
  • Ss1Ss2=01S_{s1}S_{s2} = 01：正溢出
  • Ss1Ss2=10S_{s1}S_{s2} = 10：负溢出
  • Ss1Ss2=11S_{s1}S_{s2} = 11：结果为负，无溢出

2.4 定点乘法

原码一位乘法：

  • 符号位单独处理：Ps=As⊕BsP_s = A_s \oplus B_s
  • 数值部分：被乘数加或不加（根据乘数位），然后右移

补码一位乘法（Booth 算法）：

根据乘数末两位的差值决定操作：

YiY_iYi−1Y_{i-1}操作
00右移一位
01加 [X]补[X]_{\text{补}}，右移一位
10加 [−X]补[-X]_{\text{补}}，右移一位
11右移一位

3. 浮点数表示

3.1 IEEE 754 标准

浮点数格式：

(−1)S×1.M×2E−bias(-1)^S \times 1.M \times 2^{E-\text{bias}}

参数单精度（32位）双精度（64位）
符号位 S1 位1 位
阶码 E8 位11 位
尾数 M23 位52 位
偏置值1271023
阶码范围1~2541~2046
规格化范围2−126∼21272^{-126} \sim 2^{127}2−1022∼210232^{-1022} \sim 2^{1023}

3.2 特殊值

阶码 E尾数 M含义
全0全0±0
全0非零非规格化数
全1全0±∞
全1非零NaN

3.3 非规格化数

当阶码全0、尾数非零时，表示非规格化数：

(−1)S×0.M×21−bias(-1)^S \times 0.M \times 2^{1-\text{bias}}

非规格化数填补了0和最小规格化数之间的间隙，实现渐进下溢。

3.4 浮点精度

单精度有效位数约 7 位十进制，双精度约 15~16 位十进制。

机器 epsilon：

ϵsingle=2−23≈1.19×10−7\epsilon_{\text{single}} = 2^{-23} \approx 1.19 \times 10^{-7}

ϵdouble=2−52≈2.22×10−16\epsilon_{\text{double}} = 2^{-52} \approx 2.22 \times 10^{-16}

4. 浮点运算

4.1 浮点加减法

  1. 对阶：小阶向大阶看齐，尾数右移
  2. 尾数加减：对阶后的尾数相加减
  3. 规格化：左规或右规使尾数满足 1.M1.M 格式
  4. 舍入：按舍入模式处理超出位
  5. 溢出判断：检查阶码是否溢出

4.2 舍入模式

模式说明
就近舍入舍入到最接近的可表示值（默认）
向0舍入截断
向+∞舍入向上取整
向-∞舍入向下取整

就近舍入的”银行家舍入”规则：当恰好在中间时，舍入到偶数。

4.3 浮点乘除法

乘法：

(−1)S1⊕S2×(1.M1×1.M2)×2(E1+E2−bias)(-1)^{S_1 \oplus S_2} \times (1.M_1 \times 1.M_2) \times 2^{(E_1+E_2-\text{bias})}

除法：

(−1)S1⊕S2×(1.M1÷1.M2)×2(E1−E2+bias)(-1)^{S_1 \oplus S_2} \times (1.M_1 \div 1.M_2) \times 2^{(E_1-E_2+\text{bias})}

5. 校验码

5.1 奇偶校验

在数据位后添加1位校验位，使1的个数为奇数（奇校验）或偶数（偶校验）。

  • 只能检测奇数个错误
  • 不能纠正错误
  • 检错率：1−2−n1 - 2^{-n}（对于 nn 位数据）

5.2 海明码（Hamming Code）

在数据位之间插入 rr 个校验位，满足：

2r≥m+r+12^r \geq m + r + 1

其中 mm 为数据位数，rr 为校验位数。

校验位位置：放在 2i2^i 的位置（第1、2、4、8…位）。

编码步骤：

  1. 确定校验位数 rr
  2. 将数据位填入非 2i2^i 位置
  3. 每个校验位覆盖其位置二进制表示中对应位为1的所有位
  4. 计算各校验位的值

纠错能力：SEC-DED（单纠错双检错）

5.3 CRC 循环冗余校验

将数据视为多项式，用生成多项式除取余数作为校验码。

编码过程：

  1. 数据 M(x)M(x) 左移 rr 位（rr 为生成多项式阶数）
  2. 用生成多项式 G(x)G(x) 模2除法取余数 R(x)R(x)
  3. 发送 M(x)⋅xr+R(x)M(x) \cdot x^r + R(x)

检错能力：

  • 所有单比特错误
  • 所有双比特错误（生成多项式包含 (x+1)(x+1) 因子时）
  • 所有奇数个比特错误
  • 所有长度 ≤r\leq r 的突发错误

5.4 校验码对比

校验码冗余位检错能力纠错能力应用
奇偶校验1位奇数个错无内存ECC基础
海明码⌈log⁡2(m+r+1)⌉\lceil\log_2(m+r+1)\rceil2位错1位错ECC内存
CRCrr位突发错误无（可配合重传）网络通信

自检

  • 遮住上面的表格重推一遍：十进制 -5 的 8 位补码是什么？（提示：先写原码，取反加一。）
  • 补码世界里为什么只有一个 0？移码又为什么偏爱「平移到无符号」的表示？
  • 不看表格，说出海明码与 CRC 各自的强项——一个能纠错、一个擅检突发错误，应用场景分别在哪？