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

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

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

2.55-2.57

略

2.58

intis_little_endian(){

inta=1;

return*((char*)&a);

2.59

(x&OxFF)|(y&-OxFF)

2.60

unsignedreplace_byte(unsignedx,unsignedcharb,inti)

(

return(x&~(OxFF<<(i<<3)))I(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)該是英文版對(duì)的,int_shifts_are_arithmetic()

intint_shifts_are_arithmetic(){

intx=-1;

return(X>>1)==-1;

)

2.63

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

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

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

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

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

k==0時(shí),不能使用1<<(w-k),于是改用2<<(w-k-1),

intsra(intx,intk){

intxsrl=(unsigned)x>>k;

intw=sizeof(int)<<3;

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

unsignedmask=z-1;

unsignedright=mask&xsrl;

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

returnleft|right;

}

intsrl(unsignedx,intk){

intxsra=(int)x>>k;

intw=sizeof(int)*8;

unsignedz=2<<(w-k-1);

return(z-1)&xsra;

}

2.64

intany_even_one(unsignedx){

return!!(x&(0x55555555));

)

2.65

inteven_ones(unsignedx){

xA=(x?16);

X八=(x?8);

XA=(x?4);

XA=(x?2);

XA=(x?1)；

return!(x&l);

}

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

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

2.66

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

10000000..該如何讓每一位都為1。于是便想到了二進(jìn)擴(kuò)展。先是x右移1位再和原x

進(jìn)行或，變成1100000.…，再讓結(jié)果右移2位和原結(jié)果或，變成11110000.最后

到16位，11111111..

intleftmost_one(unsignedx){

x|=(x>>1);

XI=(x>>2);

x|=(x>>4);

x|=(x>>8);

x|=(x>>16);

returnxA(X>>1);

2.67

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

B.beyond_msb變?yōu)?<<31O

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

2.68

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

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

intlower_one_mask(intn){

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

2.69

unsignedrotate_right(unsignedx,intn){

intw=sizeof(unsigned)*8;

return(x>>n)|(x<<(w-n-1)<<1);

2.70

這一題是看X的值是否在-2八(n-1)到2-(n-1)-1之間。

如果x滿足這個(gè)條件，則其第n-1位就是符號(hào)位。如果該位為0，則前面的w-n位均為0,

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

為

intfits_bits(intx,intn){

x>>=(n-1);

return!xII!(~x);

2.71

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

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

intxbyte(unsignedword,intbytenum){

intret=word<<((3-bytenum)<<3);

returnret>>24;

2.72

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

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

2.73

請(qǐng)先參考2.74題。

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

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

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

intsaturating_add(intx,inty){

intw=sizeof(int)<<3;

intt=x+y;

intans=x+y;

x>>=(w-1);

y>>=(w-1)；

t>>=(w-1)；

intpos_ovf=;

intneg_ovf=x&y&~t;

intnovf=(pos_ovf|neg_ovf);

return(pos_ovf&INT_MAX)|(novf&ans)|(neg_ovf&工NT_M工N);

2.74

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

t=a-b;

如果a,b同號(hào)，則肯定不會(huì)溢出。

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

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

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

1)a!=b，因此a-b不會(huì)等于0。

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

所以，a,b異號(hào)，t,b同號(hào)即可判定為溢出。

inttsub_ovf(intx,inty){

intw=sizeof(int)<<3;

intt=x-y;

x>>=(w-1);

y>>=(w-1);

t>>=(w-1);

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

}

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

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)彳AZ*小^?

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

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

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

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

2.75

根據(jù)2T8,不難推導(dǎo)，(x**y*)_h=(x*y)_h+x(w-1)*y+y(w-1)*xo

unsignedunsigned_high_prod(unsignedx,unsignedy){

intw=sizeof(int)<<3;

returnsigned_high_prod(xfy)+(x>>(w-1))*y+x*(y>>(w-1));

}

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

用與運(yùn)算。即((int)x>>(w-1))&y和((int)y>>(w-1))&x0

注：不使用longlong來實(shí)現(xiàn)sign一d_high_prod(intx,inty)是一件比較復(fù)雜

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

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

intuadd_ok(unsignedx,unsignedy){

returnx+y>=x;

}

voidsigned_prod_result(intx,inty,int&h,int&1){

intw=sizeof(int)<<3;

h=0;

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

for(inti=l;i<w;i++){

if((y?i)&i){

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

if(!uadd_ok(lzx<<i))h++;

1+=(x<<i);

}

)

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)4-((y>>(w-1))*x);

2.76

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

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

C.K=30:(x<<5)-(X<<1)

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

2.77

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

舍入的條件是x〈O&&x的最后k位不為Oe

intdivide_power2(intx,intk){

intans=x>>k;

intw=sizeof(int)<<3;

ans+=(x>>(w-1))&&(x&((l<<k)-1));

returnans;

2.78

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

先看上述表達(dá)式，假設(shè)X的位模式為[b(w-1),b(w-2),...,b(0)],那么我們需要

計(jì)算：

[b(w-1)zb(w-2)zb(w-3),..?，b(0),0r0]

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

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

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

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

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

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

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

為0.

intmul5div8(intx){

intbO=x&l,b2=(x>>2)&1;

intans=(x>>3)+(X>>1);

intw=sizeof(int)<<3;

ans+=(b0&b2);

ans+=((x>>(w-1))&&(x&7));

returnans;

}

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>-yo

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

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

D,true,無符號(hào)和有符號(hào)數(shù)的位級(jí)表示是相同的。

E,true,最后一個(gè)bit清0,對(duì)于偶數(shù)是不變的，對(duì)于奇數(shù)相當(dāng)于-1,而TMin是偶數(shù),

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

2.82

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

所以x=Y/(2-k-1)。

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

2.83

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

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

所以條件是：

((ux<<1)==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.25o指

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

位表示三個(gè)部分分別是s-e-f,為0-10..01-0100..0。

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

AA

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

值為2A(n+D-1.

C.最小的規(guī)格化數(shù)為2A(1-bias)即2A(-2-(k-l)+2),所以其倒數(shù)值V為

2A(2A(k-l)-2)所以M為1.00000工部分為全。E=2-(k-1)-2,e部分為2-(k-1)-2

+bias=2Ak-3,即為11..101。位表示為0-11..101-00..0。

2.85

擴(kuò)展精度

描述

值十進(jìn)制

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

最小的正規(guī)格化數(shù)2A（一2八14+2）3.3621e-4932

最大的規(guī)格化數(shù)（2人64-1）*2人（2人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*2A

2.87

格式A格式B

位值位值

1OHIO001-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)為是inf。

如果都按+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í)，左邊不會(huì)越界，而右邊會(huì)越界。

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

確表示。

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

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

E.false,0/0.0為NaN,(非0)/0.0為正負(fù)info同號(hào)inf相減為NaN,異號(hào)inf

相減也為被減數(shù)的info

2.89

A

float的k=8,n=230bias=27-1=127.

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

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

A

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

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

floatfpwr2(intx)

(

/★Resultexponentandfraction*/

unsignedexp,frac;

unsignedu;

if(x<-149){

/★Toosmall.Return0.0★/

exp=0;

frac=0;

)elseif(x<-126){

/*Denormalizedresult*/

exp=0;

frac=1<<(x+149);

}elseif(x<128){

/*Normalizedresult.*/

exp=x+127;

frac=0;

}else{

/*Toobig.Return+oo*

exp=255;

frac=0;

}

/★Packexpandfracinto32bits*/

u=exp<<23|frac;

/*Returnasfloat*/

returnu2f(u);

}

2.90

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

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

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

所以22/7為11.001001001001001[001]...

C.從第9位開始不同。

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

typedefunsignedfloat_bits;

floatu2f(unsignedx){

return*((float*)&x);

)

unsignedf2u(floatf){

return*((unsigned*)&f);

}

boolis_float_equal(float_bitsfl,floatf2){

returnf2u(f2)==fl;

)

boolis_nan(float_bitsfb){

unsignedsign=fb>>31;

unsignedexp=(fb>>23)&OxFF;

unsignedfrac=fb&0x7FFFFF;

returnexp==OxFF&&frac!=0;

)

boolis_inf(float_bitsfb){

unsignedsign=fb>>31;

unsignedexp=(fb>>23)&OxFF;

unsignedfrac=fb&0x7FFFFF;

returnexp==OxFF&&frac==0;

)

inttestFun(float_bits(*funl)(float_bits)Afloat(*fun2)(float))

(

unsignedx=0;

do{//testforall2A32value

float_bitsfb=funl(x);

floatff=fun2(u2f(x));

if(!is_float_equal(fb,ff)){

printf(H%xerror\nn,x);

return0;

)

x++;

}while(x!=0);

printf(HTestOK\nn);

return1;

最后的testFun是用來測(cè)試funl和fun2是否對(duì)每種可能的輸入都輸出相同的值，fun1

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

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

2.91

float_bitsfloat_absval(float_bitsf){

if(is_nan(f))returnf;

elsereturnf&0x7FFFFFFF;

}

floatfloat_absval_f(floatf){

if(is_nan(f2u(f)))returnf;

elsereturnfabs(f);

}

測(cè)試即調(diào)用testFun(float_absvalrfloat_absval_f);

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

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

即令x=0x7F800001.

則f2u(u2f(x))會(huì)變成0x7FC00001?奇怪的nan,第22位一定是1。

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

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

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

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

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

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

2.92

float_bitsfloat_negate(float_bitsf){

if(is_nan(f))returnf;

elsereturnfA0x80000000;

}

floatfloat_negate_f(floatf){

if(isnan(f))returnf;

return-f;

就是將最高位反位。

2.93

float_bitsfloat_half(float_bitsf){

unsignedsign=f>>31;

unsignedexp=(f>>23)&OxFF;

unsignedfracf&0x7FFFFF;

if(exp

0)returnsign<<31I((frac>>l)+((frac&l)&&((frac>>l)&1)));

elseif(exp

1)returnsign<<31I<<<1<<22)|(frac>>l))+((frac&l)&&((fr

ac>>l)&1)));

elseif(exp!=255)returnsign<<31I(exp-1)<<23|frac;

elsereturnf;

)

floatfloat_half_f(floatf){

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

elsereturnf;

}

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

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

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

2.94

float_bitsfloat_twice(float_bitsf){

unsignedsign=f>>31;

unsignedexp=(f>>23)&OxFF;

unsignedfrac=f&0x7FFFFF;

if(exp==0)returnsign<<31|frac<<l;

elseif(exp<254)returnsign<<31I(exp+l)<<23Ifrac;

elseif(exp==254)returnsign<<31|0xFF<<23;

elsereturnf;

}

floatfloat_twice_f(floatf){

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

elsereturnf;

}

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

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

2.95

float_bitsfloat_i2f(inti)

(

if(i==0)return0;

unsignedx=i>0?i:-i;

intsign=i>0?0:1;

intw=sizeof(int)<<3;

intj;

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=(1<<(j-23))-1;

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

elseif((x&mask)==1<<(j-24)&&(frac&l))frac++；//舍

入到偶數(shù)

if(frac==(1?24))exp++;//舍入到偶數(shù)超過(1<<24)-1,指數(shù)需

要再加1

}

returnsign<<31|exp<<23|frac&0x7FFFFF;

}

voidtest(){

intx=0;

do{

float_bitsfb=float_i2f(x);

floatff=(float)x;

if(!is_float_equal(fb,ff)){

H

printf("errorin%d:%x%x\nzxzfb,f2u(ff));

return;

)

x++;

}while(x!=0);

printf(HTestOK\nn);

}

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

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

2.96

intfloat_f2i(float_bitsf){

unsignedsign=f>>31;

intexp=(f>>23)&OxFF;

intfrac=(f&0x7FFFFF)|(1<<23);

exp-=127;

if(exp<0)return0;

if(exp>=31)return0x80000000;//絕對(duì)值不大于2八31(1<<31)

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

elsefrac>>=(23-exp);

returnsign?-frac:frac;

)

voidtest2(){

intx=0;

do(

intm=float_f2i(x);

intn=(int)u2f(x);

if(m!=n){

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

return;

)

x++;

}while(x!=0);

printf(HTestOK\nn);

}

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

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

而int絕對(duì)值不會(huì)超過2-31-1，因此1.0000..小數(shù)點(diǎn)右移不會(huì)到超過30次（否則就越

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

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

3.54

intdecode2(intx,inty,intz)

(

intret;

z-=y;//line2

ret=z;//line3

ret<<=15;//line4

ret>>=15;//line5

returnret*(zAx);

)

3.55

大概算法如下：

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

V的符號(hào)位擴(kuò)展成32位之后為ys(ys為0或者-1)。

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

dest_l=(xl*y)__1

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

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

相當(dāng)于1*(UNS工GNED_MAX)。

3.56

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

寄存器變量

esix

ebxn

ediresult

edxmask

intloop(intx,intn)

(

intresult=1431655765;

intmask;

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

resultA=(mask&x);

}

returnresult;

)

3.57

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

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

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

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

intcread_alt(int*xp)

(

intt=0;

int*p=xp?xp:;

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;

MODE_D:*p2=*pl;

MODE_E:result=17;break;

default:result=-1;break;

3.59

intswitch_prob(intx,intn)

intresult=x;

switch(n)

(

case0x28:

case0x2a:

result<<=3;break;

case0x2b:

result>>=3;break;

case0x2c:

result<<=3;

result-=x;

case0x2d:

result*=result;

case0x29://也可以不要

default:

result+=0x11;

)

returnresult;

)

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

3.60

對(duì)于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。

intvar_prod_ele(intn,intA[n][n],intB[n][n]tinti,intk)

(

intj=n-1;

intresult=0;

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

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

returnresult;

)

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

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

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

只需要result,a,e,b,4rl這五個(gè)變量。

intvar_prod_ele(intn,intA[n][n],intB[n][n],inti,intk)

(

intresult=0;

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

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

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

for(;a!=e;)

result+=*a**b;

b+=n;

a++;

}

returnresult;

}

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

edi是4*n,ebx和edx分另U是b和a,esi是e,eax是resulto

ecx是用于存儲(chǔ)乘法的寄存器。

L4:

movl(%ebx),%ecx

imull(%edx),%ecx

addl%ecx,%eax

addl%edi,%ebx

addl$4,%edx

cmpl%edx,%esi

jneL4

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

3.62

M=76/4=19;

i在edi中，j在ecx中；

inttranspose(intM,intA[M][M])

(

inti,j;

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

(

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

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

for(j=0;j<i;++j)

intt=*a;

*a=*b;

*b=t;

++a;

b+=M;

}

)

)

3.63

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

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

所以E2(n)=2n-lo

3.64

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

根據(jù)簡(jiǎn)單的推測(cè)，我們可以知道，imull的兩個(gè)對(duì)象是ebx^riedx,最后edx移動(dòng)到了

(eax)中，所以ebx和edx——個(gè)是*sl.p,一個(gè)是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.po

16(%ebp)為si.Vo

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

y

X

返回地址

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

s2.sum

d

si.V

si.p

&s2（word_sum的返回值地址）

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

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

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

C.

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

D.

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

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

色。

3.65

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

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

所以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存儲(chǔ)的是bp(地址)。

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

我們知道，ap->x[0]的地址是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)o

所以，不難猜測(cè)，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]的首地址。

我們先這樣猜測(cè)，于是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,里面包含了一個(gè)intidx和一個(gè)數(shù)組intx[6],

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

3.67

A.

el.p:0

el.x:4

e2.y:0

e2.next:4

B.

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

C.

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

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

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

示的e2.y。

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

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

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

到第三行，eax為*(ecx),且是一個(gè)指針，所以eax在第三行為int*p,即

up->e2.next->el.p。

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

再看看前面。

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

也不難推測(cè)它是el.x。因此前面就為up->e2.next->el.xo

結(jié)果如下：

voidproc(unionele*up)

(

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

)

3.68

版本一：使用getchar

voidgood_echo()

(

charc;

intx=0;

1f

while(x=getchar()rx!=\n&&x!=EOF)

(

putchar(x);

)

)

版本二：使用fgets

voidgood_echo()

(

constintBufferSize=10;

chars[BufferSize];

inti;

while(fgets(szBufferSize,stdin)!=NULL)

(

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

putchar(s[i]);

if(i<BufferSize-1)break;

return;

)

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

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

一輪的輸入。

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

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

3.69

longtrace(tree_ptrtp)

(

longret=0;

while(tp!=NULL)

(

ret=tp->val;