《CS：APP》第二版第三章家庭作业部分答案
<深入理解计算机系统> <CS: APP>
以下答案均有个人完成转载注明出处
3.55
movl12(%ebp), %esiget x_l
movl20(%ebp), %eaxget y
movl%eax, %edx
sarl$31, %edxget sign
movl%edx, %ecx
imull%esi, %ecxcompute x_i_sign = sign * x_l
movl16(%ebp), %ebxget x_h
imull%eax, %ebxcompute dest_h = x_h * y
addl%ebx, %ecxcompute dest_h = x_h * y + x_l * sign
mull%esicompute
x_l * y
leal(%ecx, %edx), %edxcompute x_h * y + sign * x_l + sign
movl8(%ebp), %ecxget dest
movl%eax, (%ecx)dest_l = x_l * y
movl%edx, 4(%ecx)dest_h = ( x_h * y + sign * x_l ) + sign
大致算法
取底32位加后缀l, 取高32位加后缀h, sign为符号位扩展32位的y
dest_l =( x_l * y ) 取低位
dest_h = ( sign * x_l + x_h * y )_l + (x_l *y )_h
3.56
int loop ( int x, int n)
{
int result = 1431655765;
intmask;
for(mask = 1 << 31 ; mask != 0 ; mask = (unsigned) mask >> n) {
result ^= (x & mask) ;
}
returnresult;
}
A %esi x
%edx mask
%ebx n
%edi %eax result
B result = 1431655765
mask = -2147483648
C mask!=0
E 同上
F 填了
3.58
typedef enum { MODE_A, MODE_B, MODE_C,MODE_D, MODE_E } mode_t;
int switch3( int *p1, int *p2, mode_taction)
{
intresult = 0;
switch ( action) {
case MODE_A; result = *p1; *p1 = *p2; break;
case MODE_B; result = *p2; *p2 = *p1; break;
caseMODE_C; *p2 = 15; result = *p1; break;
caseMODE_D; *p2 = *p1; result = 17; break;
caseMODE_E; result = 17; break;
default: result= -1; break;
}
return result;
}
3.59
int switch_prob(int x, int n)
{
intresult = x;
switch(n){
case40: case 42: result <<= 3; break;
case43: result >>= 3; break;
case44: result <<= 3; result -= x;
case45; result *= result;
default: result += 17;
}
returnresult;
}
3.60
int A [R] [S] [T]
A: 将等式从二维扩展到三维
A [ I ] [ j ] [ k ] = * ( A + 4 * ( i * S *T + j * T + k ) )
B:
R 11 S 7 T 9
3.62
A M: 76 / 4 = 19
B %edi i, %ecx j
C
void transpose ( int A [M][M] ) {
int I, j;
for( i = 0; I < M; i ++ )
int*a = &A[0] [i];
int*b = &A[i] [0];
for( j = 0; j < I ; j++ )
int t = *a;
*a= *b;
*b= t;
b++;
a+= M;
}
}
3.63
确定E1 和E2的定义
E1(n) = 3 * n
E2(n) = 2 * n – 1
3.64
A:
5行: result的address
6行: s1.v
7行: s1.p
B:
1: %ebp
2: s2.sum
3: s2.prod
4: s1.v
5: s1.p
6:返回地址
C向函数传递结构参数的通用策略: 将结构每一个元素当作本身的参数传入
D 从函数返回结构值的通用策略: 返回结构变量的初始地址作用, 因为没有寄存器可以存下一整个结构体, 且结构体的大小是可变的
3.66
A. 7
B typedef struct {
intidx;
intx [6];
} a_struct;
3.67
A
p: 0
x: 4
y: 0
next: 4
B: 这个结构一共需要8个字节
C:
void proc ( union ele *up )
{
up -> e2.next -> e1.x = * ( up-> e2.next -> e1.p ) – up -> e2. y ;
}
3.69
A
long trace ( tree_ptr tp ) {
long ret = 0;
while ( tp != NULL ) {
ret = tp.val;
tp = tp.left;
}
returnret;
}
B 输出二叉树最左边的结点值
3.70
long traverse ( tree_ptr tp ) {
longresult = 0;
if( !tp ) return result;
long VAL = tp->val;
longleft = traverse ( tp->left );
longresult = traverse ( tp->right );
if( left < result )
result= left;
if( v < result )
result= v;
returnresult;
}
B 计算二叉树所有结点中的最小值
