Programming 02

题目大意

完成以下3种二进制下的计算单元

整型加减乘位移ALU.java

浮点型加减FPU.java

NBCD码加减NBCDU.java

大概看一遍，整型这一块处理很简单，后面的相对麻烦一点，码了一会把第一个ALUTest.java过掉了，这部分略过。

`ALU.java`代码

    public class ALU {

    // 模拟寄存器中的进位标志位
    private String CF = "0";

    // 模拟寄存器中的溢出标志位
    private String OF = "0";
    private StringBuilder ans=new StringBuilder();

    public static String getComplement(String tar) {
        tar = tar.replace("0", "2").replace("1", "0").replace("2", "1");
        char[] status = tar.toCharArray();
        for (int i = tar.length() - 1, jud = 1; i >= 0; i--) {
            status[i] = (char) ((jud ^ (tar.charAt(i) - '0')) + '0');
            jud = ((tar.charAt(i) - '0') & jud);
        }
        return Arrays.toString(status).replaceAll("[\\[\\]\\s,]", "");
    } //取补码的方法

    //add two integer
    String add(String src, String dest) {
        ans=new StringBuilder();  //因为把ans写成全局的，这里要重置
        int c=0,s=0;
        for(int i=31;i>=0;i--){
            int x=src.charAt(i)-'0',y=dest.charAt(i)-'0';
            s=x^y^c;
            c=(x&c)|(y&c)|(x&y);
            ans.append(s);
        }
        CF=""+c;
        OF=(src.charAt(0)==dest.charAt(0))&&(src.charAt(0)!=ans.charAt(0))?"1":"0";
        //不知道这俩东西有什么用，姑且写一写
        return ans.reverse().toString();
    }

    //sub two integer
    // dest - src
    String sub(String src, String dest) {
        ans=new StringBuilder();
        src=getComplement(src);
        return add(src,dest);
    }

    //signed integer mod
    String imod(String src, String dest) {
        boolean flag=false;
        if(src.charAt(0)=='1'){
            src=getComplement(src);
        }
        if(dest.charAt(0)=='1'){
            flag=true;
            dest=getComplement(dest);
        }
        while(dest.charAt(0)!='1'){
            dest=sub(src,dest);
        }
        dest=add(src,dest);
        if (flag) return getComplement(dest);
        return dest;
    }

    String and(String src, String dest) {
        for (int i=0;i<32;i++)
            ans.append(dest.charAt(i)==src.charAt(i)&&dest.charAt(i)=='1'?'1':'0');
        return ans.toString();
    }

    String or(String src, String dest) {
        for (int i=0;i<32;i++)
            ans.append(dest.charAt(i)==src.charAt(i)&&dest.charAt(i)=='0'?'0':'1');
        return ans.toString();
    }

    String xor(String src, String dest) {
        for (int i=0;i<32;i++)
            ans.append(dest.charAt(i)!=src.charAt(i)?'1':'0');
        return ans.toString();
    }

    String shl(String src, String dest) {
        int count=Integer.parseInt(src,2);
        if(count>=32)
            return "00000000000000000000000000000000"; //特判一下超过32位就全是0，没必要继续了
        ans=new StringBuilder(dest);
        while(count>0){
            ans.deleteCharAt(0);
            ans.append('0');
            count--;
        }
        return ans.toString();
    }

    String shr(String src, String dest) {
        int count=Integer.parseInt(src,2);
        if(count>=32)
            return "00000000000000000000000000000000";
        ans=new StringBuilder(dest);
        while(count>0){
            ans.deleteCharAt(ans.length()-1);
            ans.insert(0,'0');
            count--;
        }
        return ans.toString();
    }

    String sal(String src, String dest) {
        return shl(src,dest);
    }

    String sar(String src, String dest) {
        ans=new StringBuilder(shr(src,dest));
        if(dest.charAt(0)=='1'){
            for(int i=0;i<ans.length();i++){
                if(ans.charAt(i)=='1')break;
                ans.replace(i,i+1,"1");
            }
        }
        return ans.toString();
    }

    String rol(String src, String dest) {
        int count=Integer.parseInt(src,2);
        count%=32; //减少复杂度，虽然没注意看有没有对应的样例
        char temp;
        ans=new StringBuilder(dest);
        while(count>0){
            temp=ans.charAt(0);
            ans.deleteCharAt(0);
            ans.append(temp);
            count--;
        }
        return ans.toString();
    }

    String ror(String src, String dest) {
        int count=Integer.parseInt(src);
        count%=32;
        char temp;
        ans=new StringBuilder(dest);
        while(count>0){
            temp=ans.charAt(ans.length()-1);
            ans.deleteCharAt(ans.length()-1);
            ans.insert(0,temp);
            count--;
        }
        return ans.toString();
    }

}

二进制浮点数加减法

首先明确二进制浮点数的加减步骤，减的话则是改改符号，其实都是一个东西。

第一步检查有没有0
第二步看指数，这一步要求小的指数往大的靠（因为要保护主要的部分也就是更大的那个数的精度），这里会将较小的数的significant部分右移，同时判断是否全为0了，是的话说明这个数太小，直接返回大数
如果能成功对齐指数，那么就有符号地相加significant（取决于符号位）
- significant为0，返回0
- significant溢出，右移并加指数，检查指数有没有溢出，溢出报错
significant未溢出或溢出但指数增加后指数未溢出，则检查是否标准化，是则直接输出，否则要左移significant（要求以1.开头），此时要减指数，并检查指数是否下溢出，溢出报错，成功结束则输出

当然也有另外一个方法，把二进制转成float，加好之后再转回去（好想偷懒）

观察一下FPUTest.java，发现里面其实要处理一些特殊的浮点数，比如N_INF和N_NaN之类的，同时我们发现样例的指数部分无论是输入还是结果都是没有8个0（指数以0.开头）的情况的，这可以减少不少工作量。而且注意到这些奇怪的东西都在第一个参数，于是又稍微轻松一点。

顺着思路来的话，遇到的需要处理的点：

取了一个变量e=Integer.parseInt(a.substring(1,9))-Integer.parseInt(b.substring(1,9))作为判断大小以及用来后来右移significant。考虑如果e小于0说明a更小，交换一下ab并把e取相反数，e为0说明指数已经对齐
在位移significant时，注意到我们是1.significant，位移后会是0.0..1significant，所以需要先--e并在临时的sig变量中插入一个1
承上，我们在指数未对齐时已经插入了1，那么最后进行significant的加法时，需要补全小数点左边的数，那么需要一个flag记录指数是否是对齐的，对齐的说明之前并没有插入1，因此此时要插入1，未对齐则说明先前已经插入了1，现在要插入0.
significant的有符号加法部分，检查ab的首位符号位面临两种情况
- 两个同号，可能会溢出一位（很显然不可能溢出两位），后续需要改指数部分
- 两个异号，要把负数取补码进行加法，如果significant结果为负则需要取补码，把结果的符号位置为负号，显然这时候就不用考虑溢出的问题了

顺着思路，先打了符号不同的情况，不考虑溢出，只补一个符号位再取补码，这时候发现一个样例fpuAddTest2()死活过不去，经过仔细的研究想了很久才发现，需要在后面加4位的保护位，修改之后就过了，但是实际上也没几个符号不同的，所以还要继续写。

经过一些简单的调整把所有的加法都解决了，之前提过减法只是换符号做加法，发现只剩一个样例fpuSubTest4()没有通过，发现这个样例是零，特殊判定一下就好了，再次测试通过。

以下是代码

public class FPU {

    /**
     * compute the float add of (a + b)
     **/
    String add(String a,String b){
        String ret="";
        if(a.substring(1,32).equals("0000000000000000000000000000000"))
            return b;
        else if(b.substring(1,32).equals("0000000000000000000000000000000"))
            return a;
        if(a.substring(1,9).equals("11111111"))
            return a;
        int e=Integer.parseInt(a.substring(1,9),2)-Integer.parseInt(b.substring(1,9),2);
        if(e<0){
            e=-e;
            String temp=a;
            a=b;
            b=temp;
        }
        boolean flag=false;
        StringBuilder sig=new StringBuilder(b.substring(9,32));
        if(e!=0){
            flag=true;
            sig.insert(0,'1');
            e--; //第一次位移把指数给加到significant里
            sig.append("000");//保护位
            for(int i=1;i<=e;i++){
                sig.deleteCharAt(sig.length()-1);
                sig.insert(0,'0');
                if(sig.toString().equals("00000000000000000000000"))
                    return a;
            }
        }
        else
            sig.append("0000");
        sig.insert(0,flag?'0':'1').insert(0,'0');
        StringBuilder tmp=new StringBuilder(a.substring(9,32)).insert(0,'1').insert(0,'0').append("0000");
        if(a.charAt(0)!=b.charAt(0)){
            if(a.charAt(0)=='1')
                tmp=new StringBuilder(ALU.getComplement(tmp.toString()));
            else sig=new StringBuilder(ALU.getComplement(sig.toString()));
        }
        ALU alu=new ALU();
        StringBuilder after=new StringBuilder(alu.add(tmp.toString(),sig.toString()));
        if(a.charAt(0)!=b.charAt(0)){
            if(after.charAt(0)=='1') {
                ret += "1";
                sig=new StringBuilder(ALU.getComplement(after.toString()));
            }
            else{
                ret+="0";
                sig=after;
            }
        }else{
            ret+=a.charAt(0);
            sig=after;
        }
        if(Pattern.matches("^0*$",sig.toString()))
            return "00000000000000000000000000000000"; //特判减后为0
        int del=1-sig.indexOf("1");
        e=Integer.parseInt(a.substring(1,9),2);
        e+=del;
        ret+= String.format("%8s",Integer.toBinaryString(e)).replaceAll(" ","0");
        if(ret.equals("011111111")||ret.equals("111111111"))
            return ret.charAt(0)=='1'?"11111111100000000000000000000000":"01111111100000000000000000000000";//特判无穷
        ret+=sig.substring(sig.indexOf("1")+1,sig.indexOf("1")+24);
        return ret;
    }

    /**
     * compute the float add of (a - b)
     **/
    String sub(String a,String b){
        return add(a,b.charAt(0)=='1'?'0'+b.substring(1,32):'1'+b.substring(1,32));
    }

}

NBCD加减法

上课讲的decimal arithmetic谈到了4位二进制表达一个十进制数时存在的超过“10”的问题，解决方法是检查二进制数的最高位和中间两位，从0开始编号也就是S3&(S2|S1)，如果为真则进位(+0110)，下一位+0001，依次判断。

而减法则要把A-B写成A+(10^N-B)，也就是借位，值得注意的是这里的(10^N需要一个“取反”操作)

写加法下来发现要注意进位的处理，会有4位的二进制溢出，所以需要扩展到5位。

处理不同号时，为了方便，把负数调换到a上，把开头的0除去方便取反，同时要注意一下这里取反是要ab两数位数的最大位取10的N次幂，所以最终结果检查这个最大位数的高位上是否是0001，是的话就把它置为0000直接返回，不是的话就取反。处理了一些代码上的小bug后，测试通过

public class NBCDU {

    // 模拟寄存器中的进位标志位
    private String CF = "0";

    // 模拟寄存器中的溢出标志位
    private String OF = "0";
    private static String bitAdd(String...args){
        ALU alu=new ALU();
        StringBuilder ret=new StringBuilder(alu.add("0"+args[0],"0"+args[1]));//防止溢出
        if(args.length==4)return ret.toString();
        else if(args.length==3)
            if(args[2].equals("1"))
                ret=new StringBuilder(alu.add(ret.toString(),"00001"));
        int x=ret.charAt(1)-'0',y=ret.charAt(2)-'0',z=ret.charAt(3)-'0';
        if(ret.charAt(0)=='1'){
            return alu.add(ret.toString(),"00110");//1直接保留
        }
        else if((x&(y|z))==1){
            return "1"+alu.add(ret.toString().substring(1,5),"0110"); //说明进位
        }
        return ret.toString();
    }
    private static String reverse(String tar,int bits){
        tar=tar.substring(32-bits*4,32);//取bits位
        StringBuilder reverse=new StringBuilder();
        for(int i=0;i<=tar.length()-4;i+=4){
            String tmp=bitAdd(tar.substring(i,i+4),"0110","0","not_carry")
                    .substring(1,5)
                    .replaceAll("1","2").replaceAll("0","1").replaceAll("2","0");
            if(i==tar.length()-4)
                tmp=bitAdd(tmp,"0001","0","not_carry").substring(1,5);
            reverse.append(tmp);
            //反转时不用处理进位,not_carry
        }
        return "1100"+ String.format("%28s",reverse.toString()).replaceAll(" ","0");  //返回正数化的负数
    }
    private static int getBit(String tar){
        int cnt=0;
        for(int i=4;i<28;i+=4){
            if(tar.substring(i,i+4).equals("0000")) {
                cnt++;
                continue;
            }
            break;
        }
        return 7-cnt;
    }//算位数

    /**
     *
     * @param a A 32-bits NBCD String
     * @param b A 32-bits NBCD String
     * @return a + b
     */
    String add(String a, String b) {
        StringBuilder ret=new StringBuilder();
        if(a.substring(0,4).equals(b.substring(0,4))){  //同号
            String c="0";
            for(int i=31;i>3;i-=4){
                String temp=bitAdd(a.substring(i-3,i+1),b.substring(i-3,i+1),c);
                if(temp.charAt(0)=='1')
                    c="1";
                else c="0";
                ret.insert(0,temp.substring(1,5));
            }
            return ret.insert(0,a.substring(0,4)).toString();
        }
        else{
            String temp;
            if(a.substring(0,4).equals("1100")){
                temp=a;
                a=b;
                b=temp;
            }
            int bits=Math.max(getBit(a),getBit(b));
            temp=add(reverse(a,bits),b);
            if(temp.substring(28-4*bits,32-4*bits).equals("0001"))
                return temp.replaceFirst("0001","0000");
            else
                return reverse(temp,bits).replaceFirst("1100","1101");
        }
    }

    /***
     *
     * @param a A 32-bits NBCD String
     * @param b A 32-bits NBCD String
     * @return b - a
     */
    String sub(String a, String b) {
        return add(a.substring(0,4).equals("1100")?"1101"+a.substring(4,32):"1100"+a.substring(4,32),b);
    }

}

最后编辑于：2019.10.14 11:51:09

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,980评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,178评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,868评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,498评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,492评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,521评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,910评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,569评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,793评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,559评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,639评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,342评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,931评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,904评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,144评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,833评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,350评论 2赞 342

Programming 02

题目大意

ALU.java代码

二进制浮点数加减法

NBCD加减法

推荐阅读更多精彩内容

`ALU.java`代码