implication

计算机基础实验_lab1（CSAPPdatalab）

NPU_CS_DataLab

计算机系统基础实验_数据表⽰

使⽤限制的操作符，来完成⼀些任务，主要考察了移位运算等。如果能⾃⼰认真完成，⼀定会⾮常有收获，会对计算机底层⼀些东西实现和

编码的概念有着⼀个感性的认识，尤其是浮点数那三道题，会让你对IEEE754标准定义的浮点数有着极为深刻的认识。

这个实验为⼀个⼯程，但我们只需要写bits.c⾥⾯的⼀些函数，整个框架是搭好的。然后整个⼯程智能化程度挺⾼的，不满⾜条件都没法

make。

这个⼯程要在ubuntu32位机器上运⾏，可以安装虚拟机，也可以在ubuntu64位上安装32位的包。

下⾯时bits.c⾥⾯的⼀些函数。

/*

*bitAnd-x&yusingonly~and|

*Example:bitAnd(6,5)=4

*Legalops:~|

*Maxops:8

*Rating:1

*/

intbitAnd(intx,inty){

intans=~((~x)|(~y));

returnans;

}

有点离散数学基础知识应该就可以完成。

its

/*

*upperBits-padsnupperbitswith1's

*Youmayassume0<=n<=32

*Example:upperBits(4)=0xF0000000

*Legalops:!~&^|+<<>>

*Maxops:10

*Rating:1

*/

intupperBits(intn){

inta=1<<31;

intb=n+(~0);

intk=((!!n)<<31)>>31;

returnk&(a>>b);

}

重点在于处理n为32的情况

nBit

/*

*anyEvenBit-return1ifanyeven-numberedbitinwordtto1

*ExamplesanyEvenBit(0xA)=0,anyEvenBit(0xE)=1

*Legalops:!~&^|+<<>>

*Maxops:12

*Rating:2

*/

intanyEvenBit(intx){

return!!((x|(x>>8)|(x>>16)|(x>>24))&0x55);

}

itPos

/*

*leastBitPos-returnamaskthatmarksthepositionofthe

*==0,return0

*Example:leastBitPos(96)=0x20

*Legalops:!~&^|+<<>>

*Maxops:6

*Rating:2

*/

intleastBitPos(intx){

return(~x+1)&x;

}

题意为⽤⼀个1标记出最低有效位的位置。

如：96：01100000（int为32位，现为简写）

则返回：00100000

精髓在于取反加⼀。然后进⾏简单的掩码操作便可。

ap

/*

*byteSwap-swapsthenthbyteandthemthbyte

*Examples:byteSwap(0x12345678,1,3)=0x56341278

*byteSwap(0xDEADBEEF,0,2)=0xDEEFBEAD

*Youmayassumethat0<=n<=3,0<=m<=3

*Legalops:!~&^|+<<>>

*Maxops:25

*Rating:2

*/

intbyteSwap(intx,intn,intm){

intxn=n<<3;

intxm=m<<3;

intx1=(x>>xn)<

intx2=(x>>xm)<

intans=(x&(~(0xff<

returnans;

}

⾼低字节交换，然后进⾏掩码。

qual

/*

*isNotEqual-return0ifx==y,and1otherwi

*Examples:isNotEqual(5,5)=0,isNotEqual(4,5)=1

*Legalops:!~&^|+<<>>

*Maxops:6

*Rating:2

*/

intisNotEqual(intx,inty){

return!!(x^y);

}

利⽤异或的特性，再⽤逻辑操作符将结果转化为0或1的逻辑值。

_neg

/*

*float_neg-Returnbit-levelequivalentofexpression-ffor

*floatingpointargumentf.

*Boththeargumentandresultarepasdasunsignedint's,but

*theyaretobeinterpretedasthebit-levelreprentationsof

*single-precisionfloatingpointvalues.

*WhenargumentisNaN,returnargument.

*Legalops:Anyinteger/unsignedoperationsincl.||,&&.alsoif,while

*Maxops:10

*Rating:2

*/

unsignedfloat_neg(unsigneduf){

unsignedresult=uf^0x80000000;//使⽤按位异或和掩码对符号位取反其余为不变

unsignedtmp=uf&0x7fffffff;//为下⼀步看是不是NaN数准备

if(tmp>0x7f800000)//若满⾜条件则尾数⾮零，全1阶码

result=uf;//是NaN数，返回原值，否则返回原数符号位取反对应的数

returnresult;

}

解释看注释。

ation

/*

*implication-returnx->yinpropositionallogic-0forfal,1

*fortrue

*Example:implication(1,1)=1

*implication(1,0)=0

*Legalops:!~^|

*Maxops:5

*Rating:2

*/

intimplication(intx,inty){

return(!x)|(!!y);

}

离散数学基础知识。

k

/*

*bitMask-Generateamaskconsistingofall1's

*lowbitandhighbit

*Examples:bitMask(5,3)=0x38

*Assume0<=lowbit<=31,and0<=highbit<=31

*Iflowbit>highbit,thenmaskshouldbeall0's

*Legalops:!~&^|+<<>>

*Maxops:16

*Rating:3

*/

intbitMask(inthighbit,intlowbit){

inti=~0;

return(((i<

}

题意为lowbit道highbit之间全为1。

例bitmask(5,3)应返回第三位到第五位为1其余为为0的⼀个int型变量。

即0x38:00111000

没啥说的，⾃⼰看代码，巧⽤移位吧。

ional

/*

*conditional-sameasx?y:z

*Example:conditional(2,4,5)=4

*Legalops:!~&^|+<<>>

*Maxops:16

*Rating:3

*/

intconditional(intx,inty,intz){

intm=~!x+1;

return(y&~m)|(z&m);

}

类似于数字逻辑⾥的多路选择器，学了数字逻辑应该就简单了。

OrEqual

/*

*isLessOrEqual-ifx<=ythenreturn1,elreturn0

*Example:isLessOrEqual(4,5)=1.

*Legalops:!~&^|+<<>>

*Maxops:24

*Rating:3

*/

intisLessOrEqual(intx,inty){

intsignx=x>>31;

intsigny=y>>31;

intsameSign=(!(signx^signy));

return(sameSign&((x+(~y))>>31))|((!sameSign)&signx);

}

学了数电也应该感觉⽐较简单。

tive

/*

*isPositive-return1ifx>0,return0otherwi

*Example:isPositive(-1)=0.

*Legalops:!~&^|+<<>>

*Maxops:8

*Rating:3

*/

intisPositive(intx){

return!((x>>31)|(!x));

}

⽐较简单，主要是处理符号位，但对0要特殊处理。

3

/*

*satMul3-multipliesby3,saturatingtoTminorTmaxifoverflow

*Examples:satMul3(0x10000000)=0x30000000

*satMul3(0x30000000)=0x7FFFFFFF(SaturatetoTMax)

*satMul3(0x70000000)=0x7FFFFFFF(SaturatetoTMax)

*satMul3(0xD0000000)=0x80000000(SaturatetoTMin)

*satMul3(0xA0000000)=0x80000000(SaturatetoTMin)

*Legalops:!~&^|+<<>>

*Maxops:25

*Rating:3

*/

intsatMul3(intx){

inttwo=x<<1;

intthree=two+x;

intxSign=x&(0x80<<24);

inttwoSign=two&(0x80<<24);

intthreeSign=three&(0x80<<24);

intmask=((xSign^twoSign)|(xSign^threeSign))>>31;

intsmask=xSign>>31;

return(~mask&three)|(mask&((~smask&~(0x1<<31))|(smask&(0x80<<24))));

}

注意溢出的判断与处理，我好像也⽤了数电⾥⾯多路选择器的思想。

_half

/*

*float_half-Returnbit-levelequivalentofexpression0.5*ffor

*floatingpointargumentf.

*Boththeargumentandresultarepasdasunsignedint's,but

*theyaretobeinterpretedasthebit-levelreprentationof

*single-precisionfloatingpointvalues.

*WhenargumentisNaN,returnargument

*Legalops:Anyinteger/unsignedoperationsincl.||,&&.alsoif,while

*Maxops:30

*Rating:4

*/

unsignedfloat_half(unsigneduf){

intround,S,E,maskE,maskM,maskS,maskEM,maskSM,tmp;

round=!((uf&3)^3);//处理精度问题，进⾏舍⼊时需要的参数

maskS=0x80000000;

maskE=0x7F800000;

maskM=0x007FFFFF;

maskEM=0x7FFFFFFF;

maskSM=0x807FFFFF;

E=uf&maskE;//⽤于判断是否为NaN数

S=uf&maskS;//去符号位

if(E>0x7F800000)returnuf;//阶码全1，⾮0尾数，NaN数直接返回

if(E==0x00800000){//阶码只有最后⼀位为1，除2之后要变为⾮规格化数，按⾮//规格化数处理，即处理阶码下溢情况

returnS|(round+((uf&maskEM)>>1));

}

if(E==0x00000000){//阶码全0，那要么是0，要么是⾮规格化数，直接右移⼀位同时保留符号位

tmp=(uf&maskM)>>1;

returnS|(tmp+round);

}

return(((E>>23)-1)<<23)|(uf&maskSM);//规格化数，正常处理，阶码减⼀

}

这个考察了相当细致了，要对IEEE754标准定义的浮点数有着深刻的理解，对阶码的各种情况对应的不同意义要了解。参考了某位⼤神的博

客才过的这道题。

_i2f

/*

*float_i2f-Returnbit-levelequivalentofexpression(float)x

*Resultisreturnedasunsignedint,but

*itistobeinterpretedasthebit-levelreprentationofa

*single-precisionfloatingpointvalues.

*Legalops:Anyinteger/unsignedoperationsincl.||,&&.alsoif,while

*Maxops:30

*Rating:4

*/

unsignedfloat_i2f(intx){

intsign=x>>31&1;//取符号位

inti;

inte;//阶码

intf=0;//尾数

intd;

intf_mask;

if(x==0)

returnx;//为0的话，全零阶码，全零尾数，符号位取为0，便可直接返回x。

elif(x==0x80000000)

e=158;

el

{

if(sign)

x=-x;//负数，取其对应正数

i=30;

while(!(x>>i))

i--;//计算机阶码，看权重最⼤的不为零的数是第⼏位

e=i+127;//加上偏置常数得到阶码

x=x<<(31-i);//向左移位⾄最⾼

f_mask=0x7fffff;

f=f_mask&(x>>8);//向右算术移位8位

x=x&0xff;//准备判断如何舍⼊

d=x>128||((x==128)&&(f&1));//⼤于256的⼀半，或者等于128

//同时差⼀位就被移出去的那⼀位为1的话(意为向偶数舍⼊)，d=1,

f+=d;//按IEEE754标准对尾数f进⾏修正

if(f>>23)//如果因为修正（+1）导致f超过23位，应该是将最⾼的那⼀位//置0，然后阶码加1

{

f&=f_mask;

e+=1;

}

}

return(sign<<31)|(e<<23)|f;//得到结果

}

按照定义做不是⾮常难，但有⼀个⾮常难受的地⽅，就是尾数只⽤23位，加上隐藏位最多表⽰24位有效数字，所以由int型向其转化时就会

产⽣截断误差，就要进⾏舍⼊，IEEE754标准规定为⼩于⼀半向0舍⼊，⼤于⼀半向1舍⼊，等于⼀半像偶数舍⼊，这⼀点做好，然后按照

定义分别求符号位，阶码，尾数应该就不难了。参考了某位⼤神的代码才完成此题。

yBits

/*howManyBits-returntheminimumnumberofbitsrequiredtoreprentxin

*two'scomplement

*Examples:howManyBits(12)=5

*howManyBits(298)=10

*howManyBits(-5)=4

*howManyBits(0)=1

*howManyBits(-1)=1

*howManyBits(0x80000000)=32

*Legalops:!~&^|+<<>>

*Maxops:90

*Rating:4

*/

inthowManyBits(intx){

intt=x^(x>>31);

intZero=!t;

intnotZeroMask=(!(!t)<<31)>>31;

intbit_16,bit_8,bit_4,bit_2,bit_1;

bit_16=!(!(t>>16))<<4;

t=t>>bit_16;

bit_8=!(!(t>>8))<<3;

t=t>>bit_8;

bit_4=!(!(t>>4))<<2;

t=t>>bit_4;

bit_2=!(!(t>>2))<<1;

t=t>>bit_2;

bit_1=!(!(t>>1));

t=bit_16+bit_8+bit_4+bit_2+bit_1+2;

returnZero|(t¬ZeroMask);

}

这个题也挺难的。。。

⼀开始也没想到⽤⼆分法，卡了好久，想到也该就不难了。

2sm

/*

*tc2sm-Convertfromtwo'scomplementtosign-magnitude

*wheretheMSBisthesignbit

*Youcanassumethatx>TMin

*Example:tc2sm(-5)=0x80000005.

*Legalops:!~&^|+<<>>

*Maxops:15

*Rating:4

*/

inttc2sm(intx){

intsign=x&(0x80<<24);

intmask=~(sign>>31);

returnsign|((~mask)&(~x+1))|(mask&x);

}

编码⽅式的简单转化，⽐较简单。