第1页 / 共89页
第2页 / 共89页
第3页 / 共89页
第4页 / 共89页
第5页 / 共89页
第6页 / 共89页
第7页 / 共89页
第8页 / 共89页
《深入理解计算机系统》（修订版）习题答案，CSAPP习题答案，Computer.Systems.A.Programmer's.P....pdf
Computer Systems: A Programmer’s Perspective
Instructor’s Solution Manual 1
Randal E. Bryant
David R. O’Hallaron
December 4, 2003
1Copyright c
2003, R. E. Bryant, D. R. O’Hallaron. All rights reserved.
2
Chapter 1
Solutions to Homework Problems
The text uses two different kinds of exercises:
Practice Problems. These are problems that are incorporated directly into the text, with explanatory
solutions at the end of each chapter. Our intention is that students will work on these problems as they
read the book. Each one highlights some particular concept.
Homework Problems. These are found at the end of each chapter. They vary in complexity from
simple drills to multi-week labs and are designed for instructors to give as assignments or to use as
recitation examples.
This document gives the solutions to the homework problems.
1.1 Chapter 1: A Tour of Computer Systems
1.2 Chapter 2: Representing and Manipulating Information
Problem 2.40 Solution:
This exercise should be a straightforward variation on the existing code.
code/data/show-ans.c
show_bytes((byte_pointer) &x, sizeof(short int));
1 void show_short(short int x)
2 {
3
4 }
5
6 void show_long(long int x)
7 {
8
9 }
show_bytes((byte_pointer) &x, sizeof(long));
1
2
CHAPTER1. SOLUTIONSTOHOMEWORKPROBLEMS
10
11 void show_double(double x)
12 {
13
14 }
show_bytes((byte_pointer) &x, sizeof(double));
code/data/show-ans.c
Problem 2.41 Solution:
There are many ways to solve this problem. The basic idea is to create some multibyte datum with different
values for the most and least-significant bytes. We then read byte 0 and determine which byte it is.
In the following solution is to create an int with value 1. We then access its first byte and convert it to an
int. This byte will equal 0 on a big-endian machine and 1 on a little-endian machine.
code/data/show-ans.c
/* MSB = 0, LSB = 1 */
int x = 1;
1 int is_little_endian(void)
2 {
3
4
5
6
7
8 }
/* Return MSB when big-endian, LSB when little-endian */
return (int) (* (char *) &x);
code/data/show-ans.c
Problem 2.42 Solution:
This is a simple exercise in masking and bit manipulation. It is important to mention that ˜0xFF is a way
to generate a mask that selects all but the least significant byte that works for any word size.
(x & 0xFF) | (y & ˜0xFF)
Problem 2.43 Solution:
These exercises require thinking about the logical operation ! in a nontraditional way. Normally we think
of it as logical negation. More generally, it detects whether there is any nonzero bit in a word.
A. !!x
B. !!˜x
C. !!(x & 0xFF)
D. !!(˜x & 0xFF)
Problem 2.44 Solution:
1.2. CHAPTER2: REPRESENTINGANDMANIPULATINGINFORMATION
3
There are many solutions to this problem, but it is a little bit tricky to write one that works for any word
size. Here is our solution:
code/data/shift-ans.c
int x = ˜0; /* All 1’s */
1 int int_shifts_are_arithmetic()
2 {
3
4
5
6 }
return (x >> 1) == x;
The above code peforms a right shift of a word in which all bits are set to 1. If the shift is arithmetic, the
resulting word will still have all bits set to 1.
Problem 2.45 Solution:
This problem illustrates some of the challenges of writing portable code. The fact that 1<<32 yields 0 on
some 32-bit machines and 1 on others is common source of bugs.
code/data/shift-ans.c
A. The C standard does not define the effect of a shift by 32 of a 32-bit datum. On the SPARC (and
many other machines), the expression x << k shifts by , i.e., it ignores all but the least
significant 5 bits of the shift amount. Thus, the expression 1 << 32 yields 1.
B. Compute beyond_msb as 2 << 31.
C. We cannot shift by more than 15 bits at a time, but we can compose multiple shifts to get the
desired effect. Thus, we can compute set_msb as 2 << 15 << 15, and beyond_msb as
set_msb << 1.
Problem 2.46 Solution:
This problem highlights the difference between zero extension and sign extension. It also provides an excuse
to show an interesting trick that compilers often use to use shifting to perform masking and sign extension.
A. The function does not perform any sign extension. For example, if we attempt to extract byte 0 from
word 0xFF, we will get 255, rather than
.
B. The following code uses a well-known trick for using shifts to isolate a particular range of bits and to
perform sign extension at the same time. First, we perform a left shift so that the most significant bit
of the desired byte is at bit position 31. Then we right shift by 24, moving the byte into the proper
position and peforming sign extension at the same time.
1 int xbyte(packed_t word, int bytenum)
2 {
code/data/xbyte.c
4
CHAPTER1. SOLUTIONSTOHOMEWORKPROBLEMS
int left = word << ((3-bytenum) << 3);
return left >> 24;
3
4
5 }
code/data/xbyte.c
Problem 2.47 Solution:
˜
˜
Problem 2.48 Solution:
This problem lets students rework the proof that complement plus increment performs negation.
We make use of the property that two’s complement addition is associative, commutative, and has additive
inverses. Using C notation, if we define y to be x-1, then we have ˜y+1 equal to -y, and hence ˜y equals
-y+1. Substituting gives the expression -(x-1)+1, which equals -x.
Problem 2.49 Solution:
This problem requires a fairly deep understanding of two’s complement arithmetic. Some machines only
provide one form of multiplication, and hence the trick shown in the code here is actually required to perform
that actual form.
As seen in Equation 2.16 we have
!" $#! &%('*)+ ,#- %.'*)+
has no effect on the 32
must be added to the high order 2 bits. This is implemented as follows:
. The final term
, but the middle term represents a correction factor that
-bit representation of
#-&%('*)/ %.'*)
10
3
code/data/uhp-ans.c
unsigned p = (unsigned) signed_high_prod((int) x, (int) y);
1 unsigned unsigned_high_prod(unsigned x, unsigned y)
2 {
3
4
5
6
7
8
9
10 }
if ((int) x < 0) /* x_{w-1} = 1 */
if ((int) y < 0) /* y_{w-1} = 1 */
return p;
p += y;
p += x;
Problem 2.50 Solution:
Patterns of the kind shown here frequently appear in compiled code.
code/data/uhp-ans.c
%
%
1.2. CHAPTER2: REPRESENTINGANDMANIPULATINGINFORMATION
5
A.
B.
C.
D.
: x + (x << 2)
: x + (x << 3)
: (x << 4) - (x<<1)
: (x << 3) - (x << 6)
Problem 2.51 Solution:
Bit patterns similar to these arise in many applications. Many programmers provide them directly in hex-
adecimal, but it would be better if they could express them in more abstract ways.
A.
%('
.
˜((1 << k) - 1)
B.
%(' '
.
((1 << k) - 1) << j
Problem 2.52 Solution:
Byte extraction and insertion code is useful in many contexts. Being able to write this sort of code is an
important skill to foster.
code/data/rbyte-ans.c
int itimes8 = i << 3;
unsigned mask = 0xFF << itimes8;
1 unsigned replace_byte (unsigned x, int i, unsigned char b)
2 {
3
4
5
6
7 }
return (x & ˜mask) | (b << itimes8);
Problem 2.53 Solution:
These problems are fairly tricky. They require generating masks based on the shift amounts. Shift value k
equal to 0 must be handled as a special case, since otherwise we would be generating the mask by performing
a left shift by 32.
code/data/rshift-ans.c
code/data/rbyte-ans.c
6
CHAPTER1. SOLUTIONSTOHOMEWORKPROBLEMS
/* Perform shift arithmetically */
unsigned xsra = (int) x >> k;
/* Make mask of low order 32-k bits */
unsigned mask = k ? ((1 << (32-k)) - 1) : ˜0;
1 unsigned srl(unsigned x, int k)
2 {
3
4
5
6
7
8
9 }
return xsra & mask;
1 int sra(int x, int k)
2 {
3
4
5
6
7
8
9 }
/* Perform shift logically */
int xsrl = (unsigned) x >> k;
/* Make mask of high order k bits */
unsigned mask = k ? ˜((1 << (32-k)) - 1) : 0;
return (x < 0) ? mask | xsrl : xsrl;
code/data/rshift-ans.c
code/data/rshift-ans.c
code/data/rshift-ans.c
Problem 2.54 Solution:
These “C puzzle” problems are a great way to motivate students to think about the properties of computer
arithmetic from a programmer’s perspective. Our standard lecture on computer arithmetic starts by showing
a set of C puzzles. We then go over the answers at the end.
.
A. (x-y). No, Let x =
B. ((x+y)<<4) + y-x == 17*y+15*x. Yes, from the ring properties of two’s complement arith-
0
metic.
.
C. ˜x+˜y == ˜(x+y). No, ˜ # ˜
D. (int) (ux-uy) == -(y-x). Yes. Due to the isomorphism between two’s complement and
˜ #
#
*#
unsigned arithmetic.
E. ((x >> 1) << 1) <= x. Yes. Right shift rounds toward minus infinity.
Problem 2.55 Solution:
This problem helps students think about fractional binary representations.
A. Letting
right gives a string
these gives
'*) .
0
denote the value of the string, we can see that shifting the binary point positions to the
. Equating
, and also value
, which has numeric value
#
#
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
