Skip to content

Chap 2 Bit, 数据类型与运算

约 1332 个字 预计阅读时间 4 分钟

上完专业课回来有一种融会贯通的错觉（并不）

0 从问题描述到电子运转

序号 描述
1 问题
2 算法
3 语言
4 机器（ISA）结构
5 微结构
6 电路
7 器件
汇编语言 和 ISA 的关系

汇编语言通常与 ISA 具有 1to1 关系，但前者有时支持更加复杂的操作（如结构化编程块）

  • 汇编语言是 ISA 操作码、逻辑和指令的抽象集合，是指令的文本形式（不涉及指令编码）

  • ISA 更像是指定了指令及其二进制编码的标准文档

  • 步骤 3-4 理论上就是编译原理覆盖的内容（高级语言至 ISA）

    • 高级语言 -> ISA 由 编译器 compiler 完成

    • 汇编语言 -> 对应 ISA 由 汇编器 assembly

  • 指令集结构 ISA (Instruction Set Architecture) 是程序和计算机硬件接口之间的一个完整定义，包括：

    • 计算机可以执行的指令集合
    • 每个操作所需要的数据（操作数 operand）是什么
    • 可接受的操作数表达方式（数据类型 data type）
    • 定位操作数的方法（寻址模式 addressing mode）

1 Bit & 数据类型

1.1 Bit

\[ bit = 0 \ or\ 1 \]
  • 电路只有两个状态，为了表达更多的数值状态，我们可以将多条线路合并使用（形成 k-bit 的二进制数，共有 2k种不同状态）

1.2 整数

本课程使用补码（ 2's Complement ）表示正负整数，使用 ASCII 表示字符

  • 无符号整数 Unsigned Integer

    用 k-bit 可以表示 0 ~ 2k-1 的 2k 个无符号整数

  • 有符号整数

    我们将 2k 个位置一分为二，一半表示正数，另一半表示负数。以 5-bit 字串为例：

    1. 符号位表示法 Signed Magnitude

      • 最高位表示符号，后 k 位表示数值（绝对值二进制串）

        其中 00000 与 10000 分别表示 +0，-0

      • 范围为 [+0, (2^k-1)] + [-0, -(2^k-1)]

      +5 的二进制编码为 00101，则 -5 的二进制编码为 10101

    2. 反码 1's Complement

      • 将正数的所有 bit（包括符号位） 直接取反，即可得到其相反数的二进制编码

      • 范围为 [+0, (2^k-1)] + [-(2^k-1), -0]

      +5 的二进制编码为 00101，则 -5 的二进制编码为 11010

    3. 补码 2's Complement

      • 负整数补码 = 正整数反码 + 1

      • 范围为 [+0, (2^k-1)] + [-(2^k), -1] ，负数多一个

      • +5 的二进制编码为 00101，则 -5 的二进制编码为 11011
      • 使用补码的好处是计算时可以直接将二进制 逐位相加（相反数相加后为 000...0，忽略符号位产生的进位），方便 ALU 进行计算
三种编码方式对负数表示方式的对比
  • 对于符号位表示法，符号位取反
  • 对于反码，所有位取反
  • 对于补码，数值串 = 2^k - |n| 的原码（ |n| 原码取反 + 1）
编码范围 符号位 反码 补码
00000 ~ 01111 [0, 15] [0, 15] [0, 15]
10000 ~ 11111 [-0, -15] [-15, -0] [-16, -1]

补码中负数会比正数多一个 -2k

1.3 位矢 Bit Vector

类似于 bitmap

使用一个 1*N 的矢量表示 N 台机器的闲忙：a[i] = 1 表示第 i 台机器繁忙，反之表示其空闲

1.4 浮点数 Float-Point

类似于科学计数法，除符号位以外的 bit 一部分表示指数，另一部分表示精度

32 bit 的 IEEE 标准浮点数组成如下：

序号 含义 说明
0 (1 bit) 符号 Sign 0 正 1 负
1-8 (8 bit) 指数 Exponent 正则化（ normalized ）结果，实际的为尾数部分为 1(23-bit of Frac)
9-31 (23 bit) 尾数 Fraction 仅使用了 00000001 ~ 11111110 共计 254 个数字
\[ N = (-1)^{Sign} * (1.Frac) * 2^ {Exp - 127}, \ 1 \leq Exp \leq 254 \]
  • Exp 全 0 表示： $$ N = (-1)^{Sign} * (0.Frac) * 2^{-126} $$

Samples

  • 用 IEEE 标准表示浮点数 -6(5/8)
\[ \begin{align*} -6\frac{5}{8} &= -(1*2^2 + 1*2^1 + 0*2^0 + 1*2^{-1}+0*2^{-2}+1*2^{-3}) \\ &= -110.101 \\ &\Rightarrow Normalized = -1.10101 * 2^2 \\ &\Rightarrow Sign = 1 \tag{1} \\ &\Rightarrow Exp = 127 + 2 = 129 = 10000001 \tag{2} \\ &\Rightarrow Frac = 10101 + 18*0 \tag{3} \\ &\therefore -6\frac{5}{8} = 1 \ 10000001 \ 10101 + 18*0 \end{align*} \]
  • 求 001111011 + 0*22 表示的浮点数
\[ \begin{align*} &\Rightarrow Sign = 0 \rightarrow Positive \\ &\Rightarrow Exp = 01111011 = 123 = 127 + (-4) = -4 \\ &\Rightarrow Frac = 23*0 = 1.0 \\ &\therefore N = 1.0 * 2 ^{-4} = \frac{1}{16} \end{align*} \]

2 进制转换（补码）

2.1 BtoD

  1. 检查符号位

    • 首位为 0：正数，进入 Step 2
    • 首位为 1：负数，转成相反数的补码（减一取反）

  2. 计算补码的十进制

  3. 若 Step 1 中为负数，则为 Step 2 的结果加上负号

2.2 DtoB

  1. 用短除法求得 |N| 的 k-1 bit 二进制串

  2. 最高位补 0 的到 k bit 二进制串，负数进入下一步

  3. 对 Step 2 中得到的二进制串按位取反后加一

3 运算

3.1 加减法

  • 加法：按位对其，自右向左计算（进位）
  • 减法：将 A-B 视为 A+(-B)，即先求 -B 的补码，随后相加

补码的符号扩展：正数高位补 0，负数高位补 1

溢出
  • 溢出只会发生在同符号数相加的情况下，正负数相加永远不会溢出

  • 溢出检测：在忽略最高进位的条件下，比较运算结果与两个运算数的符号，不一致时便产生溢出

    两正数相加得负 / 两负数相加得正

3.2 逻辑运算

类型 描述
AND 全 1 出 1
OR 有 1 出 1
NOT 取反
XOR 相同出 0，相异出 1