第20章 数据编码

20.1 机器数与真值

• 机器数：一个数在计算机中的二进制表示形式，包含符号位和数值位。通常用最高位表示符号（0 为正，1 为负），其余位表示数值的绝对值。
  • 例：8 位机器数 00000101 和 10000101。
• 真值：机器数对应的实际数值。
  • 00000101 的真值是 +5，10000101 的真值是 −5。

20.2 原码（True Form）

20.2.1 定义

• 正数：符号位为 0，数值位为该数二进制绝对值。
• 负数：符号位为 1，数值位为该数绝对值的二进制。

20.2.2 表示方法（以 8 位为例：1 位符号位 + 7 位数值位）

• 真值 +5 的原码：00000101
• 真值 −5 的原码：10000101
• 0 有两种形式：+0 = 00000000，−0 = 10000000

20.2.3 特点

1. 直观、与真值对应简单；
2. 加减法复杂（需先判符号）；
3. 存在两种 0 的编码，浪费一个状态。

20.3 反码（One's Complement）

20.3.1 定义

• 正数：反码 = 原码。
• 负数：符号位保持 1，数值位按位取反（0 变 1，1 变 0）。

20.3.2 表示方法（8 位）

• +5：原码 00000101，反码同为 00000101；
• −5：原码 10000101 → 数值位取反 → 反码 11111010；
• 0 仍有两种形式：+0 = 00000000，−0 = 11111111。

20.3.3 特点

1. 正数原反码一致；
2. 仍存在双零问题；
3. 加法规则特殊：若最高位产生进位，需把进位循环加回最低位。

示例：计算 $5 + (-3)$

1. +5 反码：00000101
2. −3 原码 10000011 → 反码 11111100
3. 相加：00000101 + 11111100 = 100000001（9 位）
4. 循环进位：把最高位的 1 加到末尾 → 00000001 + 1 = 00000010，真值为 2。

20.4 补码（Two's Complement）

补码是计算机标准的有符号整数编码，彻底解决了双零和减法复杂的问题。

20.4.1 定义

• 正数：补码 = 原码 = 反码；
• 负数：补码 = 反码 + 1（无循环进位）。

20.4.2 表示方法（8 位）

• +5：00000101
• −5：原码 10000101 → 反码 11111010 → 补码 11111011
• 0 只有唯一编码：00000000

20.4.3 n 位补码的取值范围

n 位（1 符号位 + n−1 数值位）：

8 位范围：−128 ~ 127。10000000 专门表示 −128，它没有对应的原码/反码。

20.4.4 运算规则

1. 加法：$[A+B]_{\text{补}} = [A]_{\text{补}} + [B]_{\text{补}}$，直接相加，最高位进位直接丢弃（模 $2^n$）。
2. 减法：$[A-B]_{\text{补}} = [A]_{\text{补}} + [-B]_{\text{补}}$，减法转为「加负数的补码」。
   • 求 $-B$ 的补码：对 $[B]_{\text{补}}$ 全部位取反再加 1。

示例1：$5 - 3$

• +5 补码 00000101，−3 补码 11111101
• 相加：00000101 + 11111101 = 100000010，舍弃进位得 00000010，真值 2。

示例2：$3 - 5$

• +3 补码 00000011，−5 补码 11111011
• 相加得 11111110（负数补码），还原：补码 −1 得反码 11111101，数值位取反 → 原码 10000010，真值 −2。

20.4.5 补码优势

1. 0 唯一，节省一个状态；
2. 减法完全转为加法，硬件只需一个加法器；
3. 比原码多表示一个最小负数（−128），取值范围更大。

20.5 三种编码转换关系

20.5.1 正数

$[X]_{\text{原}} = [X]_{\text{反}} = [X]_{\text{补}}$

20.5.2 负数

1. 原码 → 反码：符号位不变，数值位取反；
2. 反码 → 补码：整体 +1；
3. 补码 → 原码：两种方式等价
   • 补码全部位取反加 1；
   • 补码 −1 得到反码，再数值位取反（符号位不变）。

示例：X = −5（8 位）

• 原码：10000101
• 反码：11111010
• 补码：11111011
• 补码求原码：11111011 取反 00000100 +1 → 00000101，加回符号位 → 10000101。

20.6 补码溢出

运算结果超出 n 位补码范围即为溢出，结果不可信。

20.6.1 判断方法（单符号位）

• 两个正数相加，结果符号位变成 1 → 正溢出；
• 两个负数相加，结果符号位变成 0 → 负溢出；
• 一正一负相加永远不会溢出。

示例：8 位计算 120 + 10

• 120 补码 01111000，10 补码 00001010
• 相加得 10000010，符号位变为 1 → 正溢出（130 > 127）。

20.7 计算机选用补码的原因

1. 硬件简化：只需加法电路，减法转换加法；
2. 零统一：消除 ±0 两种编码；
3. 空间充分：多表示一个负极值，存储利用率更高。

20.8 C++ 验证示例

下面用 C++ 打印一个负数在内存中的补码，并验证 ~x = -x - 1 这条重要性质。

#include <iostream>
using namespace std;

// 以 8 位二进制形式输出一个 signed char 的补码
void printBinary(signed char x) {
    for (int i = 7; i >= 0; i--) {
        cout << ((x >> i) & 1);   // 逐位取出，右移后&1
    }
}

int main() {
    signed char a = -5;
    cout << "十进制 -5 在内存中的补码: ";
    printBinary(a);                 // 输出 11111011
    cout << endl;

    // 验证补码性质：~x = -x - 1
    cout << " ~a = " << (int)(~a)
         << " , -a - 1 = " << (int)(-a - 1) << endl;
    return 0;
}

20.9 选择题练习

1. 在 8 位补码表示中，能表示的整数范围是？

A. −127 ~ 127
B. −128 ~ 127
C. −128 ~ 128
D. 0 ~ 255

2. 十进制数 −5 的 8 位原码是？

A. 10000101
B. 11111010
C. 11111011
D. 00000101

3. 关于补码，下列说法正确的是？

A. 0 在补码中有两种表示（+0 与 −0）
B. 负数的补码等于其反码减 1
C. 补码体系下减法可以转化为加法
D. 8 位补码无法表示 −128

4. 两个正整数在 8 位补码下相加，结果符号位变为 1，这说明？

A. 发生了正常进位，结果正确
B. 发生了溢出，结果错误
C. 发生了借位
D. 无任何异常

5. 已知 8 位补码 11110110，其对应的真值是？

A. −10
B. −9
C. −8
D. 246