数据的表示和计算

2.1 数制与编码

2.1.1 进位计数制及其相互转换

在计算机内部，所有信息都是用二进制编码的，原因如下：

• 二进制只有两种状态，易于用物理器件实现（如高低电平）。
• 二进制与逻辑值“真/假”对应，便于逻辑运算。
• 二进制编码和运算规则简单，可通过逻辑门电路方便实现。

常用进位计数制

• 二进制：基数为2，数码0/1，逢二进一。后缀B（Binary）。
• 八进制：基数为8，数码0~7，逢八进一。后缀O（Octal）。
• 十六进制：基数为16，数码09、AF，逢十六进一。后缀H（Hexadecimal）或前缀0x。
• 十进制：基数为10，数码0~9，逢十进一。后缀D可省略。

进制转换

1. 二进制 ↔ 八进制/十六进制

• 二进制转八进制：从小数点开始，整数部分向左，小数部分向右，每3位一组（不足补0），每组转换为1位八进制数。
• 二进制转十六进制：每4位一组转换为1位十六进制数。
• 反向转换：每位八进制（十六进制）转换为3位（4位）二进制。

2. 任意进制 → 十进制 按权展开相加法：将各位数码与位权相乘后求和。
例：$(11011.1)_2 = 1×2^4+1×2^3+0×2^2+1×2^1+1×2^0+1×2^{-1}=27.5$

3. 十进制 → 任意进制

• 整数部分：除基取余法。除以基数，取余数为当前位（从低位到高位），商继续除，直到商为0。
• 小数部分：乘基取整法。乘以基数，取整数部分为当前位（从高位到低位），小数部分继续乘，直到积为1.0或达到精度。

注意：十进制小数不一定能用二进制精确表示（如0.3），但任意二进制小数都可用十进制精确表示。

2.1.2 定点数的编码表示

真值和机器数

• 真值：带正负号的数值（如+15，-8）。
• 机器数：将符号数字化（0表示正，1表示负）后的编码。常用原码、补码、反码、移码。

定点表示

• 定点小数：小数点固定在符号位之后、数值最高位之前。表示纯小数。
• 定点整数：小数点固定在数值最低位之后。表示纯整数。

原码表示

• 最高位为符号位，其余位表示绝对值。
• 定义：$[x]_{\text{原}} = \begin{cases} x & 0 \le x < 2^n \\ 2^n - x & -2^n < x \le 0 \end{cases}$（整数，n+1位含符号）
• 表示范围：$-(2^n-1) \sim 2^n-1$，0有+0和-0两种表示。
• 优点：直观，乘除运算简单；缺点：加减运算复杂，0不唯一。

补码表示

• 正数补码与原码相同；负数补码等于模减去绝对值（或取反加1）。
• 定义：$[x]_{\text{补}} = \begin{cases} x & 0 \le x < 2^n \\ 2^{n+1}+x & -2^n \le x < 0 \end{cases}$（整数，模$2^{n+1}$）
• 表示范围：$-2^n \sim 2^n-1$，比原码多表示一个最小负数$-2^n$。0的表示唯一。
• 优点：符号位与数值位一起参与运算，减法可转为加法。
• 补码与真值转换：正数不变；负数：符号位1，数值位取反加1。反之，补码符号位为1时，数值位取反加1得真值绝对值。
• 变形补码（模4补码）：双符号位，00正，11负，用于ALU中检测溢出。

反码表示

• 正数反码与原码相同；负数反码为原码符号位不变，数值位取反。
• 表示范围同原码，0有+0和-0。很少用于运算，主要作为中间表示。

移码表示

• 在补码基础上将符号位取反（或加偏移量$2^{n}$）。常用于表示浮点数的阶码。
• 移码与补码数值部分相同，符号位相反。0的移码唯一。

2.1.3 整数的表示

计算机中的有符号整数都用补码表示。n位有符号整数的表示范围：$-2^{n-1} \sim 2^{n-1}-1$。
无符号整数（unsigned）全部二进制位均为数值位，表示范围：$0 \sim 2^n-1$。

2.1.4 C语言中的整数类型及类型转换

C语言整型数据按补码形式存储，char默认无符号，short/int/long默认有符号。

有符号数与无符号数的转换

• 强制类型转换保持位值不变，仅改变解释方式。
  例：short x = -4321; unsigned short y = (unsigned short)x; 位值相同，但y的值变为61215。
• 若同时有无符号数和有符号数参与运算，C标准规定按无符号数进行运算。

不同字长整数之间的转换

• 大字长 → 小字长：直接截断高位部分，低位保留。
• 小字长 → 大字长：无符号数进行零扩展（高位补0）；有符号数进行符号扩展（高位补符号位）。

2.1.5 常见考点

• 补码表示范围、补码与真值互转。
• 有符号/无符号转换后的数值变化。
• 不同字长转换时的扩展方式。

---

2.2 运算方法和运算电路

2.2.1 基本运算部件

带标志加法器

• 在无符号数加法器基础上增加逻辑门，生成标志信息：
  • OF（溢出标志） = $C_n \oplus C_{n-1}$（符号位进位与最高数值位进位的异或），用于有符号数溢出判断。
  • SF（符号标志） = 结果的最高位 $F_{n-1}$。
  • ZF（零标志） = 1当且仅当结果为0。
  • CF（进位/借位标志） = $C_{\text{out}} \oplus C_{\text{in}}$（减法时Sub=1，CF = Sub⊕Cout），用于无符号数溢出判断。

算术逻辑单元（ALU）

• ALU核心是带标志加法器，还能执行与、或、非等逻辑运算。ALUop控制操作类型。
  一位ALU结构：通过多路选择器选择输出加法、与、或等结果。

2.2.2 定点数的移位运算

逻辑移位

• 操作数视为无符号整数。左移低位补0，右移高位补0。左移时若高位移出1，则发生溢出。

算术移位

• 操作数视为有符号整数（补码）。左移低位补0，右移高位补符号位。左移前后符号位不同则溢出。

2.2.3 定点数的加减运算

补码加减法公式

• $[A+B]_{\text{补}} = [A]_{\text{补}} + [B]_{\text{补}} \ (\text{mod}\ 2^{n+1})$
• $[A-B]_{\text{补}} = [A]_{\text{补}} + [-B]_{\text{补}} \ (\text{mod}\ 2^{n+1})$

特点：符号位参与运算，减法转为加法，结果高位丢弃。

溢出判断方法

1. 单符号位：两个同号数相加结果符号相反则溢出。$V = A_s B_s \overline{S_s} + \overline{A_s} \overline{B_s} S_s$。
2. 双符号位（模4补码）：运算结果双符号位为01正溢出，10负溢出，00或11无溢出。$V = S_{s1} \oplus S_{s2}$。
3. 进位判断：符号位进位$C_n$与最高数值位进位$C_{n-1}$不同则溢出。$V = C_n \oplus C_{n-1}$。

加减运算电路

• 利用加法器+取反器+多路选择器+低位进位Sub信号，可实现补码加减运算（Sub=0加法，Sub=1减法）。
• 该电路同时支持无符号数加减运算（无符号数减法也是用补码加法实现）。

标志位的应用

• 无符号数比较：ZF=1则相等；CF=1则A<B；ZF=0且CF=0则A>B。
• 有符号数比较：ZF=1则相等；当OF=0时，SF=0则A>B，SF=1则A<B；当OF=1时，SF=1则A>B，SF=0则A<B（实际比较时常用条件转移指令判断标志组合）。

2.2.4 定点数的乘除运算

乘法运算原理

• 原码乘法：符号位单独异或，数值部分为绝对值相乘。乘法通过加法和移位实现（递推公式 $P_{i+1} = 2^{-1}(P_i + X \times y_{n-i})$）。n位乘法需n次加法和n次移位。
• 乘法电路：包含ALU、乘积寄存器、计数器、控制逻辑。每次根据乘数最低位决定是否加被乘数，然后右移。
• 溢出判断：对于int型，若乘积高32位每一位都等于低32位的符号位，则不溢出；对于unsigned int，高32位全0则不溢出。

除法运算原理

• 原码除法：符号位异或，数值部分绝对值相除。通过减法和移位实现，够减上商1，不够减上商0。
• 除法电路：包含ALU、余数寄存器、商寄存器、计数器。每次左移后做减法，根据结果符号上商。
• 除数为0时触发异常。

2.2.5 常见考点

• 补码加减法运算及溢出判断。
• 标志位（CF、OF、SF、ZF）的含义与生成逻辑。
• 移位运算（算术/逻辑）的结果及溢出判断。
• 乘除法的基本实现原理（加-移，减-移）。

---

2.3 浮点数的表示与运算

2.3.1 浮点数的表示

浮点数表示：$N = (-1)^S \times M \times R^E$

• S：符号位
• M：尾数（定点原码小数，通常规格化）
• E：阶码（定点整数，常用移码）
• R：基数（隐含，通常为2）

规格化

• 基数为2时，原码规格化尾数满足 $1/2 \le |M| < 1$，即小数点后第一位为1。
• 左规：尾数左移，阶码减1，直到最高位为1。
• 右规：尾数右移，阶码加1，当尾数溢出（如相加结果≥2）时进行一次。

IEEE754标准

类型	符号位	阶码（移码）	尾数（原码，隐藏1）	偏置值
单精度（32位）	1	8	23	127
双精度（64位）	1	11	52	1023

• 真值：$(-1)^S \times (1.f) \times 2^{e-127}$（单精度）
• 隐藏位：规格化数尾数最高位1不存储，实际有效位多1位。
• 特殊值：
  • 阶码全0，尾数全0：表示0（符号位决定±0）。
  • 阶码全1，尾数全0：表示无穷大（±∞）。
  • 阶码全1，尾数非0：NaN（非数）。
  • 阶码全0，尾数非0：非规格化数（隐藏位为0，指数为-126或-1022），用于处理下溢。

定点数与浮点数比较

• 表示范围：浮点数远大于同字长定点数。
• 精度：浮点数精度较低（尾数位数少）。
• 运算：浮点数运算复杂，需对阶、规格化、舍入。

2.3.2 浮点数的加减运算

1. 对阶：小阶向大阶看齐，小阶尾数右移，阶码增加，直到两数阶码相等。右移时保留移出位用于舍入。
2. 尾数加减：将隐藏位还原，按原码小数加减。
3. 规格化：
   • 若尾数结果为 $\pm 1.\text{xxx}$，右规一次（尾数右移，阶码+1）。
   • 若尾数结果为 $\pm 0.0...01\text{xxx}$，左规多次（尾数左移，阶码-1），直到首位为1。
4. 舍入：IEEE754提供就近舍入（0舍1入，中间值取偶数）、正向舍入、负向舍入、截断法。
5. 溢出判断：主要看阶码是否上溢（超过最大阶码）或下溢（小于最小阶码）。尾数溢出可通过右规纠正。

2.3.3 C语言中的浮点数类型

• float → IEEE754单精度，double → 双精度。
• 类型转换：
  • int → float：可能舍入（int有32位，float尾数仅24位有效）。
  • int/float → double：精确。
  • double → float：可能溢出或舍入。
  • float/double → int：向0截断，可能溢出。
• 混合运算时自动提升到较高类型。

2.3.4 数据的大小端和对齐存储

大端/小端

• 大端方式：低地址存高位字节（MSB在低地址）。
• 小端方式：低地址存低位字节（LSB在低地址）。
• 举例：32位数据0x01234567，大端存储：01 23 45 67（地址递增）；小端存储：67 45 23 01。

边界对齐

• 要求数据的起始地址是其自身大小的整数倍（如int占4字节，地址必须能被4整除）。
• 结构体对齐：每个成员按自身类型对齐，结构体总长度是最大成员长度的整数倍。
  例：struct{ char a; int b; short c; } 在32位下占12字节（a占1，填充3，b占4，c占2，填充2）。

2.3.5 常见考点

• IEEE754单精度/双精度与十进制互转。
• 浮点数加减运算步骤（对阶、尾数加减、规格化、舍入、溢出判断）。
• 大小端存储的地址计算。
• 结构体边界对齐的存储大小和成员地址。

---

2.4 常见问题和易混淆知识点

1. 为什么采用二进制？硬件易实现、运算规则简单、与逻辑对应。
2. 补码的优点：减法转加法、0唯一、多表示一个最小负数。
3. 溢出与进位：CF用于无符号数溢出，OF用于有符号数溢出。有符号数溢出不一定产生CF=1。
4. 浮点数精度：单精度有效数字约7位十进制，双精度约16位。
5. 规格化：基数为2时原码规格化尾数最高位为1；补码规格化尾数最高位与符号位相反。
6. IEEE754隐藏位：规格化数隐藏整数部分的1，非规格化数隐藏0。
7. 强制类型转换：保持位值不变，改变解释方式（除小字长转大字长需扩展）。
8. 边界对齐：以空间换时间，提高访存效率。

---

2.5 复习提示

本章内容繁杂，但统考重点集中在：

• 补码的表示、运算及溢出判断。
• IEEE754浮点数的表示与转换。
• C语言中不同类型转换后的数值变化。
• 大小端、对齐对存储的影响。
• 浮点数加减运算流程。

建议多练习进制转换、补码运算、浮点数二进制与十进制互转，并结合C语言代码分析类型转换结果。