Skip navigation

Tag Archives: Computer Systems Book

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.33 (skipped publishing 2.31 & 2.32 as they were thought exercises):

We can represent a bit pattern of length w = 4 with a single hex digit. For a two's-
complement interpretation of these digits, fill in the following table to determine
the additive inverses of the digits shown

     x               -t 4 x
-------------------------------
Hex   Decimal   Decimal   Hex
-------------------------------
 0      0          0       0
-------------------------------
 5      5         -5       B
-------------------------------
 8     -8         -8       8
-------------------------------
 D     -3          3       3
-------------------------------
 F     -1          1       1
-------------------------------

Work:

 8 = 1000 = -8
 D = 1101 = -8 + 4 + 1 = -3

 -5
 -8 + 2 + 1 = 1011 = B




Advertisements

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.30 (my answer differs in form, but I believe is still correct, from the answer in the answer section:

Write a function with the following prototype:

/* Determine whether arguments can be added without overflow */
int tadd_ok(int x, int y);

This function should return 1 if arguments x and y can be added without causing
overflow

Answer:

int tadd_ok(int x, int y) {

  int sum;

  sum = x + y;
  if (sum >= 0 && x < 0 && y < 0) {
    return 0;
  }
  if (sum  0 && y > 0) {
    return 0;
  }
  return 1;

}

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.29:

Fill in the following table in the style of Figure 2.24. Give the integer value of
the 5-bit arguments, the values of both their integer and two's-complement sums,
the bit-level representation of the two's-complment sum, and the case from the
derivation of Equation 2.14.

   x         y        x + y    x+t5y        Case
-----------------------------------------------------
[10100]   [10001]      -27      5             1
-----------------------------------------------------
[11000]   [11000]      -16     -16            2
-----------------------------------------------------
[10111]   [01000]       -1     -1             2
-----------------------------------------------------
[00010]   [00101]        7      7             3
-----------------------------------------------------
[01100]   [00100]       16     -16            4
-----------------------------------------------------

Work:

[10100]   [10001]

 -2^4 + 2^2
 -16 + 4
 -12

 10001
 -16 + 1
 -15

 -12 + -15 = -27

Possible negative max: -16
possible positive max: 15

2^w = 2^5 = 32

-27 + 32 = 5

[11000]   [11000]

-2^4 + 2^3 =
-16 + 8 = -8

-8 + -8 = -16
within range



[10111]   [01000]

-2^4 + 2^2 + 2^1 + 2^0 =
-16 + 4 + 2 + 1
-9

8
-1

[00010]   [00101]

2 + 5 = 7

[01100]   [00100]

12 + 4 = 16

Possible positive max: 15

16 in binary:
-0 + 16
[010000]
take of extra bit:
[10000]
-2^4
-16

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.28:

We can represent a bit pattern of length w = 4 with a single hex digit. For an
unsigned interpretation of these digits, use Equation 2.12 to fill in the following
table giving the values and the bit representations (in hex) of the unsigned additive
inverses of the digits shown.

      x                   -u/4(x)
-------------------------------------
  Hex   Decimal       Decimal   Hex
-------------------------------------
   0
-------------------------------------
   5
-------------------------------------
   8
-------------------------------------
   D
-------------------------------------
   F
-------------------------------------


Work:

hex: 5
decimal: 5

2^w = 16
-u/4(x) = (2^w - x)
16 - 5 = 11

hex: 8
decimal: 8
16-8 = 8


Answers:

      x                   -u/4(x)
-------------------------------------
  Hex   Decimal       Decimal   Hex
-------------------------------------
   0       0             0       0
-------------------------------------
   5       5            11       B
-------------------------------------
   8       8             8       8
-------------------------------------
   D      13             3       3
-------------------------------------
   F      15             1       1
-------------------------------------



This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.27 (skipped 2.25 & 2.26 since they were qualitative and the answer is the back of the chapter):

Write a function with the following prototype:

/* Determine whether arguments can be added without overflow */
int uadd_ok(unsigned x, unsigned y);

This function should return 1 if arguments x and y can be added without causing
overflow.

Answer:

int uadd_ok (unsigned x, unsigned y) {

  return (x + y) >= x;

}

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.24:

Suppose we truncate a 4-bit value (represented by hex digits 0 through F) to a 3-bit
value (represented as hex digits 0 through 7). Fill in the table below showing
the efffect of this truncation for some cases, in terms of the unsigned and two's
complement interpretations of those bit patterns.

        Hex                   Unsigned           Two's complment
---------------------- ----------------------- -------------------
Original    Truncated   Original    Truncated   Original Truncated
------------------------------------------------------------------
   0            0          0            0          0         0
------------------------------------------------------------------
   2            2          2            2          2         2
------------------------------------------------------------------
   9            1          9            1         -7         1
------------------------------------------------------------------
   B            3         11            3         -5         3
------------------------------------------------------------------
   F            7         15            7         -1        -1
------------------------------------------------------------------

WorK:


2U
0010
 010 = 2

2
0010
 010 = 2

9U
1001
 001 = 1
9 mod 8 = 1

-7 = -8 + 1
1001
 001 = 1
-7 mod 8 = 1
U2T(1) = 1

11U
1011
 011 = 3
11 mod 8 = 3

-5 = -8 + 4 + 1
1011
 011 = 3
-5 mod 8 = 3
U2T(3) = 3

15U
1111
 111 = 4 + 2 + 1 = 7
15 mod 8 = 7

-1 = -8 + 4 + 2 + 1
1111
 111 = -4 + 2 + 1 = -1
-1 mod 8 = 7
U2T(7) = -1

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.23:

Consider the following C functions:

int fun1(unsigned word) {
  return (int) ((word << 24);
}

int fun2(unsigned word) {
  return ((int) word << 24;
}

Assume these are executed on a machine with a 32-bit word size that uses two's
complement aritmetic. Assume also that right shifts of signed values are
performed arithmetically, while right shifts of unsigned values are performed
logically.

A. Fill in the following table showing the effect of these functions for several
example arguments. You will find it more convienient to work with a
hexidecimal representation. Just remember that hex digits 8 through F have their
most significant bits equal to 1.

     w             fun1(w)       fun2(w)
-----------------------------------------------
0x00000076
-----------------------------------------------
0x87654321
-----------------------------------------------
0x000000C9
-----------------------------------------------
0xEDCBA987
-----------------------------------------------

B. Describe in words the useful computation each of these functions performs.

Answers

A.

word = 0x00000076

fun2(w)

(int) ((word << 24)

word << 24)

Still unsigned so performing logical right shift (adding 0's).

return value is 0x00000076

fun1(w)

((int) word << 24;

((int) word << 24)

current value is now a signed 0x76000000

Most signficant bit for this value is a 0.

Return value after right shift:

0x00000076

word = 0x87654321

fun1()

value is 0x21000000 after first operation
value is unsigned
returned value is 0x00000021

fun2()
value is 0x21000000 after first operation
value is signed
first signficant bit of 2 is 0
returned value is 0x00000021

word = 0x000000C9

fun1()
value is 0xC9000000 after first operation
value is unsigned
return value is 0x000000C9

fun2()
value is 0xC9000000 after first operation
value is signed
first signficant bit of C is 1
return value is 0xFFFFFFC9

word = 0xEDCBA987

fun1()
value is 0x87000000 after first operation
returned value is 0x00000087

fun2()
value is 0x87000000 after first operation
returned value is 0xFFFFFF87

     w             fun1(w)       fun2(w)
-----------------------------------------------
0x00000076       0x00000076     0x00000076
       118              118            118
-----------------------------------------------
0x87654321       0x00000021     0x00000021
2271560481               33             33
-----------------------------------------------
0x000000C9       0x000000C9     0xFFFFFFC9
       201              201            -55
-----------------------------------------------
0xEDCBA987       0x00000087     0xFFFFFF87
3989547399             135            -121
-----------------------------------------------

B)
fun1 reduces a number to its lower 8 bits and produces a value of 0-255
fun2 reduces a number the same but produces a value of -128-127

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.22:

Show that each of the following bit vectors is a two's complement representation
of -5 by applying Equation 2.3

A. [1011]
B. [11011]
C. [111011]

Observe that the second and third bit vectors can be derived from the first by sign
extension.

Answers:

A.
 1011
 -(1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0)
 -8 + 0 + 2 + 1
 -8 + 3
 -5

B.
 11011
 -(1 * 2^4) + (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0)
 -16 + 8 + 0 + 2 + 1
 -8 + 3
 -5

c.
 111011
 -(1 * 2^5) + (1 * 2^4) + (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0)
 -32 + 16 + 8 + 0 + 2 + 1
 -16 + 8 + 3
 -8 + 3
 -5



After upgrading my Computer Systems book I have decided to go through the first two chapters, up until the part I stopped in Chapter 2 and compare differences. The problems are all the same types of problems, but the second edition has new exercises of the same type (at least so far). Because I want to get through the book and finish it and not get stuck redoing exercises I’ve done already I am going to continue on and if I have the energy go back and update old problems to use the new version (to fix the issue in the project source hosting where there will be problems from two different books!).

One difference I have recognized already is that the first book referred to “buffer overflow bugs” and this new version calls them “buffer overflow vulnerabilities ” and has added some extra information about these vulnerabilities.

I had been solving problems for Computer Systems: A Programmer’s Perspective, but I was using the first edition. I am now upgrading to the second edition.

I have not solved any problems recently due to work commitments but will start again right now, using the second edition, a more modern book. So far I don’t see any differences between the problems I have solved for the first edition and the second, but if there are any I will solve the new problems as well.

As always, the solutions are in a repository on Google Projects.