当前位置：首页 > news >正文

数据的表示和运算 I

news 2024/10/27 11:00:40

一、数制与编码

1. 进位计数制及其相互转换

【总结】：

1）进位计数法

在进位计数法中，每个数位所用到的不同数码的个数称为 “基数” 。例如：十进制的基数为 10 (0~9)，每个数位计满 10 就向高位进位，即 “逢十进一”。

十进制数 101 ，其个位的 1 显然与百位的 1 所表示的数值是不同的。每个数码所表示的数值等于该数码本身乘以一个与它所在数位有关的常数，这个常数称为 “位权” 。一个进位数的数值大小就是它的各位数码按权相加。

式中， r 是基数；rⁱ 是第 i 位的位权（整数位最低位规定为第 0 位）；K_i 的取值可以是 0, 1, …, r-1 共 r 个数码中的任意一个。

可以用后缀字母标识一个数的进位计数制，用 B 表示二进制，用 O 表示八进制，用 D 表示十进制（通常可以省略），用 H 表示十六进制，有时也用前缀 0x 表示十六进制数。

2）不同进制数之间的相互转换

① 任意进制数转换为十进制数：

将任意进制数的各位数码与它们的权值相乘，再把乘积相加，就得到了一个十进制数。这种方法称为按权展开相加法。

② 二进制数转换为八进制数和十六进制数：

对于一个二进制混合数（既包含整数部分，又包含小数部分），在转换时应以小数点为界。

其整数部分，从小数点开始往左数，将一串二进制数分为 3 位（八进制）一组或 4 位（十六进制）一组，在数的最左边可根据需要加 “0” 补齐；
对于小数部分，从小数点开始往右数，也将一串二进制数分为 3 位一组或 4 位一组，在数的最右边也可根据需要加 “0” 补齐。

最终使总的位数为 3 或 4 的整数倍，然后分别用对应的八进制数或十六进制数取代。

③ 八进制数和十六进制数转换为二进制数：

同样，由八进制数或十六进制数转换成二进制数，只需将每位改为 3 位或 4 位二进制数即可（必要时去掉整数最高位或小数最低位的 0) 。

④ 八进制数和十六进制数之间的转换：

八进制数和十六进制数之间的转换也能方便地实现，十六进制数转换为八进制数（或八进制数转换为十六进制数）时，先将十六进制（八进制）数转换为二进制数，然后由二进制数转换为八进制（十六进制）数较为方便。

⑤ 十进制数转换为任意进制数：

一个十进制数转换为任意进制数，常采用基数乘除法。这种转换方法对十进制数的整数部分和小数部分将分别进行处理，对整数部分用除基取余法，对小数部分用乘基取整法，最后将整数部分与小数部分的转换结果拼接起来。

除基取余法（整数部分的转换）：整数部分除基取余，最先取得的余数为数的最低位，最后取得的余数为数的最高位（即除基取余，先余为低，后余为高），商为 0 时结束。

乘基取整法（小数部分的转换）：小数部分乘基取整，最先取得的整数为数的最高位，最后取得的整数为数的最低位（即乘基取整，先整为高，后整为低），乘积为 1.0（或满足精度要求）时结束。

十进制转换为二进制时，使用“拼凑法”即可。

注意：在计算机中，小数和整数不一样，整数可以连续表示，但小数是离散的，所以并不是每个十进制小数都可以准确地用二进制表示。例如 0.3 ，无论经过多少次乘二取整转换都无法得到精确的结果。但任意一个二进制小数都可以用十进制小数表示。

2. 定点数的编码表示

1）真值和机器数

真值：符合人类习惯的数字（+表示正、-表示负）。

机器数：数字实际存到机器里的形式，正负号需要被“数字化”（0表示正、1表示负）。

2）机器数的定点表示

定点数：小数点的位置固定；浮点数：小数点的位置不固定。定点表示法用来表示定点小数和定点整数。

定点小数。定点小数是纯小数，约定小数点位置在符号位之后、有效数值部分最高位之前。若数据 X 的形式为 X = x₀.x₁x₂···x_n （其中 x₀ 为符号位，x₁ 至 x_n 是数值的有效部分，也称尾数，x₁ 为最高有效位）
定点整数。定点整数是纯整数，约定小数点位置在有效数值部分最低位之后。若数据 X 的形式为 X = x₀x₁x₂···x_n（其中 x₀ 为符号位，x₁ 至 x_n 是尾数，x_n 为最低有效位）

在现代计算机中，通常用定点补码整数表示整数，用定点原码小数表示浮点数的尾数部分，用移码表示浮点数的阶码部分。

3）原码、补码、反码、移码

① 原码：用机器数的最高位表示数的符号，其余各位表示数的绝对值。

② 反码：（了解即可）负数的反码可采用“各位取反”的方法得到，正数的反码的定义和相应的原码表示相同。

③ 补码：负数的补码可采用“各位取反，末位加 1”的方法得到，正数的补码的定义和相应的原码表示相同。

可见，小数补码比原码多表示一个 “-1”；整数补码比原码多表示一个 “-2ⁿ” 。

④ 移码：移码常用来表示浮点数的阶码，它只能表示整数。

移码就是在真值 X 上加上一个常数（偏置值），通常这个常数取 2ⁿ ，相当于 X 在数轴上向正方向偏移了若干单位，这就是＂移码”一词的由来。

注意：[0]_补 ≠ [0]_移，但是相同位数的补码和移码表示具有相同的数据表示范围。

原码很容易判断大小。而负数的反码、补码很难直接判断大小，可采用如下规则快速判断：对于负数，数值部分越大，绝对值越小，真值越大（更靠近0) 。

4）总结与拓展

原码和反码的真值 0 有两种表示；补码和移码的真值 0 只有一种表示，补码和移码可以多表示一个负数。
补码的作用：使用补码可将减法操作转变为等价的加法，ALU 中无需集成减法器。执行加法操作时，符号位一起参与运算。
由 [x]_补求 [-x]_补的方法：符号位、数值位全部取反，末位 +1 。
补码与真值之间的转换：
① 真值转换为补码：对于正数，与原码的方式一样；对于负数，符号位取 1 ，其余各位由真值 “各位取反，末位加 1” 得到。
② 补码转换为真值：若符号位为 0，与原码的方式一样；若符号位为 1，真值的符号为负，数值部分各位由补码 “各位取反，末位加 1” 得到。
负数的补码转换为原码的方法：从右向左找到第一个数值为 1 的位，之后的每位进行取反操作，符号位不变。
变形补码：又称模 4 补码，双符号位的补码小数，模 4 补码双符号位 00 表示正， 11 表示负，用在完成算术运算的 ALU 部件中。将 [x]_补的符号位与数值位一起右移并保持原符号位的值不变，可实现除法功能。
移码表示的整数很方便对比大小，移码越大则真值越大。

3. 整数的表示

1）无符号整数

当一个编码的全部二进制位均为数值位而没有符号位时，该编码表示就是无符号整数，也直接称为无符号数，此时，默认数的符号为正。由于无符号整数省略了一位符号位，所以在字长相同的情况下，它能表示的最大数比带符号整数能表示的大。n 位的无符号数表示范围为：0 ~ 2ⁿ-1 。

2）带符号整数

将符号数值化，并将符号位放在有效数字的前面，就组成了带符号整数。虽然原码、补码、反码和移码都可以用来表示带符号整数，但补码表示有其明显的优势：

① 与原码和反码相比， 0 的补码表示唯一。
② 与原码和反码相比，补码比原码和反码多表示一个最小负数。
③ 与原码和移码相比，补码运算规则比较简单，且符号位可以和数值位一起参加运算。

计算机中的带符号整数都用补码表示，故 n 位带符号整数的表示范围是 -2^n-1 至 2^n-1-1 。

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

1）C语言中的整型数据类型

C 语言中的整型数据就是定点整数，根据位数的不同，可分为：

字符型（char，8位）
短整型（short 或 short int , 16 位）
整型（int，32 位）
长整型（long 或 long int，在 32 位机器中为 32 位，在 64 位机器中为 64 位）

char 是整型数据中比较特殊的一种，其他如 short int long 等不指定 signed/unsigned 时都默认是有符号整数，但 char 默认是无符号整数。

signed/unsigned 整型数据都是按补码形式存储的，只是 signed 型的最高位代表符号位，而在 unsigned 型中表示数值位，因此这两者所表示的数据范围也有所不同。

2）零扩展和符号扩展

为什么需要对数据进行长度扩展？

① ALU的位数是固定的，运算前可能需要把短数据扩展为长数据
② 通用寄存器位数是固定的，把数据存入寄存器时，可能需要进行长度扩展
③ 主存内的各种数据长度不一，有时需要把短数据扩展为长数据

3）类型转换

① 有符号数和无符号数的转换：强制类型转换的结果保持位值不变，仅改变了解释这些位的方式。

② 不同字长整数之间的转换：

当大字长变量向小字长变量强制类型转换时，系统把多余的高位部分直接截断，低位直接赋值，因此也是一种保待位值的处理方法。
当短字长到长字长的转换时，不仅要使相应的位值相等，还要对高位部分进行扩展。如果原数字是无符号整数，则进行零扩展，扩展后的高位部分用 0 填充。否则进行符号扩展，扩展后的高位部分用原数字符号位填充。

二、运算方法和运算电路

1. 基本运算部件

1）逻辑门电路基础

逻辑门电路基础总结：

逻辑运算的优先级、常见公式：

多路选择器与三态门：

多路选择器（multiplexer，MUX）：在多个输入数据中，只允许其中一个数据通过 MUX 。
三态门：根据控制信号决定是否让输入的数据通过。
三态门与非门的核心区别：“非门”没有控制信号，只有输入和输出。

2）加法器

【总结】：

① 串行进位的并行加法器：

一位全加器：

S_i = A_i ⊕ B_i ⊕ C_i-1 ；C_i = A_i·B_i + (A_i ⊕ B_i)·C_i-1 。

n位全加器：

进位信息是串行产生的，计算速度取决于进位产生和传递的速度，位数越多，运算速度越慢。

由于两个输入端允许并行输入 n bit，因此这种加法器属于：并行加法器；
由于进位信息是串行产生的，因此从“进位方式”看，这种加法器属于：串行进位加法器。串行进位又称为行波进位，每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的。

② 并行进位的并行加法器：

并行进位的并行加法器：所有进位信息都是同时产生的，几乎没有延迟。

特点：运算速度比“串行进位的并行加法器”更快。

③ 带标志位的加法器：

标志位的生成：

3）算术逻辑单元（ALU）

【总结】：

CPU 由控制器、运算器组成。控制器负责解析指令，并根据指令功能发出相应的控制信号；运算器负责对数据进行处理，如：加减乘除等。

ALU（Arithmetic and Logic Unit）是一种组合逻辑电路，实现了加/减/乘/除、与/或/非等功能。因此 ALU 是运算器的核心。由于加减乘除等运算都要基于“加法”来实现，因此加法器是 ALU 的核心。

2. 定点数的移位运算

【总结】：

移位：通过改变各个数码位和小数点的相对位置，从而改变各数码位的位权。可用移位运算实现乘法、除法。

1）算术移位

① 原码的算数移位：符号位保持不变，仅对数值位进行移位。

右移：高位补 0 ，低位舍弃。若舍弃的位 = 0 ，则相当于 ÷ 2 ；若舍弃的位 ≠ 0 ，则会丢失精度；
左移：低位补 0 ，高位舍弃。若舍弃的位 = 0 ，则相当于 × 2 ；若舍弃的位 ≠ 0 ，则会出现严重误差。

② 反码的算数移位：

正数的反码与原码相同，因此对正数反码的移位运算也和原码相同。
右移：高位补 0 ，低位舍弃；
左移：低位补 0 ，高位舍弃。
负数的反码数值位与原码相反，因此负数反码的移位运算规则为：
右移：高位补 1 ，低位舍弃；
左移：低位补 1 ，高位舍弃。

③ 补码的算数移位：

正数的补码与原码相同，因此对正数补码的移位运算也和原码相同。
右移：高位补 0 ，低位舍弃；
左移：低位补 0 ，高位舍弃。
负数补码的算数移位规则如下：
右移（同反码）：高位补 1 ，低位舍弃；
左移（同原码）：低位补 0 ，高位舍弃。

由于位数有限，因此有时候无法用算数移位精确地等效乘除法。

2）逻辑移位

可以把逻辑移位看作是对 “无符号数” 的算数移位。

逻辑右移：高位补 0 ，低位舍弃；
逻辑左移：低位补 0 ，高位舍弃。

3）循环移位

3. 定点数的加减运算

【总结】：

1）原码的加减运算（了解即可）

2）补码的加减运算

3）溢出判别方式

方法一：采用一位符号位

方法二：符号位的进位 C_S 和最高数值位的进位 C₁

在加法运算中，如果符号位和数值位都有进位，但符号位的进位与数值位的进位不一致，就表明计算产生了超出能够表示的范围。

例如，如果两个正数相加时，数值位出现了进位（意味着结果在某种意义上可以被认为是“更大”），但符号位却没有进位，这就意味着我们却得到了一个负数（这是不合理的，因为两个正数加起来不应该是负数）。

方法三：采用双符号位（最高位符号位代表了真正的符号）

【归纳】：

带符号数（补码）的加法运算：从最低位开始，按位相加（符号位参与运算），并往更高位进位。
带符号数（补码）的减法运算：
① “被减数”不变，“减数”全部位按位取反、末位 + 1，减法变加法（[A]_补 - [B]_补 = [A]_补 + [-B]_补）；
② 从最低位开始，按位相加，并往更高位进位。

4. 无符号数的加减运算

【总结】：

无符号整数的加法运算：从最低位开始，按位相加，并往更高位进位。
无符号数的减法运算：
① “被减数”不变，“减数”全部位按位取反、末位 + 1，减法变加法（相当于模运算）；
② 从最低位开始，按位相加，并往更高位进位。

无符号数加法/减法的溢出判断：

5. 加减运算的电路

带标志位的加法器：

零标志 ZF = 1 表示结果 F 为 0 。不管对于无符号数还是带符号整数运算，ZF 都有意义。
溢出标志 OF = 1 表示带符号整数运算时发生溢出。对于无符号数运算， OF 没有意义。
符号标志 SF 表示结果的符号，即 F 的最高位。对于无符号数运算，SF 没有意义。
进／借位标志 CF 表示无符号整数运算时的进位／借位，判断是否发生溢出。加法时，CF = 1 表示结果溢出，因此 CF 等于进位输出 C_out 。减法时，CF = 1 表示有借位，即不够减，故 CF 等于进位输出 C_out 取反。综合可得 CF = Sub ⊕ C_out 。对于带符号数运算，CF 没有意义。

（1）无符号数大小的比较：

假设有两个无符号数 A 和 B ，执行 A - B 。
① 当 ZF = 1 时，说明 A = B ；
② 当 ZF = 0 且 CF = 0 时，说明 A > B ；
③ 当 ZF = 0 且 CF = 1 时，说明 A < B 。

（2）有符号数大小的比较：

假设有两个有符号数 A 和 B ，用补码表示，执行 [A]_补 - [B]_补。
① 当 ZF = 1 时，说明 A = B ；
② 当 OF = SF（或 OF ⊕ SF = 0）且 ZF = 0 时，说明 A > B ；
③ 当 OF ≠ SF（或 OF ⊕ SF = 1）且 ZF = 0 时，说明 A < B 。