3. Arithmetic for Computer

约 6162 个字 预计阅读时间 31 分钟

3.1 Introduction

1. Computer words are composed of bits;

   • there are 32 bits/word or 64 bits/word in RISC-V

   • Contains four bytes for 32bits word

     一个字 word 32 bits

2. Simplified to contain only in course:

   • memory-reference instructions: lw, sw(load word \ store word)，ld，sd（load double store double）,lh, sh（load half store half）

   • arithmetic-logical instructions: add, sub, and, or, xor, slt(set less than比较 slt x1 x2 x3: x1 = (x2 < x3) ? 1 : 0)...

   • control flow instructions(跳转): beq（如果equal跳转到……branch）, bne（not equal）, jal（jump and link）

     以上均需要ALU，计算内存地址，进行条件判断

3. Generic Implementation:

   • use the program counter (PC) to supply instruction address

     PC program counter 储存指令的地址

   • get the instruction from memory 从内存中取出指令

   • read registers

   • use the instruction to decide exactly what to do

4. All instructions use the ALU after reading the registers

对于binary integer \(1001_2\)

• unsigned : \(1001_2 = 9_{10}\)
• signed : \(1001_2 = -1_{10}(原码) = -6_{10}(1's \ compliment) = -7_{10}(2's \ compliment)\)

3.2 Signed and Unsigned Numbers Representations

• Sign and magnitude

  

  • 补码 2's Complement

    扩充位数，左侧补符号位即可

    only one representation for 0

    one more negative number than positive number \([-2^{n-1},2^{n-1}-1]\)

    

  • 反码 1's Complement

  • 原码 sign magnitude

    首位为符号位，后续按照2的幂进行计算

补充 Two‘s Biased notation

如上图所示，左侧为32位的二进制补码表示，如果看作无符号数，则左侧是从小到大排列的。但是右侧对应的十进制整数确实分段递增。

假设原先 n = 4

为此引入移码，在左侧加上\(2^{4}\),也就是在原先符号位的地方+1，此时变为

\[ \begin{aligned} &0000_2 = 0 &0001_2 = 1 &\cdots &0111_2 = 7\\ &1000_2 = -8 &1001_2 = -7 &\cdots &1111_2 = -1\\ &左侧加上2^4\\ &10000_2 = 0 &10001_2 = 1 &\cdots &10111_2 = 7\\ &01000_2 = -8 &01001_2 = -7 &\cdots &01111_2 = -1\\ \end{aligned} \]

\([X]_b = 2^n + X\)从2进制补码到移码，只需符号位扩充一位，再翻转符号位即可。

现在0表示负数，1表示正数

3.3 Arithmetic

3.3.1 Addition and Substraction

• Addition

• Substraction

• Overflow detection: \(C_n \oplus C_{n-1}\)

\[ \begin{aligned} &unsigned \ representation\\ &1111 \ 1111 \ (255)_{10}\\ + &1111 \ 1010 \ (250)_{10}\\ = 1 \ &1111 \ 1001 \ (249)_{10}\\ &2's \ compliment\\ &1000 \ 0001 \ (-127)_{10} \\ +&1111 \ 1110 \ (-2)_{10} \\ = 1 \ &0111 \ 1111 \ (127)_{10}\\ \end{aligned} \]

对于无符号数，看进位是否产生即可；\(n\)位二进制数，看\(C_n\)

对于有符号数，看\(C_n \oplus C_{n-1}\)

对于有符号数的进位，对于已知operandA，B符号的情况下，可以直接利用Result[n]^Result[n-1]来判断。如果A，B的符号未知，则采用进位判断，判断C_n ^ C_{n-1}

3.3.2. Logical operations

1. Logical shift operations（空余的位置补充0）

   sll x1 x2 x3

   slli x1 x2 imm

   

2. AND->bit-wise AND between registers

   and R1, R2, R3

3. OR->bit-wise OR between registers

   or R1, R2, R3

3.4 Construct an ALU

世界上不存在减法。众所周知，减法就是加上相反数。所以这个世界上不存在减法。

Overflow。硬件规模是有限的，因此运算结果超过这个限制时，就会发生溢出。

对于有符号加法，当正数和正数相加得到负数，或者负数和负数相加得到正数时，就可以判定溢出。

对于无符号加法，如果结果小于二者中任意一个，也可以判定溢出。因为无符号数得到的一定都是正数

• 关于 Overflow，硬件层面需要能检测溢出，然后将这个指令的地址存储到一个特别的寄存器 EPC 里，然后跳转到 OS 中专门的程序中来处理这个溢出（异常处理）；

ALU, Arithmetic Logic Unit，算术逻辑单元，执行一些算术运算或者逻辑运算。

3.4.1 1-bit ALU

（下面这部分内容在课本附录 A.5 开始的地方）

我们先考虑 1 bit ALU 的构造。我们学习过 1 bit Full Adder 的构造：

$$ S = X \oplus Y \oplus Cin\ COUT = XY + Cin(X+Y) = XY + Cin X + Cin Y $$ 上左图是全加器的具体构造，右图是我们将其进行封装后的表示方式。

我们结合一个 mux，就可以构造一个支持与、或以及加法运算的 1 bit ALU：

其中 Operation 是用来指明 mux 采取哪个结果的信号，值为 00 01 10 分别对应与、或、加法运算。

32位的行波进位加法器，速度慢

3.4.2 加上减法和 NOR！****

减法运算怎么办呢？众所周知，由于补码有 \(x + \bar x = 111\dots111_2 = -1\)，因此 \(-x = \bar x + 1\)，所以 \(a - b = a + (-b) = a + \bar b + 1\)。据此我们可以构造这样的结构：

其中 Binvert 用来指明是否需要将结果取反；在计算减法时，我们将 Binvert 设为 1 ，然后将 CarryIn 也设为 1 ， Operation 设为 2 ，这样我们的结果就是 \(a + \bar b + 1\)。

NOR 运算： a NOR b = NOT(a OR b) = (NOT a) AND (NOT b) ，因此 NOR 运算可以这样实现：

在计算NOR时，将Ainvert,Binvert设为1，Operation设为0

上右图是我们目前的 1 bit ALU 的抽象结构。

3.4.3 加上comparison

现在补充比较功能comparison

slt rd,rs,rt

• If rs < rt, rd = 1, else rd = 0

• 对于rd，除了最后一个bit（bit[0]）其他的bit都是0

• 如何判断rs < rt？，采用substraction,利用符号位进行判断

• 最后输入的Less，取的就是rd寄存器的LSB（least significant bit ）

3.4.4 加上overflow

单精度浮点数 符号位1位，指数8位， frac23位

0x7F800000 = 0b 0111_1111_1000_0000….0

首先是正数，指数部分是11111111， 对应正无穷\(+\inf\)

---

对于-1的表示方法： \(-1 \times 1.0 \times 2^0\)

符号位为1，frac全为0，指数部分=127 = 01111111

1 01111111 00000….0 = 0xBF800000

---

引入模块overflow detection，Set is most significant bit ，也就是bit[n-1]

carry out 是 bit[n]

\(overflow =carry \ in \oplus carry \ out\)

3.4.5 串联得到 64-bit ALU！

有了 1 bit 的 ALU，我们就可以构造出 RISC-V 所需的 64 bits 的 ALU 了：

注意一下此处：Set 连接作为Less的输入。本质上是因为，执行减法计算后，如果rs < rt，此时a - b 计算得到的结果 符号位肯定为1，对应Less = 1，满足 a < b

可以看到，对于 64 位的加法、减法、AND, OR, NOR 运算，这样的 64 位 ALU 都可以完成。

同时也可以注意到，这里面除了我们熟悉的内容外，还多了 Less , Set 和 Overflow 这些位。它们是用来干什么的呢？

首先 Overflow 是容易理解的，它用来表示加法或减法有没有出现溢出的现象；显然这个判断只需要在 ALU63，即 Most Significant Bit 才需要进行。容易证明，如果 \(C_{in} \oplus C_{out} = 1\)，那么存在溢出；因此 ALU63 只需要添加一个额外的 XOR 门即可完成这一判断。

Tip: 这里提到的 \(C_{in}\) 和 \(C_{out}\) 指的都是最后一个 ALU 的 carry in 和 carry out。

简单做解释，首先，最后一位是符号位。\(C_{in} \oplus C_{out} = 1\) 意味着其中一个是 1，另外一个是 0；

• 假设 \(C_{in} = 1, \, C_{out} = 0\)，则意味着 \(a_{63}\) 和 \(b_{63}\) 都为 0，即两个 operand 都是正数，此时由于 \(C_{in} = 1\)，所以 \(res_{63}=1\) 即结果是负数，两正数相加得到负数，发生 overflow；
• 假设 \(C_{in} = 0, \, C_{out} = 1\)，则意味着 \(a_{63}\) 和 \(b_{63}\) 都为 1，即两个 operand 都是负数，此时由于 \(C_{out} = 1\)，所以 \(res_{63}=0\) 即结果是正数，两负数相加得到正数，发生 overflow；

Less 和 Set 共同使用，是为了实现 slt rd, rs1, rs2 这个操作（即实现比较操作）（SLT 即 Set Less Than）的。

这个操作的含义是，如果 rs1 < rs2 ，那么将 rd 置为 1 ，否则置为 0 。如何进行这一判断呢？很简单，rs1 < rs2 即 rs1 - rs2 < 0，也就是说如果 rs1 - rs2 结果的最高位是 1 ，那么就说明 rs1 < rs2 。

所以对于 slt 这个操作，我们只需要计算 rs1 - rs2，而后将 ALU63 中加法器的结果（即最终结果的符号位）赋值给 Result[0] ，即运算结果的 Least Significant Bit，而将其他位的结果 Result[63:1] 都设成 0，就可以完成 slt 操作了。

因为在比较操作中，最终的输出结果就是Less，所以上图中，除了 ALU0 的 Less 来自 ALU63 的 Set 外，其他 ALU 的 Less 都是 0 。

结合上述讨论，上图中 ALU0 ~ ALU62 的结构如下第一张图所示，ALU63 的结构如下第二张图所示：（溢出仅需在最后一个ALU进行计算）

（注：第二张图中的 Overflow Detection 被复杂化了，实际上可以通过 CarryIn 和 CarryOut 的异或\(\oplus\)完成的。）

可以看到， Operation 增加了 3 的取值，这个取值表示进行 slt 操作。

3.4.6 优化 + zero detector！

之前我们也讨论过，如果做减法或者 slt 的话，需要将 Binvert 和 ALU0 的 CarryIn 设成 1 ，如果是加法的话这两个信号都是 0 ；其他运算用不到这两个信号。因此这两个信号始终取值相等，我们可以将这两个信号合并为一个，称之为 Bnegate替代原有的Binvert和CarryIn 。

另外，我们也有 beq ， bne 这样的操作，结合 Common case fast 的设计思想，我们将判断结果是否为 0 的功能也直接加到 ALU 里。

结合上述两个思路，我们形成了最终的 64-bit ALU！

对于这样的一个 ALU，我们需要 4 bits 的 control lines，分别是 Ainvert , Bnegate 和 Operation (2 bits)。ALU 的符号和 control lines 的含义如下：

对于NOR，A NOR B = NOT（A OR B） = （NOT A） AND （NOT B），所以需要对A和B都取反，在执行AND操作

3.5 加速加法器

上面的 64 位加法的实现方式是通过 1 位加法器串联实现的，这种方式势必需要等待前一个加法器算出结果后才能算后一个的。这种多位加法器的实现称为行波加法器 Ripple Carry Adder, RCA。显然，这种实现方式比较慢。

$$ S_i = A_i \oplus B_i \oplus C_i\ C_{i+1} = A_i B_i + C_i(A_i+B_i) $$

那么，如何加速呢？

3.5.1 Carry Lookahead Adder, CLA

课本指出，RCA(ripple carry adder) 缓慢的重要原因是后一个 adder 需要等前一个 adder 的 carry 结果；但我们不妨讨论出现 carry 的可能。第一种可能是，如果 \(a\) 和 \(b\) 都是 1，那么一定会 生成 一个 carry；另一种可能是，如果 \(a\) 和 \(b\) 中有且仅有一个是 1，那么如果传入的 carry 是 1，则这里也会 carry，即 carry 被 传播 了。

也就是说，\(c_{out} = a \cdot b + (a + b)\cdot c_{in}\)。我们记 generate \(g = a\cdot b\)，propagate \(p = a + b\)，则有 \(c_{out} = g + p \cdot c_{in}\)。所以，我们可以这样构造一个全加器：

进位的生成与传播：

generate = a & b propagate = (a | b)

\(C_{out} = g + p * C_{in}\)

所以，我们可以推导出如下关系（可以形象理解每一个等式的每一个 term 的来源）：

\[ \begin{aligned} c_1 &= g_0 + p_0 \cdot c_0\\ c_2 &= g_1 + p_1 \cdot c_1\\ &= g_1 + p_1 \cdot (g_0 + p_0 \cdot c_0)\\ &= g_1 + p_1 \cdot g_0 + p_1 \cdot p_0 \cdot c_0\\ c_3 &= g_2 + p_2 \cdot c_2 = g_2 + p_2 \cdot g_1 + p_2 \cdot p_1 \cdot g_0 + p_2 \cdot p_1 \cdot p_0 \cdot c_0 \end{aligned} \]

利用这个关系，我们可以构造这样一个四位加法器：

上面的 PFA, Partial Fully Adder，就是前面我们构造的新全加器的一部分。可以看到，通过这样的方式，我们可以加速加法的运算；但是注意到越到高位，门的 fan-in 就越大，因此不能一直增加的。所以对于更多位数的加法器，我们将上面这样构成的 4-bit CLA(Carry Look-ahead Adder) 再通过类似的方式串起来！

group generate(\(G_{0-3}\)), group propagate(\(P_{0-3}\))

\[ \begin{aligned} &G_{0-3} = G_3 + P_3G_2 + P_3P_2G_1+P_3P_2P_1G_0\\ &P_{0-3} = P_3P_2P_1P_0\\ &C_4 = G_{0-3} + P_{0-3}C_0 \end{aligned} \]

3.5.2 Carry Skip Adder

3.5.3 Carry Select Adder, CSA

体现了 预测 / 冗余 的思想。

这个思路其实比较简单，就是把输入 carry 为 0 或者 1 的情况都算一遍，然后根据实际的情况从中选出正确的那种就好了：

3.6 乘法

Multiplicand 被乘数 Multiplier 乘数

3.6.1 version1

• 大致原理

换句话来说，所谓的乘法实际上是根据 Multiplier 的 0/1 来选择是否要将 Multiplicand 的对应位移结果加到 Product 上。

64 bits 乘法器的硬件实现大致如下：

简单做解释，一共进行 64 次：

1. 判断 Multiplier 寄存器的最低位是否是 1（control test）：
   1. 如果是(write = 1)，则将 Multiplicand 寄存器的值加到 Product 寄存器里(128-bit ALU)；
   2. 如果否，进入下一步；
2. 将 Multiplier 寄存器的值右移一位（这是为了不断拿出每一位，相当于在枚举 Multiplier 的每一位），将 Multiplicand 寄存器的值左移一位（对应于和 Multiplier 的第几位乘得到的位移，具体参考上面的链接内容）；
3. 判断是否做满 64 次，决定是否终止；

3.6.2 version2

不再移动被乘数multiplicand

相反移动product

ALU 缩减为64 bits

可以发现，version1 中做了大量的 128 位加法，但是实际上被加过去的 Multiplicand 有效内容只有 64 位。version2 正是解决了这个问题。

它将 Multiplicand 寄存器换为了 64 位，而将位移操作转移到了 Product 寄存器中进行。这里最重要的一点就是，64 位加法只影响 Product 寄存器左侧的 64 位，而之后的右移操作则是 128 位。这样，虽然最低位的结果一开始会被放在 Product 寄存器的第 65 位里，但是在经过 64 次右移之后，它就出现在第一位了。于是，所有的 128 位加法都被 64 位加法替代，实现了加速。

其流程大概是，一共进行 64 次：

1. 判断 Multiplier 寄存器的最低位是否是 1：
   1. 如果是，则将 Multiplicand 寄存器的值加到 Product 寄存器的左半部分里；
   2. 如果否，进入下一步；
2. 将 Multiplier 寄存器的值右移一位，将 Product 寄存器的值右移一位；
3. 判断是否做满 64 次，决定是否终止；

3.6.3 version3

在version2的基础上，发现multiplier每回合需要右移一位，同时product也需要右移一位。但是multiplier每次移位之后，左侧会多一个无用的bit，同时product移位后一个无用的bit将被丢弃。那为什么不把multiplier放在product的右边半呢？

V3 正是抓住了这个点，直接将 Multiplier 存在了 Product 的低 64 位中。当我们从中取出最低位并经过一次判断后，这一位就不重要了，而恰好 Product 需要右移，就将这一位消除，方便我们下一次从最低位拿出下一个比特！

那么这么做的好处在哪里呢？首先，少了一个寄存器，节省了空间；其次，原本需要 Multiplier 寄存器和 Product 寄存器都做右移，现在只需要 Product 寄存器右移即可，减少了一个 64 位右移操作。

product 的 右半边存放multiplier

其流程大概是，一共进行 64 次：

1. 判断 Product 寄存器的最低位是否是 1：
   1. 如果是，则将 Multiplicand 寄存器的值加到 Product 寄存器的左半部分里；
   2. 如果否，进入下一步；
2. 将 Product 寄存器的值右移一位；
3. 判断是否做满 64 次，决定是否终止；

---

3.6.4 有符号乘法

乘有符号数主要是转化为乘无符号数来做。

1. 首先存储两个数的符号，然后将它们转化为无符号数（MSB = 0）。
2. 接下来对两个无符号数做无符号乘法，
3. 最后根据之前存储的符号决定结果的符号并转化为有符号数。如果符号位相同，结果符号位=0，否则，结果符号位=1

---

一种改进的乘法方法是 Booth's Algorithm。

3.6.5 Booth's Algorithm。

• Booth's Algorithm（有点类似于差分算法）

在我看来，Booth's Algorithm 的主要思想在于，减少乘数中“1”的数量。具体来说，在我们原先的乘法策略中，每当乘数中有一位 1 时，都会需要一个加法（将位移后的被乘数累加到结果中）。

但是，如果乘数中有较长的一串 1 时，我们可以将它转化为一个大数字减一个小数，如：00111100 = 01000000 - 00000100，此时 4 个 1 变为 2 个 1，我们就可以减少做加法的次数。这也是为什么 xyx 说有点像差分了。

增加移位的次数，减少加减运算的次数

那么在实际执行过程中，Booth's Algorithm 主要遵循两位比特的模式进行操作。

对于上面这张图的理解，稍微做一些解释。它实际上的表示是挪用了 Version3 的乘法器。product 一列代表的是 product 寄存器，左一半一开始置 0，右一半一开始存放的是乘数，而上面提到的将被乘数加减累计到结果中的操作，也是对于左半部分来说的（换句话来说就是用 Version 做 Booth's）。需要提醒的是，在 Booth's Algorithm 中，两位识别是从第一位开始的，此时第一位作为两位中的高位，低位为 0，而后在下一轮中第一位作为低位，第二位作为高位，以此类推。

有意思的事出现了，Booth's Algorithm 也能应用于负数。

仔细想想就会发现其实很合理，对于正数，其最高位一定是 0，因此不管怎么样它最终都会匹配到一个 01 的模式，来给一个 1111.. 收尾。但是负数不然，负数的最高位是 1，这也意味着它最终不会执行所谓的 01 对应的加法操作来给 111... 收尾。换句话来说，它好像“亏”了一个在下一位的加法。（具体的为什么我来不及细想了，但是只管上理解这个“亏”很合理.）

Faster Multiplication

Uses multiple adders

相当于64 个 64 bits的数相加

3.7 除法

3.7.1 version1

divisor（除数） 在divisor寄存器的左侧，dividend（被除数）位于Remainder寄存器的右侧

1. 用Remainder 减去 Divisor 除数
   • 如果余数小于0，说明当前的除数太大。需要先复原，余数加回除数。再对商进行左移，令Q0=0
   • 如果余数大于0，说明当好。此时先将商进行左移，再将Q0设为1
2. 除数缩小右移
3. 判断是否做满 65 （n+1）次，决定是否终止；

思考一下：为什么需要执行65次？

因为在第一次执行的时候，remainder的左半边全为0，但是devisor的数全在左半边，所以毫无疑问，第一次的执行得到的商是0.

我们假设除数是0，被除数是111….11，那么从第一轮执行结束后，除数已经发生过右移，此时的除数变为0，所以后续的64次执行得到的商都是1，最开始的商0，也被右移出寄存器，符合结果。

\(7 \div 2 = 00000111 \div 0010\)

3.7.2 version2

除数和ALU的宽度减半；

商寄存器不再需要。

除数不再移动，余数寄存器移动，商补在余数寄存器的右侧

余数寄存器左移一位

1. 用余数寄存器的左半边减去除数，结果保留在左半边
   • 如果小于0，加回除数，恢复原数。左移一位余数寄存器，右侧补上0
   • 如果大于0，余数寄存器左移，右侧补1
2. 判断是否做满 64 次，决定是否终止；终止时余数寄存器的左半边右移1位（得到余数）

此处执行64次与上方的不同之处在于：第一轮开始之前的操作是左移remainder。

所以，第一轮，remainder在左移之后，可能会使得左半边大于divisor的情况（除数是0的情况），所以商是不确定的。

在64轮操作执行之后，显然余数寄存器的左移执行了65次，商和余数之间间隔着第一次左移带来的0，所以全部执行之后，需要对余数寄存器进行右移操作

余数的符号和被减数保持一致

3.8 浮点运算

大部分处理器可能本身并不支持浮点运算，只不过在软件层面可以将浮点运算转换为整数运算。

3.8.1 IEEE 754 浮点表示

我们将小数点左边只有 1 位数字的表示数的方法称为 科学记数法, scientific notation，而如果小数点左边的数字不是 0，我们称这个数的表示是一个 规格化数, normalized number。科学记数法能用来表示十进制数，当然也能用来表示二进制数。

normalized 与 not normalized 的区别在于有无前导0，且小数点前只能有一位

\[ \begin{aligned} &-2.24 \times 10^{45} ——normalized\\ &0.002 \times 10^{-4}—— not \ normalized \\ &1101.01101 ——not \ normorlized\\ &1.10101101 \times 10^3 ——normalized \end{aligned} \]

IEEE 754 规定了一种浮点数标准：我们将浮点数表示为 $(-1)^S \times F \times 2^E$ 的形式，这里的 \(F \times 2^E\) 是一个规格化数，而 \((-1)^S\) 用来表示符号位：\(S\) 为 0 说明该浮点数为正数，为 1 则为负数；\(F\) 和 \(E\) 也用若干 bits 表示，分别表示尾数和指数，我们稍后讨论。也就是说，我们将其表示为 \(1.\text{xxxxx}_2\times 2^{\text{yyyy}}\) 的形式这意味着我们没法直接通过这种表达形式表示 0（为什么小数点左边是 1 呢？因为二进制只有 0 和 1，而规格化要求小数点左边不能为 0）。我们通过科学记数法调整了小数点的位置使其满足规格化的要求，因此我们称这种数的表示方法为 浮点, floating point。

小数点的英文是 decimal point，但是我们这种表示方法不再是 decimal 的了，因此我们起个新名字：二进制小数点, binary point。

IEEE 754 规定了两种精度的浮点数格式，分别是 single precision 和 double precision（分别对应 C 语言中的 float 和 double ），RISC-V 这两种都支持：

可以看到，fraction 的位数越多，浮点数的精度就越高；而 exponent 的位数越多，浮点数能保存的范围就越大。

那么对于 \((-1)^S \times F \times 2^E\)，\(S\) 的二进制表示方法是显然的，仅需要一个 bit 就好了。那么 \(F\) 和 \(E\) 怎么表示呢？如我们之前所说，\(F\) 就是 \(1.\text{.xxxxx}_2\) 的形式，这个 1 是固定的，因此 \(F\) 只需要保存 \(\text{.xxxxx}\) 的部分就可以了（但是请注意，它的权重从左到右分别是 \(2^{-1}, 2^{-2}, ...\)）！那么 \(E\) 怎么办呢？注意到这个指数在实际使用中可能是正整数、负整数或 0，因此我们使用一个偏移，对单精度浮点数偏移 127，双精度浮点数偏移 1023（刚好是表示范围的一半！），也就是说我们保存的 exponent 其实是 \(E + bias\) 的二进制。也就是说，对于这样的一个表示，其值是：

\[(-1)^S\cdot (1 + \text{fraction}) \cdot 2 ^ {\text{exponent} - \text{bias}}\]

exponent 表示范围是\(1 - 254\), 0 和 255用于表示特殊数据

\(Normalize \ significand: 1.0 ≤ |significand| < 2.0\)

\(min:1.0000\cdots0; max:1.111\cdots11 \approx 2\)

课本给出了一个例子：

单精度实数和双精度实数 绝对值 的范围

\[ \begin{aligned} &smallest: Exponent :0000\_0001\\ &Fraction:000\cdots000 \rightarrow significand = 1.0 \rightarrow +-1.0 \times 2^{-126}\\ \end{aligned} \]

\[ \begin{aligned} &largest: Exponent:1111\_1110\\ &Fraction:111\cdots111 \rightarrow significand \approx 2.0 \rightarrow +-2.0 \times 2^{127} \end{aligned} \]

• Overflow: The number is too big to be represented
  • 正上溢
  • 负上溢
• Underflow: The number is too small to be represented

单精度实数和双精度实数的精度

根据fraction的位数确定精度

小数点后7位和小数点后16位

聪明的小朋友可能会问，0 应该怎么保存呢？毕竟 0 没有前导 1。对于这样的特殊情形，IEEE 754 有特别规定，用特殊的值保存它们：

在上表中：

• 第 1 条表示 0；Exponent = 0 , Fraction = 0

• 第 2 条表示非规格化数（denormalized number），这种数主要是为了用来表示一些很小的数，它的取值为 \((-1)^S\cdot (\mathbf{0} + \text{fraction}) \cdot 2 ^ { \text{1- bias}}\)；但是并非所有机器都支持这种表示，有的机器会直接抛出一个 exception。我们不考虑非规格数的存在；

  规格化能表示的最小数是\(2^{-126}\),非规格化能表示的更小

  \(max: 0.111\cdots11 \times 2^{-126} = 2^{-126}\)

  \(min: 0.000\cdots01 \times 2^{-126} = 2^{-23} \times 2^{-126} = 2 ^{-149}\)

  对于双精度实数同理

• 第 3 条表示正常的浮点数；

• 第 4 条表示无穷大或者无穷小，出现在 exponent overflow 或者浮点数运算中非 0 数除以 0 的情况；

• 第 5 条表示非数（NaN），出现在 0/0, inf / inf, inf - inf, inf * 0 的情况

（如果数字过大不能表示，即 overflow，则结果置为 inf；如果数字过小不能表示，即 underflow，则结果置为 0。）

这两种表示法的范围和精度分别是多少呢？

• 范围

  • 能表示值的 绝对值 的范围是 \(1.0_2 \times 2^{1-\text{bias}} \sim 1.11\dots 11_2 \times 2^{11\dots 11_2-1-\text{bias}}\)，即 \(1\times 2^{1 - \text{bias}}\sim(2 - 2^\text{-Fra\#})\times 2^{(2^\text{Exp\#} - 1) - 1 - \text{bias}}\)，其中 Fra# 和 Exp# 分别表示 fraction 和 exponent 的位数；
  • 单精度浮点数：\(\pm 1\times 2^{-126}\sim \pm(2 - 2^{-23}) \times 2^{127}\)
  • 双精度浮点数：\(\pm 1\times 2^{-1022}\sim \pm(2 - 2^{-52}) \times 2^{1023}\)

• 精度

  • \(2^ \text{-Fra\#}\)
  • 单精度浮点数：\(2^{-23}\)
  • 双精度浮点数：\(2^{-52}\)

有时候题目里会出不同的浮点数表示法，让你比较精度，此时一般指的是，fraction + exponent 总位数相同的情况下，fraction 更多的一般更精确，也就是说这个精度更倾向于“能表示更多的小数位”。

单精度浮点数 符号位1位，指数8位， frac23位

0x7F800000 = 0b 0111_1111_1000_0000….0

首先是正数，指数部分是11111111， 对应正无穷\(+\inf\)

3.8.2 浮点加法

以 \(1.000_2\times2^{-1}-1.110_2\times2^{-2}\) 为例， 浮点数的加减法分为以下几步：

1. Alignment: 指数对齐，将小指数对齐到大指数：\(-1.110_2\times2^{-2} = -0.111\times2^{-1}\)
   1. 为什么是小对大？首先，小对大的过程是在小指数的 fraction 前补 0，可能导致末尾数据丢失；大对小的过程是在大指数的 fraction 后补 0，可能导致前面的数据丢失。在计算过程中，我们保持的精确位数是有限的，而在迫不得已丢去精度的过程中，让小的那个数的末几位被丢掉的代价比大的前几位丢失要小太多了；
2. Addiction Fraction 部分相加减：\(1.000-0.111=0.001\)
3. Normalization: 将结果规格化：\(0.001\times2^{-1}=1.000\times2^{-4}\)；同时需要检查是否出现 overflow 或者 underflow，如果出现则触发 Exception
4. Rounding: 将 Fraction 部分舍入到正确位数；舍入结果可能还需要规格化，此时回到步骤 3 继续运行

3.8.3 浮点乘法

分别处理符号位、exponent 和 fraction：

• 将两个 Exponent 相加并 减去一个 bias，因为 bias 加了 2 次
• 将两个 (1 + Fraction) 相乘，并将其规格化；此时同样要考虑 overflow 和 underflow；然后舍入，如果还需要规格化则重复执行
• 根据两个操作数的符号决定结果的符号

3.8.4 精确算术

IEEE 754 规定了一些额外的舍入控制，用来保证舍入的精确性。

Round modes

• guard / round / sticky

down: 变小 up：变大 0：抹去小数即可，往0靠 nearest even：最近的偶数

Round to nearest even 只对 0.5 有效，别的都和四舍五入一样

一般的浮点数后面还会有 2 bits，分别称为 guard 和 round，其主要目的是让计算结果的舍入更加的精确：

事实上加法只需要用到 guard，但是对于乘法，如果存在前导 0，需要将结果左移，这时候 round bit 就成了有效位，能避免精度的损失。

另外还有一个位叫 sticky bit，其定义是：只要 round 右边出现过非零位，就将 sticky 置 1，这一点可以用在加法的右移中，可以记住是否有 1 被移出，从而能够实现 "round to nearest even"。

units in the last place(ulp): The number of bits in error in the leas t significant bits of the significant between the actual number and the number that can be represented.

Separate FP registers: $f0, …, f31 $

• double-precision

• single-precision values stored in the lower 32 bits

单精度值存储在较低的 32 位中

FP instructions operate only on FP registers

FP 指令仅在 FP 寄存器上运行

• Programs generally don’t do integer ops on FP data, or vice versa
• More registers with minimal code-size impact

FP load and store instructions \(flw, fld fsw, fsd\)