chap3 algorithm
Add and Sub
1. 纸笔运算
| ![[Pasted image 20241023190204.png | 500]] |
E.g.1 计算 7-6=1
![[Pasted image 20241023190419.png|500]]
[!NOTE] 二进制相反数
如图，对6取相反数-6的步骤是：直接把所有位（包括符号位）都取反，然后给最低位+1
E.g.2 计算41-26=15
![[Pasted image 20241025212752.png|300]]
在运算过程中，从右往左逐位进行计算。
1-0=1；
0不够减1，[向前借一后加2]变成[2]；2-1=1；
0在上一步被借一所以减为-1，-1不够减0，[向前借一后加2]变成1；1-0=1；
1在上一步被借一所以减为0，0不够减1，向前借一后[加2]变成2；2-1=1；
0在上一步被借一所以减为-1，-1不够减1，向前借一后[加2]变成1；1-1=0；
1在上一步被借一所以减为0，0-0=0.
————————————————
[!NOTE] Title
==向高位借一，不是简单地给当前位借来了一个”1”，而是借来了一个”2”！==因为假设当前位是第n位，则当前位的”1”代表 $2^n$，而更高一位的”1”则代表 $2^{n+1}$，即当前位的值的2倍；
所以向更高位借来的”1”，到了当前位就变成了”2”，就像在美国拿了1dollar，回中国就变成了7yuan
要仿照图中的方法：用绿字表示当前位 “被低一位借走后变成了多少” ，红字表示 “向高一位借来了多少”
绿字共有两种取值：若当前位本来是0，被低位借1后就变成-1；若本来是1，被低位借1后就变成0）
红字共有两种取值：若当前位本来是-1，向高位借1后就变成-1+2=1；若本来是0，向高位借1后就变成0+2=2）
2. 溢出
a. 正数加负数一定不会溢出，因为结果不会大于其中任意一个操作数；
b. 正数-负数=负数、负数-正数=正数（减法的溢出）
c. 正数+正数=负数、负数+负数=正数（加法的溢出）
d. 无符号运算：和小于加数中的任何一个、差大于被减数
溢出检查的机制：
加或减两个32位的数字可能产生一个需要33位才能表示的结果；
缺少第33位意味着：当溢出发生时，符号位被结果的值占用而非结果的正确符号。由于溢出结果只可能多一位，所以只有符号位可能是错误的。因此，当两个正数相加但和为负数时，说明发生了溢出，反之亦然。这个假的和值意味着产生了向符号位的进位；
Multiplication
1. 【纸笔运算】
![[Pasted image 20241023192147.png|200]]
a) 从上面的手工计算示例中可以清楚地看到，我们需要在每一步计算中 将被乘数左移一位 ，因为它可能会和之前的中间结果相加。然后需要 把乘数右移一位 ，以对齐下一个0或1。
b) 在32步计算之后，32位被乘数会向左移动32位。因此，我们需要一个 64位的被乘数寄存器 ，将其初始化为右半部分的32位被乘数和左半部分的零。然后该寄存器每执行一步便左移1位，将被乘数与64位的乘积寄存器中的中间结果对齐并累加到中间结果。
c) n位被乘数×m位乘数的结果需要 n+m位 来表示 ;
E.g.
![[Pasted image 20241023194028.png|500]]
2. 【乘法器硬件】
![[Pasted image 20241023192850.png|500]]
被乘数寄存器、ALU和乘积寄存器都是64位长，只有乘数寄存器是32位
（因为乘数右移后，被右移掉的数位就不再需要保存了）
3. 【乘法器的改进】
这种算法和硬件很容易改进到每步只花费 一个时钟周期 。加速来源于操作的 并行执行 ：如果乘数位是1，那么对被乘数和乘数进行移位，与此同时，把被乘数加到积上。硬件只需要保证它检测的是乘数的最右位，而且得到的是被乘数移位前的值。
![[Pasted image 20241023193650.png|500]]
这个改进版的乘法器的运行机制是什么？
4. 【带符号数的乘法】
a) 把被乘数和乘数 转换为正数
b) 记住它们的 初始符号，据此决定结果的符号
Float
1. 规格化：小数点左边只有1位数字，且不能是0，只能是一个1
(1.xxxxxxxx)$_2$×2$^{yyyy}$
2. 尾数：(1.xxxxxxxx)$_2$中的”xxxxxxxx”
增加尾数的位数可以提高精度，增加指数位数的大小可以增加数的表示范围
3. RISC-V浮点数格式
float单精度(32bit)：1位符号位(1表示负数)+8位指数(包括指数的符号位)+23位尾数；
- double双精度(64bit)：1+11+52
思考：float和double能表示的小数的范围是多少?4. 溢出
上溢：正指数太大而无法用指数字段表示
- 下溢：负指数太大而无法用指数字段表示
5. 前导1：
为了表示更多的位，IEEE 754让规格化二进制数的前导1是隐含(implicit)的
这是因为规格化数的小数点左边一定是一个1，所以不必占用存储空间，直接在结果上加上这个1即可，尾数部分全部用来保存小数点右边的值
| ![[Pasted image 20241015201623.png | 500]] |
所以除了0之外所有规格数的形式：(-1)$^S$×(1+尾数)×2$^E$
| ![[Pasted image 20241015202459.png | 500]] |
例外：0以及非规格化数没有前导1,IEEE 754通过将所有的指数位都设置为0来表示这是一个0（或非规格化数），此时隐含的前导1就会消失
6. 有效位数=尾数位数+1(隐含的前导1)
7.不同编码表示的意义
![[Pasted image 20241015204216.png|500]]
解释：
当指数为0, 前导1就会消失, 小数点左边为0；此时若尾数为0, 则该数为0;
第二行同理, 整数部分为0；尾数非0，则该数为(0.xxxxxxxx)$_2$×2$^{yyyy}$，即非规格化数（有前导0）
第三行可知格式为(1.xxxxxxxx)$_2$×2$^{yyyy}$，是规格化数
第4-5行需要注意，是IEEE浮点标准对异常的表示
一定要记住[1,254], [1,2046]这两个范围！
8.IEEE 异常表示
(1)正/负无穷
(2)表示无效运算结果的符号Nan
例如0/0或无穷减去无穷。NaN表示不是一个数，其目的是推迟程序中的一些测试和决定，等到方便的时候再进行
9.IEEE 指数排列对排序的考虑
(1)对于浮点表示，尤其是进行排序操作时，最好能直接利用已有的整数比较硬件来处理，这就是符号位处于最高位的原因，这样一来就可以快速判定是小于0、大于0还是等于0；
(2)把指数字段放在尾数之前也简化了利用整数比较指令对浮点数的排序。因为只要两个数的指数部分符号相同，那么具有更大指数的数就一定更大。
(3)不足:
![[Pasted image 20241015205402.png|500]]
于是出现了移码表示法
10.【移码表示法】
(1)偏移值
单精度的偏移值为127
双精度的指数偏移值为1023
如指数-1表示为-1+127${10}$，指数1表示为1+127${10}$
| ![[Pasted image 20241015205648.png | 500]] |
所以，带偏移值的指数意味着一个由浮点数表示的值实际上是：
(-1)$^S$×(1+尾数)×2$^{(指数-偏移量)}$
| ![[Pasted image 20241015210850.png | 500]] |
| ![[Pasted image 20241015210905.png | 500]] |
- 疑问：为什么尾数部分是$(01111110)_2$？
- 答：01111110是126的二进制表示，因为原指数为-1，加上偏移量127后变成了126
浮点数加法
浮点数的运算步骤
浮点数的加减运算一般由以下五个步骤完成：对阶、尾数运算、规格化、舍入处理、溢出判断
一、对阶
所谓对阶是指将两个进行运算的浮点数的阶码对齐的操作。对阶的目的是为使两个浮点数的尾数能够进行加减运算。因为，当进行M x·2Ex与M y·2Ey加减运算时，只有使两浮点数的指数值部分相同，才能将相同的指数值作为公因数提出来，然后进行尾数的加减运算。对阶的具体方法是：首先求出两浮点数阶码的差，即⊿E＝E x-E y，将小·阶码加上⊿E，使之与大阶码相等，同时将小阶码对应的浮点数的尾数右移相应位数，以保证该浮点数的值不变。几点注意：
（1）对阶的原则是小阶对大阶，之所以这样做是因为若大阶对小阶，则尾数的数值部分的高位需移出，而小阶对大阶移出的是尾数的数值部分的低位，这样损失的精度更小。
（2）若二者的指数相等，说明两浮点数的阶码已经相同，无需再做对阶操作。
（3）采用补码表示的尾数右移时，符号位保持不变。
（4）由于尾数右移时是将最低位移出，会损失一定的精度，为减少误差，可先保留若干移出的位，供以后舍入处理用。
二、尾数运算
尾数运算就是进行完成对阶后的尾数相加减。这里采用的就是我们前面讲过的纯小数的定点数加减运算。
三、结果规格化
在机器中，为保证浮点数表示的唯一性，浮点数在机器中都是以规格化形式存储的。对于IEEE754标准的浮点数来说，就是尾数必须是1.M的形式。由于在进行上述两个定点小数的尾数相加减运算后，尾数有可能是非规格化形式，为此必须进行规格化操作。
规格化操作包括左规和右规两种情况。
左规操作：将尾数左移，同时阶码减值，直至尾数成为1.M的形式。例如，浮点数0.0011·25是非规格化的形式，需进行左规操作，将其尾数左移3位，同时阶码减3，就变成1.1100·22规格化形式了。
右规操作：将尾数右移1位，同时阶码增1，便成为规格化的形式了。要注意的是，右规操作只需将尾数右移一位即可，这种情况出现在尾数的最高位（小数点前一位）运算时出现了进位，使尾数成为10.xxxx或11.xxxx的形式。例如，10.0011·25右规一位后便成为1.00011·26的规格化形式了。
四、 舍入处理
浮点运算在对阶或右规时，尾数需要右移，被右移出去的位会被丢掉，从而造成运算结果精度的损失。为了减少这种精度损失，可以将一定位数的移出位先保留起来，称为保护位，在规格化后用于舍入处理。
IEEE754标准列出了四种可选的舍入处理方法：
（1）就近舍入（round to nearest）这是标准列出的默认舍入方式，其含义相当于我们日常所说的“四舍五入”。例如，对于32位单精度浮点数来说：
- 若超出可保存的23位的多余位大于100…00，则多余位的值超过了最低可表示位值的一半，这种情况下，舍入的方法是在尾数的最低有效位上加1；
- 若多余位≤011…11，则直接舍去；
- 若多余位刚好为100…00，判断尾数的最低有效位的值，若为0则直接舍去，若为1则再加1。
（2）朝+∞舍入（round toward +∞）对正数来说，只要多余位不为全0，则向尾数最低有效位进1；对负数来说，则是简单地舍去。
（3）朝-∞舍入（round toward -∞）与朝+∞舍入方法正好相反，对正数来说，只是简单地舍去；对负数来说，只要多余位不为全0，则向尾数最低有效位进1。
（4）朝0舍入（round toward 0）
即简单地截断舍去，而不管多余位是什么值。这种方法实现简单，但容易形成累积误差，且舍入处理后的值总是向下偏差。
五、 溢出判断
与定点数运算不同的是，浮点数的溢出是以其运算结果的阶码的值是否产生溢出来判断的。若阶码的值超过了阶码所能表示的最大正数，则为上溢，进一步，若此时浮点数为正数，则为正上溢，记为+∞，若浮点数为负数，则为负上溢，记为-∞；若阶码的值超过了阶码所能表示的最小负数，则为下溢，进一步，若此时浮点数为正数，则为正下溢，若浮点数为负数，则为负下溢。正下溢和负下溢都作为0处理。
要注意的是，浮点数的表示范围和补码表示的定点数的表示范围是有所不同的，定点数的表示范围是连续的，而浮点数的表示范围可能是不连续的。
E.g.
![[Pasted image 20241015221111.png|500]]
![[Pasted image 20241015221155.png|500]]
一定要记得检查上溢和下溢！！检查的标准是：指数加127后的值是否在1~254之间（这是正负规格数指数的合法范围）（如果发生溢出，程序会被[例外]打断）
详细笔记见书p139
用于浮点加法的ALU见书p141
浮点乘法
E.g.
![[Pasted image 20241018215716.png|500]]
**【第一步】指数处理
和加法不同，我们通过简单地将操作数的[指数相加]来计算积的指数：
New exponent = 10+(-5) = -5
=10+(-5)+127(偏移量)
==不要先给10和-5加上偏移量，然后再把二者相加，否则会多加一个127！==
**【第二步】有效数位部分的相乘
![[Pasted image 20241018220330.png|400]]
[!NOTE] 舍入
实际情况下，这里需要 [向偶数舍入]，才能正确地保留有效数字
【第三步】规格化、检测上/下溢
![[Pasted image 20241018220602.png|200]]
这里未加过偏移量的指数6∈ [-126,127]，所以没溢出
[!NOTE] 上\/下溢检测(对于float单精度)
1.如果是已经经过移码表示法（加过偏移量）的指数E，那么不溢出的条件是E∈ [1 , 254] ；
2.如果是还没经过移码表示法（还没有已经加过偏移量）的指数E，那么不溢出的条件是E∈ [-126 , 127]3.前两个范围很容易弄混！记住加上偏移量127后肯定上下界都变大，所以[1 , 254]是加了偏移量之后的E的范围
【第四步】对积舍入
【第五步】设置符号位
（此例中因为操作数的符号相反，因此将积的符号设为负）
舍入
(1)guard, round and stick
IEEE754规定所有浮点数运算的中间结果右边都必须至少保留两位附加位。这两位附加位中，紧跟尾数右边的那一位叫做保护位（guard），随后一位是舍入位（round）。为了更进一步提高精度，在保护位和舍入位后面还加上了一位粘滞位（sticky）。只要舍入位右边有任何非0数字，粘滞位就置1，否则置0。
(2)为什么要设置Guard and Round bit？
在对阶和尾数右规时，为保证运算精度，一般将低位移出的位保留下来，并让其参与中间过程的运算，最后再将结果进行舍入。（和我们进行十进制运算保留两位小数类似，一般运算过程中都是更精确的3～4位小数，最后才约简。）
如果在计算之前就把操作数先舍入成目标的有效位数，那么得到的结果会有较大的精度损失：
E.g.
![[Pasted image 20241018145713.png|500]]
所以设置guard, round的目的就是强制多保留2位，以防过早地舍入而导致精度损失；
(3)为什么设置Stick bit ?
粘着位的定义：
stick bit是指在guard bit和round bit后面所有位（也就是更低精度部分的位）是否有任何非零值。只要有一个非零位1出现，stick bit就被置为1。如果所有这些位都是零，stick bit就是0。粘着位的作用：
stick bit可以帮助在舍入过程中判断余下的低位是否包含重要信息。如果stick bit是1，说明有低位信息被丢弃，这意味着这些位对最终的结果应该有影响。结合guard和round位，stick bit能确保舍入的精度更加合理。
(4)向偶数舍入
IEEE 754 采用向最近偶数舍入（round to nearest even）的规则
舍入的规则需要区分三种情况，
- 当具体的值大于中间值的时候，向上舍入
- 当具体的值小于中间值的时候，向下舍入
- 当具体的值等于中间值的时候，向偶数舍入
向偶数舍入指的是要保留的最低有效位为偶数，具体规则，
- 要保留的最低有效位如果为奇数，则向上舍入
- 要保留的最低有效位如果为偶数，则向下舍入
中间值
上面的舍入规则，提到了一个很重要的概念，中间值。怎样才能确定这个中间值呢？
要找到中间值，先确定要保留的有效数字，找到要保留的有效数字最低位的下一位。如果这位是 进制的一半，而且之后的位数都为 0，则这个值就是中间值。
上面的描述比较抽象，来看两个例子
- 十进制的
1.2500，要保留到小数点后一位，下一位是5，是进制的一半(10的一半)，后面位数都为 0，所以这个值就是中间值 - 二进制的
10.0110，要保留到小数点后两位，下一位是1，是进制的一半(2的一半)，后面位数都为 0，所以这个值就是中间值
例子
知道了舍入规则之后，我们来看几个具体的例子，以二进制为例，有效位数保留到小数点后两位
10.00011，中间值为10.00100，小于中间值，向下舍入为10.0010.00110，中间值为10.00100，大于中间值，向上舍入为10.0110.11100，中间值为10.11100，等于中间值，要保留的最低有效位1为奇数，向上舍入为11.0010.10100，中间值为10.10100，等于中间值，要保留的最低有效位0为偶数，向下舍入为10.10