題目大意
? 完成以下3種二進(jìn)制下的計算單元
- 整型加減乘位移
ALU.java- 浮點(diǎn)型加減
FPU.java- NBCD碼加減
NBCDU.java
大概看一遍，整型這一塊處理很簡單般渡，后面的相對麻煩一點(diǎn)邻遏，碼了一會把第一個ALUTest.java過掉了，這部分略過。
ALU.java代碼
public class ALU {
// 模擬寄存器中的進(jìn)位標(biāo)志位
private String CF = "0";
// 模擬寄存器中的溢出標(biāo)志位
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,]", "");
} //取補(bǔ)碼的方法
//add two integer
String add(String src, String dest) {
ans=new StringBuilder(); //因?yàn)榘補(bǔ)ns寫成全局的森渐，這里要重置
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冒晰，沒必要繼續(xù)了
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; //減少復(fù)雜度同衣，雖然沒注意看有沒有對應(yīng)的樣例
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();
}
}
二進(jìn)制浮點(diǎn)數(shù)加減法
首先明確二進(jìn)制浮點(diǎn)數(shù)的加減步驟，減的話則是改改符號壶运，其實(shí)都是一個東西耐齐。
- 第一步檢查有沒有0
- 第二步看指數(shù)，這一步要求小的指數(shù)往大的靠（因?yàn)橐Ｗo(hù)主要的部分也就是更大的那個數(shù)的精度）蒋情，這里會將較小的數(shù)的significant部分右移埠况，同時判斷是否全為0了，是的話說明這個數(shù)太小棵癣，直接返回大數(shù)
- 如果能成功對齊指數(shù)辕翰，那么就有符號地相加significant（取決于符號位）
- significant為0，返回0
- significant溢出狈谊，右移并加指數(shù)喜命，檢查指數(shù)有沒有溢出沟沙，溢出報錯
- significant未溢出或溢出但指數(shù)增加后指數(shù)未溢出，則檢查是否標(biāo)準(zhǔn)化壁榕，是則直接輸出矛紫，否則要左移significant（要求以1.開頭），此時要減指數(shù)牌里，并檢查指數(shù)是否下溢出颊咬，溢出報錯，成功結(jié)束則輸出
當(dāng)然也有另外一個方法牡辽，把二進(jìn)制轉(zhuǎn)成float贪染，加好之后再轉(zhuǎn)回去（好想偷懶）
觀察一下FPUTest.java，發(fā)現(xiàn)里面其實(shí)要處理一些特殊的浮點(diǎn)數(shù)催享，比如N_INF和N_NaN之類的杭隙，同時我們發(fā)現(xiàn)樣例的指數(shù)部分無論是輸入還是結(jié)果都是沒有8個0（指數(shù)以0.開頭）的情況的，這可以減少不少工作量因妙。而且注意到這些奇怪的東西都在第一個參數(shù)痰憎，于是又稍微輕松一點(diǎn)。
順著思路來的話攀涵，遇到的需要處理的點(diǎn)：
- 取了一個變量
e=Integer.parseInt(a.substring(1,9))-Integer.parseInt(b.substring(1,9))作為判斷大小以及用來后來右移significant铣耘。考慮如果e小于0說明a更小以故，交換一下ab并把e取相反數(shù)蜗细，e為0說明指數(shù)已經(jīng)對齊 - 在位移significant時，注意到我們是1.significant怒详，位移后會是0.0..1significant炉媒，所以需要先--e并在臨時的sig變量中插入一個1
- 承上，我們在指數(shù)未對齊時已經(jīng)插入了1昆烁，那么最后進(jìn)行significant的加法時吊骤，需要補(bǔ)全小數(shù)點(diǎn)左邊的數(shù)，那么需要一個flag記錄指數(shù)是否是對齊的静尼，對齊的說明之前并沒有插入1白粉，因此此時要插入1，未對齊則說明先前已經(jīng)插入了1鼠渺，現(xiàn)在要插入0.
- significant的有符號加法部分鸭巴，檢查ab的首位符號位面臨兩種情況
- 兩個同號，可能會溢出一位（很顯然不可能溢出兩位）拦盹，后續(xù)需要改指數(shù)部分
- 兩個異號鹃祖，要把負(fù)數(shù)取補(bǔ)碼進(jìn)行加法，如果significant結(jié)果為負(fù)則需要取補(bǔ)碼掌敬，把結(jié)果的符號位置為負(fù)號惯豆，顯然這時候就不用考慮溢出的問題了
順著思路池磁，先打了符號不同的情況奔害，不考慮溢出楷兽，只補(bǔ)一個符號位再取補(bǔ)碼，這時候發(fā)現(xiàn)一個樣例fpuAddTest2()死活過不去华临，經(jīng)過仔細(xì)的研究想了很久才發(fā)現(xiàn)芯杀，需要在后面加4位的保護(hù)位，修改之后就過了雅潭，但是實(shí)際上也沒幾個符號不同的揭厚，所以還要繼續(xù)寫。
經(jīng)過一些簡單的調(diào)整把所有的加法都解決了扶供，之前提過減法只是換符號做加法筛圆，發(fā)現(xiàn)只剩一個樣例fpuSubTest4()沒有通過，發(fā)現(xiàn)這個樣例是零椿浓，特殊判定一下就好了太援，再次測試通過。
以下是代碼
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--; //第一次位移把指數(shù)給加到significant里
sig.append("000");//保護(hù)位
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位二進(jìn)制表達(dá)一個十進(jìn)制數(shù)時存在的超過“10”的問題扳碍，解決方法是檢查二進(jìn)制數(shù)的最高位和中間兩位提岔，從0開始編號也就是S3&(S2|S1)，如果為真則進(jìn)位(+0110)笋敞，下一位+0001碱蒙，依次判斷。
而減法則要把A-B寫成A+(10N-B)夯巷，也就是借位赛惩，值得注意的是這里的(10N需要一個“取反”操作)
寫加法下來發(fā)現(xiàn)要注意進(jìn)位的處理，會有4位的二進(jìn)制溢出趁餐，所以需要擴(kuò)展到5位坊秸。
處理不同號時，為了方便澎怒，把負(fù)數(shù)調(diào)換到a上褒搔，把開頭的0除去方便取反，同時要注意一下這里取反是要ab兩數(shù)位數(shù)的最大位取10的N次冪喷面，所以最終結(jié)果檢查這個最大位數(shù)的高位上是否是0001星瘾，是的話就把它置為0000直接返回，不是的話就取反惧辈。處理了一些代碼上的小bug后琳状，測試通過
public class NBCDU {
// 模擬寄存器中的進(jìn)位標(biāo)志位
private String CF = "0";
// 模擬寄存器中的溢出標(biāo)志位
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"); //說明進(jìn)位
}
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);
//反轉(zhuǎn)時不用處理進(jìn)位,not_carry
}
return "1100"+ String.format("%28s",reverse.toString()).replaceAll(" ","0"); //返回正數(shù)化的負(fù)數(shù)
}
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;
}//算位數(shù)
/**
*
* @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);
}
}
