计组第五次作业

本次我们实现了浮点数的加减法，是关于浮点数运算的第一次实现，并且虽然看过了书和ppt，但是在实操过程中也出现了不少的问题，尤其是溢出的处理这些特殊情况，下面通过此次作业来分析一下浮点数的加减法。

1 实验要求

在FPU类中实现2个方法，具体如下

1.计算两个浮点数真值的和

public DataType add(DataType src, DataType dest)

2.计算两个浮点数真值的差

public DataType sub(DataType src, DataType dest)

2 实验指导

2.1 代码实现要求

本次实验中，我们仍然明确禁止各位采用直接转浮点数进行四则运算来完成本次实验。

2.2 代码实现流程

对于浮点数加减运算的流程，课件与课本都有很详细的讲解，在此不再赘述。对于代码实现层面，大致可分为以下几步:

处理边界情况(NaN, 0, INF)
提取符号、阶码、尾数
模拟运算得到中间结果
规格化并舍入后返回

2.2.1 处理边界情况

在框架代码中，我们提供了cornerCheck方法来检查0和INF的情况，大家直接调用即可。

此外，对于NaN的情况，我们提供了一个基于正则表达式的处理方案，可用如下代码进行检查：

String a = dest.toString();
String b = src.toString();
if (a.matches(IEEE754Float.NaN_Regular) || b.matches(IEEE754Float.NaN_Regular)) {
    return new DataType(IEEE754Float.NaN);
}

在util.IEEE754Float类中，我们提供了NaN的正则表达式，对于正则表达式的作用机制大家可以自行查阅。

在本次作业中，大家直接调用cornerCheck方法以及上述正则表达式的解决方案即可轻松完成第一步：对边界情况的检查。

如果你顺利实现第一步，应该可以在seecoder平台上拿到15分。

2.2.2 提取符号、阶码、尾数

在本次作业中，我们使用IEE754浮点数运算标准，模拟32位单精度浮点数，符号位、指数部分与尾数部分分别为1、8、23位，同时使用3位保护位(GRS保护位)，大家经过简单操作即可完成这一步。

这一步有三个需要特殊处理的地方：

当有一个操作数提取出的阶码为全1时，应该返回其本身。（为什么？考虑无穷加减其他数的结果）
当提取出的阶码为全0时，说明该操作数是一个非规格化数，此时应该对阶码+1使其真实值变为1，以保证后面的对阶操作不会出错。（为什么？可以考察IEEE754浮点数标准中阶码为0和阶码为1分别表示2的多少次方）
在这一步中不要忘记尾数的最前面添加上隐藏位，规格化数为1，非规格化数为0。所以提取结束后尾数的位数应该等于1+23+3=27。

2.2.3 模拟运算得到中间结果

这一步是要求大家实现的重要步骤。这一步主要做两件事情。

第一件事情是对阶，采用小阶向大阶看齐的方式，小阶增加至大阶，同时尾数右移，保证对应真值不变。注意，基于GRS保护位标准，尾数右移时不能直接将最低位去掉。我们提供了对尾数进行右移的方法，方法签名如下：

private String rightShift(String operand, int n)

第一个参数为待右移的尾数，第二个参数为右移的位数。请大家每次对尾数进行右移操作时都调用这个方法，否则很可能出现最后对保护位进行舍入后，尾数与结果差1的情况。

第二件事情是尾数相加或相减。这一步相对简单，大家可以调用提供的ALU类进行操作，也可以拷贝上次实验中自己写的代码进行操作。

2.2.4 规格化并舍入后返回

在这一步中，我们只要求大家进行规格化的处理。这里需要大家思考的是，在上一步运算结束后，有哪几种情况会导致结果不符合规格化的条件？

当运算后尾数大于27位时，此时应该将尾数右移1位并将阶码加1。
- 注意，这个将阶码加1的操作可能会导致阶码达到"11111111"，导致溢出。针对这种阶码上溢的情况，应该返回什么？
当运算后尾数小于27位时，此时应该不断将尾数左移并将阶码减少，直至尾数达到27位或阶码已经减为0。
- 注意，若阶码已经减为0，则说明运算得到了非规格化数，此时应该怎么办？（可以考察阶码为0000 0001，尾数为0.1000 0000 0000 0000 0000 0000 00的浮点数该如何正确表示）

我们提供了相关的本地用例，大家可以仔细揣摩其中的奥妙。

对于规格化后的舍入操作，我们不要求掌握GRS保护位相关的舍入操作，感兴趣的同学可以自行查阅。我们提供了舍入操作的函数如下

private String round(char sign, String exp, String sig_grs)

请注意，在调用此方法前，请确保你传入的参数已经进行了规格化，务必确保传入的符号位为1位，阶码为8位，尾数为1+23+3=27位。

在此方法中，我们已经对GRS保护位进行了相应的处理并完成舍入，返回的结果即为32位的字符串，转化为DataType类型后即可通过测试。

至此，你已经完成了浮点数加减法的全部工作(・ω・)ノ

2.3 测试用例相关

本次实验中，test9方法会使用表驱动的方法进行多次的运算。如果出现了报错，但却不知道是哪一对数字报的错，可以在函数运行过程中，每当遇到expect结果跟actual结果不一样的情况时，将src、dest、expect与actual分别打印到控制台，然后再对这组数据进行单步调试。这种调试方法不但在本次作业中非常有用，并且也会让你在以后的debug生涯中受益匪浅。

例如，可以在test9中的assertEquals语句前插入如下代码。

String expect = Transformer.intToBinary(Integer.toString(Float.floatToIntBits(input[i] + input[j])));
if (!expect.equals(result.toString())) {
    System.out.println("i = " + i + ", j = " + j);
    System.out.println("src: " + src);
    System.out.println("dest:" + dest);
    System.out.println("Expect: " + expect);
    System.out.println("Actual: " + result);
    System.out.println();
}

2.4 GRS保护位

注：以下内容不需要掌握

GRS保护位机制使用3个保护位辅助完成舍入过程。一个27位的尾数可表示为

1(0) . m1 m2 m3 …… m22 m23 G R S

这里G为保护位（guard bit），用于暂时提高浮点数的精度。R为舍入位（rounding bit），用于辅助完成舍入。S为粘位（sticky bit）。粘位是R位右侧的所有位进行逻辑或运算后的结果，简单来说，在右移过程中，一旦粘位被置为1（表明右边有一个或多个位为1）它就将保持为1。

在round函数中，根据GRS位的取值情况进行舍入，舍入算法采用就近舍入到偶数。简单来说，在进行舍入时分为以下三种情况。

当GRS取值为"101" "110" "111"时，进行舍入时应在23位尾数的最后一位上加1。
当GRS取值为"000" "001" "010" "011"时，进行舍入时直接舍去保护位，不对23位尾数进行任何操作。
当GRS取值为"100"时，若23位尾数为奇数则加1使其变成偶数，若23位尾数为偶数则不进行任何操作。

3. 解答与分析

首先贴一张流程图

加法和减法的本质是相同的，所以减法的第一步就是将减数的符号部分取反，然后用加法计算。

3.1 Step1

首先处理边界情况，方法助教都已经写好了，直接写（袁春风的那本书上并没有这部分的内容）。在实际中就是要考虑正负无穷和+0、-0，这几种情况。

//加法
String a = dest.toString();
String b = src.toString();
if (a.matches(IEEE754Float.NaN_Regular) || b.matches(IEEE754Float.NaN_Regular)) {
    return new DataType(IEEE754Float.NaN);
}
String cornerResult = cornerCheck(addCorner, a, b);
if (null != cornerResult)return new DataType(cornerResult);

//减法
String a = dest.toString();
String b = src.toString();
if (a.matches(IEEE754Float.NaN_Regular) || b.matches(IEEE754Float.NaN_Regular)) {
    return new DataType(IEEE754Float.NaN);
}
String cornerResult = cornerCheck(subCorner, a, b);
if (null != cornerResult)return new DataType(cornerResult);

最后一列是返回值。

3.2 Step2

实现流程图中的第一部，判断被加数和加数是否其中有一个值为0。

//判断是否为0
if (a.equals(IEEE754Float.P_ZERO) || a.equals(IEEE754Float.N_ZERO))return src;
if (b.equals(IEEE754Float.P_ZERO) || b.equals(IEEE754Float.N_ZERO))return dest;

3.3 Step3

提取符号、阶码、尾数

这里我们需要判断是否为无穷的情况，即阶码全为1。
此外还需要检查阶码是否全为0，可以参考一下非规格化数和规格化数的表示，为了防止后续的对阶不会出错，因此需要加1，对实际值是不影响的。
最后需要加入三位保护位GRS

//提取
char sign_a = a.charAt(0), sign_b = b.charAt(0);
String expo_a = a.substring(1, 9), expo_b = b.substring(1, 9);
//判断是否为无穷
if (expo_a.equals("11111111"))return dest;
else if (expo_b.equals("11111111"))return src;
//非规格化数阶码全为0
char hiddenBit_a = '1';
char hiddenBit_b = '1';
if (expo_a.equals("00000000")){
    expo_a = oneAdder(expo_a).substring(1);
    hiddenBit_a = '0';
}
if(expo_b.equals("00000000")){
    expo_b = oneAdder(expo_b).substring(1);
    hiddenBit_b = '0';
}
String significand_a = hiddenBit_a + a.substring(9) + "000";
String significand_b = hiddenBit_b + b.substring(9) + "000";

3.4 Step4

下面就是十分重要的对阶操作

首先实现了ExponentMatching和binaryToInt方法

private int ExponentMatching(String expo1, String expo2){
    if (expo1.equals(expo2))return 0;
    int e1 = binaryToInt(expo1), e2 = binaryToInt(expo2);
    return e1 - e2;
}

private int binaryToInt(String s){
    int len = s.length();
    int sum = 0;
    for (int i = len - 1; i >= 0; i--){
        if (s.charAt(i) == '1')sum += Math.pow(2, len - 1 - i);
    }
    return sum;
}

然后就按照正常的操作开始移位

//对阶
int E = ExponentMatching(expo_a, expo_b);
if (E >= 0){
    significand_b = rightShift(significand_b, E);
    if (significand_b.equals("000000000000000000000000000")){
        return dest;
    }
}
else{
    expo_a = expo_b;
    E = -E;
    significand_a = rightShift(significand_a, E);
    if (significand_a.equals("000000000000000000000000000")){
        return src;
    }
}

这里需要注意是否会出现尾数下溢（等于0）的情况，这时候我们只需要返还另一个数就行了。

3.5 Step5

尾数加减，并进行规格化处理

对于原码的加法，所采取的方式为同号相加，异号相减。

求和时，数值位相加，如果最高位产生了进位则需要在之后进行右移。
相减时，分两种情况
- 最高数值位产生了进位，表明加法结果为正，所得数值位正确。符号位取被加数（被减数）的符号。
- 最高数值位没有产生进位，表明加法结果为负，得到的是数值位的补码形式，因此，需要对结果求补，还原为绝对值形式的数值位。符号位为被加数（被减数）的符号取反。

实现的addSignificand方法如下：

private String addSignificand(String a, String b, char sign_a, char sign_b){
        //同号求和，异号求差
        ALU alu = new ALU();
        if (sign_a != sign_b) {
            b = oneAdder(alu.negation(b)).substring(1);
        }
        return alu.add(new DataType("00000" + a), new DataType("00000" + b)).toString().substring(4);
    }

在尾数相加之后需要进行左移或者右移的处理。

右移最多只需要移一位，因此我们只需判断现在的指数是否是“11111110”即可，如果是则根据符号位返回+Inf或-Inf。

左移需要考虑的情况比较多，尤其是用例对于尾数是0的情况，对应的expected为正0，并没有管符号位，因此，我索性加了一行尾数为0直接返回正0，虽然我觉得大概是这题出的漏洞，因为确实应该考虑正0和负0的情况呀。

其他的就是对于指数下溢的情况，这边不是直接返回0（ppt多少有点问题）。rtw老师上课也说过，我们默认这个数已经无药可救了，于是右移回去一位，指数置为0，作为非规格化数处理。

//尾数加减
String significand = addSignificand(significand_a, significand_b, sign_a, sign_b);
if (sign_a == sign_b){
    if (significand.charAt(0) == '1'){
        significand = rightShift(significand, 1);
        if (expo_a.equals("11111110")){
            if (sign_a == '0'){
                return new DataType(IEEE754Float.P_INF);
            }else if(sign_a == '1'){
                return new DataType(IEEE754Float.N_INF);
            }
        }
        expo_a = oneAdder(expo_a).substring(1);
    }
}else{
    if (significand.charAt(0) != '1'){
        significand = oneAdder(new ALU().negation(significand)).substring(1);
        sign_a = sign_a == '0' ? '1' : '0';
    }
}
significand = significand.substring(1);
if (significand.equals("000000000000000000000000000"))return new DataType(IEEE754Float.P_ZERO);
int ex = binaryToInt(expo_a);
while (significand.charAt(0) != '1'){
    significand = leftShift(significand);
    ex--;
    if (ex == 0){
        significand = rightShift(significand, 1);
        expo_a = intToBinary(ex);
        return new DataType(round(sign_a, expo_a, significand));
    }
}

3.6 Step6

最后调用已经写好的舍入round函数，就行了。

expo_a = intToBinary(ex);
return new DataType(round(sign_a, expo_a, significand));

4. 完整代码

package cpu.fpu;

import cpu.alu.ALU;
import util.DataType;
import util.IEEE754Float;
import util.Transformer;

/**
 * floating point unit
 * 执行浮点运算的抽象单元
 * 浮点数精度：使用3位保护位进行计算
 */
public class FPU {

    private final String[][] addCorner = new String[][]{
            {IEEE754Float.P_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
            {IEEE754Float.N_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
            {IEEE754Float.P_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
            {IEEE754Float.N_ZERO, IEEE754Float.N_ZERO, IEEE754Float.N_ZERO},
            {IEEE754Float.P_INF, IEEE754Float.N_INF, IEEE754Float.NaN},
            {IEEE754Float.N_INF, IEEE754Float.P_INF, IEEE754Float.NaN}
    };

    private final String[][] subCorner = new String[][]{
            {IEEE754Float.P_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
            {IEEE754Float.N_ZERO, IEEE754Float.P_ZERO, IEEE754Float.N_ZERO},
            {IEEE754Float.P_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
            {IEEE754Float.N_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
            {IEEE754Float.P_INF, IEEE754Float.P_INF, IEEE754Float.NaN},
            {IEEE754Float.N_INF, IEEE754Float.N_INF, IEEE754Float.NaN}
    };

    /**
     * compute the float add of (dest + src)
     */
    public DataType add(DataType src, DataType dest) {
        // TODO
        String a = dest.toString();
        String b = src.toString();
        if (a.matches(IEEE754Float.NaN_Regular) || b.matches(IEEE754Float.NaN_Regular)) {
            return new DataType(IEEE754Float.NaN);
        }
        String cornerResult = cornerCheck(addCorner, a, b);
        if (null != cornerResult)return new DataType(cornerResult);

        //判断是否为0
        if (a.equals(IEEE754Float.P_ZERO) || a.equals(IEEE754Float.N_ZERO))return src;
        if (b.equals(IEEE754Float.P_ZERO) || b.equals(IEEE754Float.N_ZERO))return dest;

        //提取
        char sign_a = a.charAt(0), sign_b = b.charAt(0);
        String expo_a = a.substring(1, 9), expo_b = b.substring(1, 9);
        //判断是否为无穷
        if (expo_a.equals("11111111"))return dest;
        else if (expo_b.equals("11111111"))return src;
        //非规格化数阶码全为0
        char hiddenBit_a = '1';
        char hiddenBit_b = '1';
        if (expo_a.equals("00000000")){
            expo_a = oneAdder(expo_a).substring(1);
            hiddenBit_a = '0';
        }
        if(expo_b.equals("00000000")){
            expo_b = oneAdder(expo_b).substring(1);
            hiddenBit_b = '0';
        }
        String significand_a = hiddenBit_a + a.substring(9) + "000";
        String significand_b = hiddenBit_b + b.substring(9) + "000";
        //对阶
        int E = ExponentMatching(expo_a, expo_b);
        if (E >= 0){
            significand_b = rightShift(significand_b, E);
            if (significand_b.equals("000000000000000000000000000")){
                return dest;
            }
        }
        else{
            expo_a = expo_b;
            E = -E;
            significand_a = rightShift(significand_a, E);
            if (significand_a.equals("000000000000000000000000000")){
                return src;
            }
        }
        //尾数加减
        String significand = addSignificand(significand_a, significand_b, sign_a, sign_b);
        if (sign_a == sign_b){
            if (significand.charAt(0) == '1'){
                significand = rightShift(significand, 1);
                if (expo_a.equals("11111110")){
                    if (sign_a == '0'){
                        return new DataType(IEEE754Float.P_INF);
                    }else if(sign_a == '1'){
                        return new DataType(IEEE754Float.N_INF);
                    }
                }
                expo_a = oneAdder(expo_a).substring(1);
            }
        }else{
            if (significand.charAt(0) != '1'){
                significand = oneAdder(new ALU().negation(significand)).substring(1);
                sign_a = sign_a == '0' ? '1' : '0';
            }
        }
        significand = significand.substring(1);
        if (significand.equals("000000000000000000000000000"))return new DataType(IEEE754Float.P_ZERO);
        int ex = binaryToInt(expo_a);
        while (significand.charAt(0) != '1'){
            significand = leftShift(significand);
            ex--;
            if (ex == 0){
                significand = rightShift(significand, 1);
                expo_a = intToBinary(ex);
                return new DataType(round(sign_a, expo_a, significand));
            }
        }
        expo_a = intToBinary(ex);
        return new DataType(round(sign_a, expo_a, significand));
    }

    /**
     * compute the float add of (dest - src)
     */
    public DataType sub(DataType src, DataType dest) {
        // TODO
        String a = dest.toString();
        String b = src.toString();
        if (a.matches(IEEE754Float.NaN_Regular) || b.matches(IEEE754Float.NaN_Regular)) {
            return new DataType(IEEE754Float.NaN);
        }
        String cornerResult = cornerCheck(subCorner, a, b);
        if (null != cornerResult)return new DataType(cornerResult);

        char sign_b = b.charAt(0) == '0' ? '1' : '0';
        StringBuilder sb = new StringBuilder(b);
        sb.setCharAt(0, sign_b);
        return add(new DataType(sb.toString()), dest);
    }


    private String cornerCheck(String[][] cornerMatrix, String oprA, String oprB) {
        for (String[] matrix : cornerMatrix) {
            if (oprA.equals(matrix[0]) && oprB.equals(matrix[1])) {
                return matrix[2];
            }
        }
        return null;
    }

    /**
     * right shift a num without considering its sign using its string format
     *
     * @param operand to be moved
     * @param n       moving nums of bits
     * @return after moving
     */
    private String rightShift(String operand, int n) {
        StringBuilder result = new StringBuilder(operand);  //保证位数不变
        boolean sticky = false;
        for (int i = 0; i < n; i++) {
            sticky = sticky || result.toString().endsWith("1");
            result.insert(0, "0");
            result.deleteCharAt(result.length() - 1);
        }
        if (sticky) {
            result.replace(operand.length() - 1, operand.length(), "1");
        }
        return result.substring(0, operand.length());
    }

    private String leftShift(String operand){
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < operand.length() - 1; i++){
            result.append(operand.charAt(i + 1));
        }
        result.append('0');
        return result.toString();
    }

    /**
     * 对GRS保护位进行舍入
     *
     * @param sign    符号位
     * @param exp     阶码
     * @param sig_grs 带隐藏位和保护位的尾数
     * @return 舍入后的结果
     */
    private String round(char sign, String exp, String sig_grs) {
        int grs = Integer.parseInt(sig_grs.substring(24, 27), 2);
        if ((sig_grs.substring(27).contains("1")) && (grs % 2 == 0)) {
            grs++;
        }
        String sig = sig_grs.substring(0, 24); // 隐藏位+23位
        if (grs > 4) {
            sig = oneAdder(sig);
        } else if (grs == 4 && sig.endsWith("1")) {
            sig = oneAdder(sig);
        }

        if (Integer.parseInt(sig.substring(0, sig.length() - 23), 2) > 1) {
            sig = rightShift(sig, 1);
            exp = oneAdder(exp).substring(1);
        }
        if (exp.equals("11111111")) {
            return sign == '0' ? IEEE754Float.P_INF : IEEE754Float.N_INF;
        }

        return sign + exp + sig.substring(sig.length() - 23);
    }

    /**
     * add one to the operand
     *
     * @param operand the operand
     * @return result after adding, the first position means overflow (not equal to the carray to the next) and the remains means the result
     */
    private String oneAdder(String operand) {
        int len = operand.length();
        StringBuilder temp = new StringBuilder(operand);
        temp.reverse();
        int[] num = new int[len];
        for (int i = 0; i < len; i++) num[i] = temp.charAt(i) - '0';  //先转化为反转后对应的int数组
        int bit = 0x0;
        int carry = 0x1;
        char[] res = new char[len];
        for (int i = 0; i < len; i++) {
            bit = num[i] ^ carry;
            carry = num[i] & carry;
            res[i] = (char) ('0' + bit);  //显示转化为char
        }
        String result = new StringBuffer(new String(res)).reverse().toString();
        return "" + (result.charAt(0) == operand.charAt(0) ? '0' : '1') + result;  //注意有进位不等于溢出，溢出要另外判断
    }

    private int ExponentMatching(String expo1, String expo2){
        if (expo1.equals(expo2))return 0;
        int e1 = binaryToInt(expo1), e2 = binaryToInt(expo2);
        return e1 - e2;
    }

    private int binaryToInt(String s){
        int len = s.length();
        int sum = 0;
        for (int i = len - 1; i >= 0; i--){
            if (s.charAt(i) == '1')sum += Math.pow(2, len - 1 - i);
        }
        return sum;
    }

    private String intToBinary(int n){
        StringBuilder ans = new StringBuilder();
        while (n != 0){
            if (n % 2 == 1)ans.append('1');
            else ans.append('0');
            n /= 2;
        }
        int len = ans.length();
        for (int i = 0; i < 8 - len; i++){
            ans.append('0');
        }
        return ans.reverse().toString();
    }

    private String addSignificand(String a, String b, char sign_a, char sign_b){
        //同号求和
        ALU alu = new ALU();
        if (sign_a != sign_b) {
            b = oneAdder(alu.negation(b)).substring(1);
        }
        return alu.add(new DataType("00000" + a), new DataType("00000" + b)).toString().substring(4);
    }
}

Kiyotaka Wang's Blog

计组第5次作业