深入理解計(jì)算機(jī)系統(tǒng)第二版家庭作業(yè)答案

深入理解計(jì)算機(jī)系統(tǒng)(第二版)家庭作業(yè)第二章

深入理解計(jì)算機(jī)系統(tǒng)二進(jìn)制

2.55-2.57?

略

2.58

int?is_little_endian(){

????int?a=?1;

????return?*((char*)&a);

}

2.59

(x&OxFF)|(y&~OxFF)

2.60

unsigned?replace_byte(unsigned?x,?unsigned?char?b,?int?i)

(

????return?(x?&?"(OxFF?(i?3)))?|?(b???(i?3));

}

2.61

A.!~x

B.!x

C.!~(x>>((sizeof(int)-1)?3))

D.!(x&OxFF)

注意，英文版中C是最低字節(jié)，D是最高字節(jié)。中文版恰好反過來了。這里是按中文版來

做的。

2.62

這里我感覺應(yīng)該是英文版對的，int_shifts_are_arithmetic()

int?int_shifts_are_arithmetic(){

????int?x=?-1;

????return?(x?l)?==?-1;

)

2.63

對于sra,主要的工作是將xrsl的第w-k-1位擴(kuò)展到前面的高位。

這個可以利用取反加1來實(shí)現(xiàn)，不過這里的加1是加1?(W-k-1)o

如果x的第w-k-1位為0,取反加1后，前面位全為0,如果為1,取反加1后就全是1。

最后再使用相應(yīng)的掩碼得到結(jié)果。

對于srl,注意工作就是將前面的高位清0,即xsra&(l?(w-k)-1)o額外注意k==0

時(shí)，不能使用l?(w-k),于是改用2?(w-kT)。

?

int?sra(int?x,?int?k){

????int?xsrl=?(unsigned)?x???k;

????int?w=?sizeof(int)?3;

????unsignedz=?1???(w-k-1);

????unsignedmask=z?-?l;

????unsignedright=mask?&?xsrl;

????unsignedleft=?~mask?&?(~(z&xsrl)?+?z);

????return?left?|?right;

int?srl(unsignedx,?int?k){

????int?xsra=?(int)?x?>>?k;

????int?w=?sizeof(int)*8;

????unsignedz=?2???(w-k-l);

????return?(z?-?l)?&?xsra;

}

2.64

int?any_even_one(unsignedx){

????return?!!(x?&?());

)

2.65

int?even_ones(unsignedx){

????x?"=?(x??16);

????x?”=?(x??8);

????x?”=?(x??4);

????x?”=?(x??2);

????x?”=?(x??1);

????return?!(x&l);

)?

x的每個位進(jìn)行異或，如果為0就說明是偶數(shù)個1,如果為1就是奇數(shù)個1。

那么可以想到折半縮小規(guī)模。最后一句也可以是return(x*l)&l

2.66

根據(jù)提示想到利用或運(yùn)算，將最高位的1或到比它低的每一位上，忽然想如果X就是該如

何讓每一位都為1。于是便想到了二進(jìn)擴(kuò)展。先是X右移1位再和原X進(jìn)行或，變成

1100000...,再讓結(jié)果右移2位和原結(jié)果或，變成，最后到16位，變成。

int?leftmost_one(unsignedx){

????x?|=?(x???l);

????x?=?(x???2);

????x?|=?(x???4);

????x?=?(x???8);

????x?|=?(x???16);

????return?x"(X>>1);

}

2.67

A.32位機(jī)器上沒有定義移位32次。

B.beyondjnsb變?yōu)??31o

C.定義a=1?15;a<<=15;set_msb=a<<l;beyond_msb=a?2;

2.68

感覺中文版有點(diǎn)問題，注釋和函數(shù)有點(diǎn)對應(yīng)不上，于是用英文版的了。

個人猜想應(yīng)該是讓x的最低n位變1。

int?lower_one_mask(int?n){

????return?(2?(n-1))?-?1;

2.69

unsigned?rotate_right(unsignedx,?int?n){

????int?w=?sizeof(unsigned)*8;

????return?(x?n)?|?(x?(w-n-l)?1);

)

2.70

這一題是看x的值是否在-2?nT)到2"(n-l)-1之間。

如果x滿足這個條件，則其第n-l位就是符號位。如果該位為0,則前面的w-n位均為0,

如果該位為1,則前面的w-n位均為1。所以本質(zhì)是判斷，x的高w-n+l位是否為0或者為

-1O

int?fits_bits(int?x,?int?n){

????x??=?(n-l);

????return?!x?I|?!("x);

)

2.71

A.得到的結(jié)果是unsigned,而并非擴(kuò)展為signed的結(jié)果。

B.使用int,將待抽取字節(jié)左移到最高字節(jié)，再右移到最低字節(jié)即可。

int?xbyte(unsignedword,?int?bytenum){

????int?ret=word???((3?-?bytenum)?3);

????return?ret???24;

)

2.72

A.size1是無符號整數(shù)，因此左邊都會先轉(zhuǎn)換為無符號整數(shù)，它肯定是大于等于0的。

B.判斷條件改為if(maxbytes>0&&maxbytes>=sizeof(val))

2.73

請先參考2.74題。

可知：t=a+b時(shí)，如果a,b異號(或者存在0),則肯定不會溢出。

如果a,b均大于等于0,則t<0就是正溢出，如果a,b均小于0,則t〉=0就是負(fù)溢出。

于是，可以利用三個變量來表示是正溢出，負(fù)溢出還是無溢出。

int?saturating_add(int?x,?int?y){

????int?w=?sizeof(int)<<3;

????int?t=x?+?y;

????int?ans=x?+?y;

????x?=(w-l);

????y?=(w-l);

????t?=(w-l);

????int?pos_ovf=?~x&~y&t;

????int?neg_ovf=

????int?novf=?~(pos_ovf|neg_ovf);

????return?(pos_ovf&INT_MAX)?|?(novf&ans)?|?(neg_ovf&INT_MIN);

)?

2.74

對于有符號整數(shù)相減，溢出的規(guī)則可以總結(jié)為：

t=a-b;

如果a,b同號，則肯定不會溢出。

如果a>=0&&b<0,則只有當(dāng)t<=0時(shí)才算溢出。

如果a〈0&&b>=0,則只有當(dāng)t>=0時(shí)才算溢出。

不過，上述t肯定不會等于0,因?yàn)楫?dāng)a,b不同號時(shí)：

1)a!=b,因此a-b不會等于0。

2)a-b<=abs(a)+abs(b)<=abs(TMax)+abs(TMin)=(2*w-1)

所以，a,b異號，t,b同號即可判定為溢出。

int?tsub_ovf(int?x,?int?y){

????int?w=?sizeof(int)<<3;

????int?t=x?-?y;

????x?=(w-l);

????y?=(w-l);

????t?=(w-l);

????return?(x?!=y)&&(y==t);

)

順便整理一下匯編中CF,OF的設(shè)定規(guī)則(個人總結(jié)，如有不對之處，歡迎指正)。

t=a+b;

CF:(unsignedt)<(unsigneda)進(jìn)位標(biāo)志

OF:(a<0==b<0)&&(t<0!=a<0)

t=a-b;

CF:(a<0&&b>=0)||((a<0==b<0)&&t<0)退位標(biāo)志

OF:(a<0!=b<0)&&(b<0==t<0)

匯編中，無符號和有符號運(yùn)算對條件碼(標(biāo)志位)的設(shè)定應(yīng)該是相同的，但是對于無符號

比較和有符號比較，其返回值是根據(jù)不同的標(biāo)志位進(jìn)行的。

詳情可以參考第三章3.6.2節(jié)。

2.75

根據(jù)2T8,不難推導(dǎo)，(x'*y')_h=(x*y)_h+x(wT)*y+y(wT)*x。

unsigned?unsigned_high_prod(unsignedx,?unsignedy){

????int?w=?sizeof(int)<<3;

????return?signed_high_prod(x,?y)?+?(x>>(w-1))*y?+?x*(y>>(w-l));

)

當(dāng)然，這里用了乘法，不屬于整數(shù)位級編碼規(guī)則，聰明的辦法是使用int進(jìn)行移位，并使

用與運(yùn)算。即((int)x?(w-l))&y和((int)y?(w-l))&x?

注:不使用longlong來實(shí)現(xiàn)signed_high_prod(intx,inty)是一件比較復(fù)雜的工作,

而且我不會只使用整數(shù)位級編碼規(guī)則來實(shí)現(xiàn)，因?yàn)樾枰褂醚h(huán)和條件判斷。

下面的代碼是計(jì)算兩個整數(shù)相乘得到的高位和低位。

int?uadd_ok(unsignedx,?unsignedy){

????return?x?+?y?>=x;

)

void?signed_prod_result(int?x,?int?y,?int?&h,?int?&l){

????int?w=?sizeof(int)<<3;

????h=?0;

????!=?(y&l)?x:0;

????for(int?i=l;?i<w;?i++){

????????if(?(y?i)&l?)?{

????????????h?+=?(unsigned)x?(w-i);

????????????if(!uadd_ok(1,?x?i))?h++;

????????????!?+=?(x?i);

99999999}

????}

????h=h?+?((x?(w-1))*y)?+?((y?(w-1))*x);

)

最后一步計(jì)算之前的h即為unsigned相乘得到的高位。

sign_h=unsign_h-((x>>(w-1))&y)-((y?(w-1))&x);

sign_h=unsign_h+((x>>(w-1))*y)+((y?(w-1))*x);

2.76

A.K=5:(x?2)+x

B.K=9:(x?3)+x

C.K=30:(x?5)-(x?l)

D.K=-56:(x?3)-(x?6)

2.77

先計(jì)算x>>k,再考慮舍入。

舍入的條件是x<O&&x的最后k位不為Oo

int?divide_power2(int?x,?int?k){

????int?ans=x>>k;

????int?w=?sizeof(int)?3;

????ans?+=?(x?(w-l))?&&?(x&((l?k)-l));

????return?ans;

}?

2.78

這相當(dāng)于計(jì)算((x<<2)+x)?3,當(dāng)然，需要考慮x為負(fù)數(shù)時(shí)的舍入。

先看上述表達(dá)式，假設(shè)x的位模式為[b(w-l),b(w-2),,b(0)],那么我們需要計(jì)算：

[b(w-l),b(w-2),b(w-3),?...??,b(0),?0,??0]

+???????[b(w-l),b(w-2),...,b(2))?b(l),b(0)]

最后需要右移3位。因此我們可以忽略下方的b(l),b(0)o

于是就計(jì)算(x>>2)+x,再右移一位即是所求答案。

不過考慮到(x〉>2)+x可能也會溢出，于是就計(jì)算(x>>3)+(x?l),這個顯然是不會溢

出的。再看看b(0)+b(2)會不會產(chǎn)生進(jìn)位，如果產(chǎn)生進(jìn)位，則再加一。

最后考慮負(fù)數(shù)的舍入。負(fù)數(shù)向0舍入的條件是x〈0&&((x?2)+x的后三位不全為0)。滿

足舍入條件的話，結(jié)果再加1。容易證明，加法后三位不全為0可以等價(jià)為x后三位不全

為0o

???

int?mul5div8(int?x){

????int?b0=x&l,?b2=?(x?2)&l;

????int?ans=?(x?3)?+?(x?l);

????int?w=?sizeof(int)?3;

????ans?+=?(b0&b2);

????ans?+=?((x?(w-l))?&&?(x&7));

????return?ans;

)?

2.79

不懂題意，感覺就是2.78。

2.80

A.1[w-n]0[n]:?^((l?n)-1)

B.0[w-n-m]1[n]0[m]:((l?n)-1)?m

2.81

A.false,當(dāng)x=0,y=TMin時(shí)，x>y,而-y依然是Tmin,所以-x>-y0

B.true,補(bǔ)碼的加減乘和順序無關(guān)(如果是右移，則可能不同)。

C.false,當(dāng)x=T,y=l時(shí)，~x+~y=OxFFFFFFFE,而~&+丫)==OxFFFFFFFF。

D.true,無符號和有符號數(shù)的位級表示是相同的。

E.true,最后一個bit清0,對于偶數(shù)是不變的，對于奇數(shù)相當(dāng)于T,而TMin是偶數(shù),

因此該減法不存在溢出情況。所以左邊總是<=x。

2.82

A.令x為無窮序列表示的值，可以得到x*2~k=Y+Xo

所以x=Y/(2"k-Do

B.(a)1/7,(b)9/15=3/5,(c)7/63=1/9

2.83

浮點(diǎn)數(shù)的一個特點(diǎn)就是，如果大于0,則可以按unsigned位表示的大小排序。

如果小于0則相反。注意都為0的情況即可。

所以條件是：

((ux?l)==0&&(uy?l)==0)||?

(!sx&&sy)||?

(!sx&&!sy&&ux>=uy)

(sx&&sy&&ux<=uy);

2.84

A.5.0,5表示為101,因此位數(shù)M就是1.01為1.25,小數(shù)f為0.01=0.25。指數(shù)部分

應(yīng)該為E=2,所以其指數(shù)部分位表示為e=(2Xk-l)-l)+2=2'(k-l)+lo

位表示三個部分分別是s-e-f,為0-10..01-0100..0o

B.能被準(zhǔn)確描述的最大奇數(shù)，那么其M=L11L.1,故f部分全為1,E應(yīng)該為n。當(dāng)然，這

個假設(shè)在2?kT)>=n的情況下才能成立。這時(shí),s=0,e=n+27k-l)-l,f=ll...l0值為

2(n+1)-1o

C.最小的規(guī)格化數(shù)為2X1-bias)即2”(-2,(kT)+2),所以其倒數(shù)值V為2、(2?卜1)-2),

所以M為L00000,f部分為全0,E=2"(k-l)-2,e部分為2-。-0-2+bias=26-3,

即為11..101o位表示為0-11..101-00..0o

2.85

擴(kuò)展精度

描述

值十進(jìn)制

最小的正非規(guī)格化數(shù)2"(-63)*2"(-2"14+2)3.6452e-4951

最小的正規(guī)格化數(shù)2*(-2*14+2)3.3621e-4932

最大的規(guī)格化數(shù)(2^64-1)*272'14-1-63)1.1897e+4932

2.86

描述HexMEV

-00x80000-62——

最小的值＞10x3F01257/2560257*2"(-8)

2560x470018——

最大的非規(guī)格化數(shù)OxOOFF255/256-62255*2*(-70)

-infOxFFOO——————

Hex為0x3AA00x3AA0416/256-5416*2"(-13)=13*2"(-8)

2.87

格式A格式B

位值位值

101110001-9/16101100010-9/16

010110101208011101010208

100111110-7/1024100000111-7/1024

0000001016/2-170000000000

111011000-4096111110000-inf

011000100768011110000inf

沒有特別明白轉(zhuǎn)換成最接近的，然后又說向+inf舍入的含義。

按理說，舍入到+inf就是向上舍入，而并不是找到最接近的。

表格中是按最接近的進(jìn)行舍入，并且如果超出范圍則認(rèn)為是info

如果都按+inf進(jìn)行舍入，那么第四行格式B將是000000001?

2.88

A.false,float只能精確表示最高位1和最低位的1的位數(shù)之差小于24的整數(shù)。所以當(dāng)

x==TMAX時(shí)，用float就無法精確表示，但double是可以精確表示所有32位整數(shù)的。

B.false,當(dāng)x+y越界時(shí)，左邊不會越界，而右邊會越界。

C.true,double可以精確表示所有正負(fù)2.53以內(nèi)的所有整數(shù)。所以三個數(shù)相加可以精確

表示。

D.false,double無法精確表示廠64以內(nèi)所有的數(shù)，所以該表達(dá)式很有可能不會相等。

雖然舉例子會比較復(fù)雜，但可以考慮比較大的值。

E.false,0/0.0為NaN,(非0)/0.0為正負(fù)inf。同號inf相減為NaN,異號inf相減也

為被減數(shù)的info

2.89

float的k=8,n=23obias=2*7-1=127O

最小的正非規(guī)格化數(shù)為2~(1-bias-n)=2~-1490

最小的規(guī)格化數(shù)為2(0-bias)*2=2'-126o

最大的規(guī)格化數(shù)(二的幕)為2、(2'8-2-bias)=2127。

因此按各種情況把區(qū)間分為[TMin,-148][-149,-125][-126,127][128,TMax]。

float?fpwr2(int?x)

(

????/*Resultexponentandfraction*/

????unsignedexp,?frac;

????unsignedu;

????if?(x?<-149)?{

????????/*Toosmall.Return0.0*/

????????exp=?0;

????????frac=?0;

????}?else?if?(x?<?-126)?{

????????/*Denormalizedresult*/

????????exp=?0;

????????frac=?l?(x+149);

????}?else?if?(x?<?128)?(

????????/*Normalizedresult.*/

????????exp=x?+?127;

????????frac=?0;

????}?else?{

????????/*Toobig.Return+oo*/

????????exp=?255;

????????frac=?0;

????}

????/*Packexpandfracinto32bits*/

????u=exp???23?I?frac;

????/*Returnasfloat*/

????return?u2f(u);

)

2.90

A.pi的二進(jìn)制數(shù)表示為：，E=128-127=l,

它表示的二進(jìn)制小數(shù)值為：

B.根據(jù)2.82,可知1/7的表示為0.001001[001]...,

所以22/7為

C.從第9位開始不同。

為了方便測試2.91-2.94,我寫了幾個公共函數(shù)。

typedefunsignedfloat_bits;

float?u2f(unsignedx){

????return?*((float*)&x);

)

unsigned?f2u(float?f){

????return?*((unsigned*)&f);

}

bool?is_float_equal(float_bitsfl,?float?f2){

????return?f2u(f2)?==fl;

}

bool?is_nan(float_bitsfb){

????unsignedsign=fb>>31;

????unsignedexp=?(fb?23)?&?0xFF;

????unsignedfrac=fb&0x7FFFFF;

????return?exp==?0xFF?&&?frac?!=?0;

}

bool?is_inf(float_bitsfb){

????unsignedsign=fb>>31;

????unsignedexp=?(fb?23)?&?0xFF;

????unsignedfrac=fb&0x7FFFFF;

????return?exp==?0xFF?&&?frac==?0;

int?testFun(?float_bits(*funl)(floatbits),??float(*fun2)(float)){

????unsignedx=?0;

????do{?//testforall2-32value

????????float_bitsfb=?funl(x);

????????float?ff=?fun2(u2f(x));

????????if(!is_float_equal(fb,?ff)){

????????????printfC%xerror\n〃，？x);

9

9999999?9?99return0,

99999999)

99999999x++-

????}while(x!=0);

??printf(z，Test0K\n");?

????return?l;

最后的testFun是用來測試funl和fun2是否對每種可能的輸入都輸出相同的值，funl為

題中所要求的函數(shù)，fun2為float版本。這個函數(shù)大概會運(yùn)行2到3分鐘，也可以寫多線

程，利用多核處理器求解。？

2.91

float_bits?float_absval(float_bitsf){

????if(is_nan(f))?return?f;

????else?return?f?&?0x7FFFFFFF;

)

f1oat?f1oat_absval_f(float?f){

????if(is_nan(f2u(f)))?return?f;

????else?return?fabs(f);

}

測試即調(diào)用testFun(float_absval,float_absval_f);

在測試的時(shí)候發(fā)現(xiàn)0x7F800001的時(shí)候不對了。

后來debug了一下，發(fā)現(xiàn)u2f的時(shí)候，會篡改原值。

即令x=0x7F800001o

則￡211(112￡2))會變成0x7FC00001o奇怪的nan,第22位一定是1。

我將f2u和u2f里用memcpy也同樣是不行。

所以，我將testFun中的一個條件變成了：

if(!is_float_equal(fb,ff)&&?!is_nan(fb))

這個bug實(shí)在是不知道怎么回事。想了想，這和高位低位排列是無關(guān)的。這個bug還是之

后再找吧。也有可能是硬件本身的原因了。

注：C庫中也提供了isnan()函數(shù)。

2.92

float_bits?float_negate(float_bitsf){

????if(is_nan(f))?return?f;

????else?return?f";

)

float?float_negate_f(float?f){

????if(isnan(f))?return?f;

????return?-f;

就是將最高位反位。

2.93

f1oatbits?float_half(float_bitsf){

????unsignedsign=f>>31;

????unsignedexp=?(f?23)?&?0xFF;

????unsignedfrac=f&0x7FFFFF;

????if(exp==?0)?return?sign?31?|?((frac?l)?+?((frac&l)&&((frac?l)&1)));

????else?if(exp

==?1)?return?sign?31?|?((?(1?22)?|?(frac?l))?+?((frac&l)&&((frac?l)&1)))?：

????else?if(exp?!=?255)?return?sign?31?|(exp-1)???23?|?frac;

????else?return?f;

)

float?float_half_f(float?f){

????if(!isnan(f))?return?(float)0.5*f;

????else?return?f;

}

需要注意的是，舍入采用的是向偶數(shù)舍入。這也是我在測試的過程中發(fā)現(xiàn)的。(好吧，書

上在浮點(diǎn)數(shù)位級編碼規(guī)則中說過了，眼殘沒看到)

最后，非規(guī)格化的平滑效果讓exp==l時(shí)的程序變得比較簡潔。

2.94

f1oatbits?float_twice(floatbitsf){

????unsignedsign=f>>31;

????unsignedexp=?(f?23)?&?0xFF;

????unsignedfrac=f&0x7FFFFF;

????if(exp==?0)?return?sign?31?|?frac<<l;

????else?if(exp?<?254)?return?sign?31?|?(exp+1)?23?|?frac;

????else?if(exp==?254)?return?sign?31?|?0xFF?23;

????else?return?f;

)

float?float_twice_f(float?f){

????if(!isnan(f))?return?(float)2*f;

????else?return?f;

}

比float_half簡單一些。對于非規(guī)格化的平滑，使用移位就可以了，對于規(guī)格化，只要

exp+1即可，當(dāng)然，如果exp==254,就要返回inf了。

2.95

float_bits?float_i2f(int?i)

(

????if(i==?0)?return?0;

????unsignedx=i>0?i：-i;

????int?sign=i>0?0:1;

????int?w=?sizeof(int)?3;

????int?j;

????for(j=w-l;?j>=0;?j—){?〃找到最高位

????????if(?(x?j)?&?1)?break;

????}

????unsignedbias=?127;

????unsignedexp,?frac;

????exp=bias?+?j;

????if(j?<=?23)?frac=x?(23~j);

????else?{

????????frac=x?(j-23);

????????unsignedmask=?(l?(j-23))?-?1;

????????if(?(x&mask)?>?(1?(j-24))?)?frac++;?//需要舍入到大值

????????else?if(?(x&mask)?==?1?(j-24)??&&??(frac&l))?frac++;?〃舍入到偶數(shù)

????????if(frac==?(l〈〈24))?exp++;?〃舍入到偶數(shù)超過(1?24)-1,指數(shù)需要再加1

????}

????return?sign?31?|?exp?23?|?frac&0x7FFFFF;

}

void?test(){

????int?x=?0;

????do{

????????float_bitsfb=?float_i2f(x);

????????float?ff=?(float)x;

????????if(!is_float_equal(fb,?ff)){

????????????printf("errorin%d:??%x%x\n",?x,?fb,?f2u(ff));

????????????return;

99999999)

999?9?99x++-

????}while(x!=0);

????printfCTest0K\n");

無恥地使用了循環(huán)。我也是一點(diǎn)一點(diǎn)測試修改，才通過的。不過好在大方向都知道，所以

沒有花多少時(shí)間，主要糾結(jié)點(diǎn)還是在舍入那塊。需要特別注意。

2.96

int?float_f2i(float_bitsf){

????unsignedsign=f?31;

????int?exp=?(f?23)?&?0xFF;

????int?frac=?(f&0x7FFFFF)?I?(1?23);

????exp?-=?127;

????if(exp?<?0)?return?O;

????if(exp?>=?31)?return?;?//絕對值不大于2-31(1?31)

????if(exp?>?23)?frac??=?(exp?-?23);

????else?frac??=?(23?-?exp);

????return?sign??-frac:frac;

}

void?test2(){

????int?x=?0;

????do{

????????int?m=?float_f2i(x);

????????int?n=?(int)u2f(x);

????????if(m?!=n){

????????????printf("errorin%x:??%d%d\n",?x,?m,?n);

999999999999return'

99999999)

999?Q?99X++-

????}while(x!=0);

????printf("TestOK\n");

在exp＜0和＞=31上犯了小錯誤。開始寫成＜=0和＞=32了。

其實(shí)1這個整數(shù)就是exp==O的。

而int絕對值不會超過因此1.0000..小數(shù)點(diǎn)右移不會到超過30次(否則就越界

了)，所以exp<=30。而這里剛好用TMin來表示越界，因此不用關(guān)心TMin的表示。

深入理解計(jì)算機(jī)系統(tǒng)(第二版)家庭作業(yè)第三章

3.54

int?decode2(int?x,?int?y,?int?z)

(

????int?ret;

????z?-=y;?//line2

????ret=z;?//line3

????ret??=?15;//line4

????ret??=?15;//line5

????return?ret*(z-x);

)

3.55

大概算法如下：

x的高32位為xh,低32位為xl。

y的符號位擴(kuò)展成32位之后為ys(ys為0或者T)。

dest_h=(xl*ys)_l+(xh*y)_l+(xl*y)_h

dest_l=(xl*y)_l

注意，所有的乘法都是unsigned*unsigned。

也就是說對于1*(T),如果存入兩個寄存器中，那么高32位是0,低32位是-1。?

相當(dāng)于1*(UNSIGNED_MAX)O

3.56

注意n在這里是一個很小的數(shù)，用8位就能表示，也可以用n=n%256表示。

寄存器變量

esi??x

ebx??n

edi??result

edx??mask

int?loop(int?x,?int?n)

(

????int?result=?;

????int?mask;

????for(mask=?1?31;?mask?!=?0;?mask=?((unsigned)mask)?n){

????????result?^=?(mask?&?x);

????}

????return?result;

}

3.57

xp?*xp:O這個語句是不能被編譯成條件傳送語句的。因?yàn)槿绻菞l件傳送語句，那么不論

xp為什么，*xp都會被計(jì)算。

我們要寫一個和該功能完全一樣的能編譯成條件傳送語句的函數(shù)。

于是，我們要想辦法不使用*xp,而使用一個替代的指向0的非空指針。

int?cread_alt(int?*xp)

????int?t=?0;

????int?*p=xp?xp:&t;

????return?*p;

)

3.58

MODE_A:result=?*pl;?*pl=?*p2;?break;

MODE_B:result=?*pl?+?*p2;?*p2=result;?break;

MODE_C:result=?*pl;?*p2=?15;?break;

M0DE_D:?*p2=?*pl;

MODE_E:result=?17;?break;

default:result=?-l;?break;

3.59

int?switch_prob(int?x,?int?n)

(

????int?result=x;

????switch(n)

????{

????????case?0x28:

????????case?0x2a:

????????????result?<<=?3;?break;

????????case?0x2b:

????????????result??=?3;?break;

????????case?0x2c:

????????????result??=?3;?

????????????result?-=x;

????????case?0x2d:

????????????resu1t?*=result;

????????case?0x29:?〃也可以不要

????????default:

????????????result?+=?Oxl1;

999999999999

????}

????return?result;

}

中間有一句話沒明白，匯編第12行l(wèi)eaOxO(%esi),%esi

3.60

對于A[R][S][T],A[i][j][k]的位置是A(,i*S*T+j*T+k,4)。

由匯編代碼可知：

S*T=63;

T=9;

R*S*T=2772/4;

所以得R=ll,S=7,T=9o

3.61

感覺可以用一j，而不是比較j和n。

int?var_prod_ele(int?n,?int?A[n][n],?int?B[n][n],?int?i,?int?k)

(

????int?j=n-1;

????int?result=?0;

????for(;?j!=-l;?—j)

????????result?+=A[i][j]?*?B[j][k];

????return?result;

)

但是這樣得到的結(jié)果仍然會使用到存儲器。

按下面的代碼，循環(huán)里面貌似就沒有用到存儲器。

但是用到了一個常量4,就是增加a的時(shí)候，會add4。

只需要result,a,e,b,4n這五個變量。

int?var_prod_ele(int?n,?int?A[n][n],?int?B[n][n],?int?i,?int?k)

(

????int?result=?0;

????int?*a=?&A[i][0];

????int?*b=?&B[0][k];

????int?*e=?&A[i][n];

????for(;a!=e;)

????{

????????result?+=?*a?*?*b;

9?9999Q9b+=n-

9?9?9999a++-

????}

????return?result;

}

下面是其匯編代碼的循環(huán)部分：

edi是4*n,ebx和edx分別是b和a,esi是e,eax是result。

ecx是用于存儲乘法的寄存器。

L4:

movl?(%ebx),%ecx

imull?(%edx),%ecx

addl?%ecx,%eax

addl?%edi,%ebx

addl?$4,%edx

cmpl?%edx,%esi

jneL4

我怎么感覺前面那個程序，編譯器應(yīng)該也會自動優(yōu)化。。。

3.62

M=76/4=19;

i在edi中，j在ecx中;

int?transpose(int?M,?int?A[M][M])

(

????int?i,j;??

????for(i=0;?i<M;?++i)

????{

????????int?*a=?&A[i][0];

????????int?*b=?&A[0][i];

????????for(j=O;?j<i;?++j)

99999999(

99999?999?9?int?t=?*a-

99999?999?99*a=9*b-

9?9?99999?99*b=f

9999999?9?99++a-

9999999?9?99b9+=M'

99999999)

????}

)

3.63

El(n)在esi中，esi=3n。

E2(n)在ebx中，ebx=4*E2(n)=4*(2n-l)□

所以E2(n)=2n-lo

3.64

這道題比較考驗(yàn)對知識的拓展應(yīng)用能力。

根據(jù)簡單的推測,我們可以知道，imuil的兩個對象是ebx和edx,最后edx移動到了(eax)

中，所以ebx和edx一個是*sl.p,一個是si.v,并且word_sum的12行的eax是result

的prod的地址，也就是result的地址。而eax只在第5行賦值，所以result的地址是在

8(%ebp)中的。也就是說，結(jié)構(gòu)體返回值實(shí)際上是利用類似參數(shù)的變量進(jìn)行傳入(在8(%ebp)),

而傳入的是返回結(jié)構(gòu)體變量的地址。

所以：

A.?

8(%ebp)為result的地址。

12(%ebp)為si.p。

16(%ebp)為si.v。

B.棧中的內(nèi)容如下表，分配的20個字節(jié)用黃底展示（每一行為4個字節(jié)）

y

X

返回地址

保存的ebp（也是當(dāng)前ebp的指向）

s2.sum

s2.prod

si.v

si.p

&s2（word_sum的返回值地址）

在匯編中,沒懂word_sum15:ret$4

以及diff12:subl$4,%esp的意義何在。

可能是為了清除那個result的返回地址。

c.

傳遞結(jié)構(gòu)體參數(shù)就像正常的傳值。結(jié)構(gòu)體的每一個變量可以看做是單獨(dú)的參數(shù)進(jìn)行傳入。

D.

返回結(jié)構(gòu)體的通用策略：將返回變量的地址看做第一個參數(shù)傳入函數(shù)。而不是在函數(shù)中分

配?？臻g給一個臨時(shí)變量，因?yàn)閑ax確實(shí)存不下一個結(jié)構(gòu)體，eax充當(dāng)返回變量的指針的

角色。

3.65

B取四的倍數(shù)的上整數(shù)=80

8+4+(B*2)取四的倍數(shù)的上整數(shù)=28。

所以B的可選值為8和7。

2*A*B取四的上整數(shù)為44,所以A*B的可選值為21和22。

所以A=3,B=7o

3.66

我們用結(jié)構(gòu)體A表示a_structo

首先，根據(jù)第11和12行，可以得到CNT*size(A)=196。

根據(jù)13行，知道ecx+4*edx+8為ap->x[ap->idx]的地址。

ecx存儲的是bp(地址)。

ap的地址是bp+4+i*size(A)

我們知道，ap->x[O]的地址是bp+4+i*size(A)+pos(x),pos(x)為結(jié)構(gòu)體A中x的

偏移。

那么ap->x[ap->idx]的地址是bp+4+i*size(A)+pos(x)+?4*(ap->idx)□

所以4*edx+8=4+i*size(A)+pos(x)+4*(ap->idx)。

所以，不難猜測，pos(x)=4,也就是說，在A中，首先是idx,再是x數(shù)組。

那么，我們看ap->idx在哪里計(jì)算過。

到第10行，edx的結(jié)果是7i+bp[4+28*i],

bp[4+28*i]是什么呢它很可能是bp中的a[i]的首地址。

我們先這樣猜測，于是size(A)=28,并且bp[4+28*i]的值為ap-〉idx。

另一方面：4*edx=28*i+4*bp[4+28*i]=i*size(A)+4*(ap->idx)□

所以，我們的猜想是正確的。

因此，size(A)=28,里面包含了一個intidx和一個數(shù)組intx[6]。

總共有多少個A呢CNT=196/size(A)=7。

3.67

A.?

el.p:0

el.x:4

e2.y:0

e2.next:4

B.

總共需要8個字節(jié)。

c.

不難知道，賦值前后都應(yīng)該是整數(shù)。

edx就是參數(shù)up(一個指針)。

最后結(jié)果是用eax-(edx)得到的，說明(edx)是整數(shù)，即up-〉_為整數(shù)，肯定是表示的

e2.y。

再看看之前的eax,eax是由(eax)所得，說明到第3行后，eax是個指針。

它是由(ecx)得到的，說明ecx在第二行也是個指針。

而ecx是通過*(up+4)得到的，所以ecx是一個union指針next,即up->e2.next;

到第三行，eax為*(ecx)，且是一個指針，所以eax在第三行為int*p,即up->e2.next->el.p0

所以，賦值符號后面的表達(dá)式就為?*(up->e2.next->el.p)-up->e2.y

再看看前面。

最終賦值的地址是ecx+4,而ecx那時(shí)候是一個next指針，而(next+4)必須是一個int,

也不難推測它是el.x。因此前面就為up->e2.next->el.x?

結(jié)果如下：

void?proc(unionele?*up)

(

????up->e2.next->el.x=?*(up->e2.next->el.p)?-?up->e2.y;

)

3.68

版本一：使用getchar

void?good_echo()

????char?c;

????int?x=?0;

????while(?x=getchar(),?x!='\n'?&&?x!=EOF)

????{

????????putchar(x);

????}

)

版本二：使用fgets

void?good_echo()

{

????const?int?BufferSize=?10;

????char?s[BufferSize];

????int?i;

????while(fgets(s,?BufferSize,?stdin)!=NULL)

????{

????????for(i=0;s[i];++i)

???????????putchar(s[i]);

????????if(i<BufferSize-l)?break;

????}

????return;

)

兩種方法對于EOF好像沒效果，就是輸入一定字符后不按回車直接按EOF,沒能正確輸出。

網(wǎng)上查到的資料說，getchar在輸入字符后，如果直接按EOF,并不能退出，只能導(dǎo)致新一

輪的輸入。

需要在最開始輸入的時(shí)候按，即按了回車之后按。

而fgets就不知道了，不按回車，就不添加0。

3.69

long?trace(tree_ptrtp)

(

????long?ret=?0;

????while(tp?!=NULL)

????{

????????ret=tp->val;

????????tp=tp->left;

????}

????return?ret;

}

作用是從根一直遍歷左子樹，找到第一個沒有左子樹的節(jié)點(diǎn)的值。

3.70

long?traverse(tree_ptrtp)

(

????long?v=MAX_L0NG;

????if(tp?!=NULL)

????{

????????v=?min(traverse(tp->left),?traverse(tp->right));?

????????????//Linel6cmovle:if(rl2<rax)rax=rl2;

????????v=?min(v,?tp->v);?//Line20cmovle:if(rax>rbx)rax=rbx;

????}

????return?v;

當(dāng)然，如果要用三目條件表達(dá)式的話：

long?traverse(tree_ptrtp)

(

????long?v=MAX_LONG,?rv,?lv;

????if(tp?!=NULL)

????{

????????lv=?traverse(tp->left);

????????rv=?traverse(tp->right);

????????v=lv?<?rv???lv:rv?;?//Linel6cmovle:if(rl2<rax)rax=rl2;

????????v=v?>?tp->v???tp->v:v?;?//Line20cmovle:if(rax>rbx)rax=rbx;

????}

????return?v;

}

函數(shù)的目的是找到樹的所有節(jié)點(diǎn)的值中最小的一個。

深入理解計(jì)算機(jī)系統(tǒng)(第二版)家庭作業(yè)第四章

4.43

沒有正確執(zhí)行pushl%esp,pushl%esp是將esp當(dāng)前的內(nèi)容入棧。

如果REG是esp,那么代碼是先減去了esp,然后將減了4以后的REG移入了esp。

修改：(我只能想到利用其它的寄存器)

movlREG,%eax

subl$4,%esp

movl%eax,(%esp)

4.44

也沒有正確執(zhí)行popl%esp,因?yàn)閜opl%esp是將當(dāng)前棧頂?shù)闹捣湃雃sp。

如果REG是esp,那么最后得到esp是棧頂值減4之后的值。

movl(%esp),%eax

addl$4,%esp

movl%eax,REG

4.45

我沒有按書上給的例子寫，而是自己寫了一個冒泡。

void?bubble(int?*data,?int?count)

(

????if(count==?0)?return;

????int?i,?j;

????int?*p,?*q;

????for(i=count-l;?i!=0;?i"){

????????p=data,?q=data?+?1;

????????for(j=0;?j!=i;?++j)

99999999{

999999999999if(9*p9>9*q?)

999999999999{

9999999999999999int9t=?*p?

99999999999?9999*p=9*q-

99999999999?9999*q=f

999999999999)

999999999999p++?q++?

99999999}

????}

）

Y86：（movl就沒有區(qū)分那么細(xì)了，因?yàn)樘闊┝?。。。?/p>

data:#（從地地址往高地址）

$5,$2,$7,$4,$3,$6,$1,$8

movl$8,%ecx?

pushl%ecx?#count=8

movldata,%ecx

pushl%ecx#pushdata

callbubble

halt

bubble:

pushl?%ebp

movl?%esp,%ebp

pushl?%esi

pushl?%ebx

pushl?%edx

movl?8（%ebp）,%edx?#edx==data

movl?12(%ebp),%esi?#esi==count

andl?%esi,%esi

je?bubb1eEnd?#count==0

movl$1,%eax

subl?%eax,%esittcount一一

je?bubb1eEnd?#count==1

OuterLoop:

movl?%edx,%ecx?#p=data(ecx)

pushl?%esi#tosaveonereg

InnerLoop:

movl?(%ecx),%eax

movl?4(%ecx),%ebx

subl?%eax,%ebx

movl4(%ecx),%ebx

jg?NoSwap

movl?%eax,%ebx?#swap,soebxisgreater

movl4(%ecx),%eax

NoSwap:

movl?%eax,(%ecx)

movl%ebx,4(%ecx)

movl$4,%eax

addl?%eax,%ecx

movl$1,%eax

subl%eax,%esi

jne?InnerLoop

popl?%esi

movl$1,%eax

subl?%eax,%esi

jne?OuterLoop

bubbleEnd:

popl?%edx

popl?%ebx

popl?%esi

movl?%ebp,%esp

popl?%ebp

ret

4.46

InnerLoop內(nèi)改成：（edx是循環(huán)利用）

movl?(%ecx),%edx

InnerLoop:

movl?%edx,%eax

movl?4(%ecx),%ebx

subl?%ebx,%eax?#compare*pand*(p+l)

cmovl?%ebx,%edx?#edxismax

movl(%ecx),%eax?

cmovg%ebx,%eax??#%eaxismin

movl?%edx,4(%ecx)

movl?%eax,(%ecx)

movl$4,%eax

addl?%eax,%ecx

movl$1,%eax

subl?%eax,%esi

jne?InnerLoop

4.47

我們可以明確的是，這條指令完成的任務(wù)為，

ebp<-M4[cur_ebp]

esp<-cur_ebp+4

取指階段icode:ifun=D:0

????????valP<=PC+1

譯碼階段?valB<=R[%ebp]

執(zhí)行階段?valE<=valB+4??

訪存階段?valM<=M4[valB]

寫回階段?R[%esp]<=valE

?????R[%ebp]<=valM

4.48

取指階段？icode:ifun=Ml[PC]=C:0

??????rA:rB<=M1[PC+1]

??????valC<=M4[PC+2]

????valP<=PC+6

譯碼階段?valB<=R[rB]

執(zhí)行階段?valE<=valB+valC

??????SetCC

訪存階段？

寫回階段?R[rB]<=valE??

4.49

4.50

取指

boolneed_regids=

????icodein{IRRMOVL,IOPL,IPUSHL,IPOPL,

????????????????!IRMOVL,IRMMOVL,IMRMOVL,?IADDL?};

boolneed_valC=

????icodein{IIRMOVL,IRMMOVL,IMRMOVL,IJXX,ICALL,?IADDL?};

譯碼和寫回

intsrcA=[

????icodein{IRRMOVL,IRMMOVL,IOPL,IPUSHL?):rA;

????icodein{?IPOPL,?IRET}:RESP;

????!:RNONE;#Don'tneedregister

]：

intsrcB=[

icodein{IOPL,IRMMOVL,IMRMOVL,?IADDL?}:rB;

icodein{IPUSHL,IPOPL,ICALL,IRET}:RESP;

icodein{ILEAVE}:REBP;

1:RNONE;#Don'tneedregister

]；

intdstE=[

icodein{IRRMOVL)?&&C