ITC222 Solutions to Exercises 5

The solutions are to the exercises specified in the section Arithmetic/logical operations of the Study Notes. The exercises are from Chapter 5 of the textbook, A Programmer's View of Computer Architecture by Goodman & Miller and some solutions are derived from those given in The Instructor's Manual by Miller.

Some of the exercises include material of general interest that goes beyond the requirements of this subject. These are indicated by an asterisk.

Exercise 5.1

The rotate instructions are invariant to rotation amounts differing by a multiple of 32. Thus rol x, y, 5 is equivalent to ror x, y, 27

Exercise 5.2

The carry out from the most significant bit is shown in brackets.
  1. (1)000001 for 54 + 11 = 65, overflow in 6 bits;
  2. (0)101000 for 13 + 27 = 40, no overflow in 6 bits;
  3. (0)100000 for 1 + 127 = 128, no overflow in 8 bits;

Exercise 5.3

  1. 1111101 for (-14) + 11 = (-3), no overflow in 6 bits;
  2. 101010 for 13 + 27 = 40, overflow in 6 bits (incorrect sign);
  3. 00000000 for 1 + (-1) = 0, no overflow in 8 bits;
Return to top of page

Exercise 5.4

  1. 0x47f0d for 241672 + 52997 = 294669, no overflow in 20 bits;
  2. 0xf4f533 for (-7028207) + 6304546 = (-723661), no overflow in 24 bits;
  3. 0xfd058 for 52446 + (-64646) = (-12200), no overflow in 20 bits;

Exercise 5.5*

1's complement numbers in n bits are represented as their actual values modulo 2n-1. A normal n-bit adder represents the result correctly modulo 2n. If there is carry out from the most significant bit of the adder then the number has been represented modulo one-more-than-it-should-have-been, which will reduce the resulting number by one. This can be solved by adding the carry bit back into the least significant bit of the result.
Return to top of page

Exercise 5.6

  1. We can do this one as if numbers are unsigned. 
             100001
       x    100
         ------
              0
             0
       100001
       --------
       10000100
    which equals 132. Check: 33*4 = 132.
  2. Numbers of the size specified need 5 bits to represent them in a two's complement representation. We need to sign extend to 10 bits, retaining 10 bits in the product. 
        11 1111 1111
  x         1100
    ------------
               0
              0
    11 1111 11
    11 1111 1 
    ------------
    11 1111 0100
    which equals -12. Check: (-1)*12 = -12.
  3. Numbers of the size specified need 6 bits to represent them in a two's complement representation. We need to sign extend to 12 bits, retaining 12 bits in the product. 
        0000 0001 0110
  x 1111 1111 1011
    --------------
            1 0110
           10 110
               0
         1011 0
       1 0110
      10 110
     101 10
    1011 0
    0110
    110
    10
    0
    --------------
    1111 1001 0010
    which equals -110. Check: 22*(-5) = -110.
  4. Numbers of the size specified need 6 bits to represent them in a two's complement representation. We need to sign extend to 12 bits, retaining 12 bits in the product. 
        1111 1110 1110
  x 1111 1111 0000
    --------------
Return to top of page

Exercise 5.7

val1 val2 NOT val1 val1 AND val2 val1 OR val2
0000 0000 1111 1111 1111 1111 0000 0000 1111 1111
0000 0000 0000 0000 1111 1111 0000 0000 1111 1111
1111 0000 0101 0101 0000 1111 0101 0000 1111 0101

Exercise 5.8

  1. 1010 1101 for 115 + 58 = 173, overflow in 8 bits;
  2. 0011 1000 for (-36) + 92 = 56, no overflow in 8 bits;
  3. 1101 1110 for (-47) + 13 = (-34), no overflow in 8 bits;

Exercise 5.9

  1. 0100 0001 for (-73) - 118 = (-191), overflow in 8 bits;
  2. 1100 0111 for 30 - 87 = (-57), no overflow in 8 bits;
  3. 111 1101 for 81 - 20 = 61, no overflow in 8 bits;
Return to top of page

Exercise 5.10

All are 6-bit numbers. If sign extended to 12 bits before the multiplication there can be no overflow. 
  1.                111
  x            110
    --------------
                 0
              111
            1 11
    --------------
          010 1010
    which equals 42. Check: 7*6 = 42. 
  2.     0000 0001 1110
  x 1111 1111 0111
    --------------
            1 1110
           11 110
          111 10
              0
       1 1110
      11 110
     111 10
    1111 0
    1110
    110
    10
    --------------
    1110 1111 0010
    which equals -270. Check: 30*(-9) = (-270). 
  3.            01 1011
  x        01 0100
    --------------
          110 11
       1 1011
    --------------
    0010 0001 1100
    which equals 540. Check: 27*20 = 540. 
  4.     1111 1111 1111
  x 1111 1110 1111
    --------------
    1111 1111 1111
    1111 1111 111
    1111 1111 11
    1111 1111 1
            0
    1111 111
    1111 11
    1111 1
    1111
    111
    11
    1
    --------------
    0000 0001 0001
    which equals 17. Check: (-1)*(-17) = 17.
Return to top of page

Exercise 5.11

  1. 23/4: 
       5          101
  --        -----
4|23    100|10111
  20        100
  --        ---
   3          111
              100
              ---
               11
  2. 240/8: 
       30            11110
  ---         --------
8|240    1000|11110000
  24          1000
  --          ----
   00          1110
               1000
               ----
                1100
                1000
                ----
                 1000
                 1000
                 ----
                    00
Return to top of page

Exercise 5.12

The number of bits used is not specified. The sign-magnitude representations of 10 and -15 are 00...01010 and 10...01111. Adding these as 2's complement numbers gives 10...011001, which would be interpreted as the sign-magnitude number -25. This has assumed that the number of bits is at least 6. If however only 5 bits are available, then adding 01010 and 11111 gives 01001 which would be interpreted as the sign-magnitude number +9.

Exercise 5.13

If sll were not available, we could use rol and clear those bits that are rotated from the left end of the data item and reinserted on the right. Thus, the instruction 
        sll     x, y, 5
could be replaced by the instructions 
        rol     x, y, 5
        and     x, x, 0xffffffe0

Exercise 5.14

An assumption here is that data items are word-sized. If the use of sra is to be replaced by rol, the amount moved has to subtracted from 32 and the correct sign bits have to be inserted. Thus, the instruction 
        sra     x, y, 5
could be replaced by the instructions 
        rol     x, y, 27
        bltz    y, a10
        and     x, x, 0x07ffffff
        b       a20
a10:
        or      x, x, 0xf8000000
a20:

Exercise 5.16

A solution will be available in due course.
Return to top of page
Author: Ken Lodge
Last Update: 30 August, 1997

ITC222 Home Page