COS 111, Fall 1998: First In-Class Exam Solutions

COS 111, Fall 1998 - In-Class Exam Solutions

Problem 1

Part a Since the high-order (leftmost) bit is 0, the number is positive. 010110 = 2+4+16 = 22 decimal.
Part b

 15    = 01111
-12    = 10100     by 12= 01100,  complement 12 = 10011,  add 1 to get 
---      -----                    2's complement = 10100
  3     100011  but we throw away the carry from the high-order bit to get 
         00011 in 5-bit 2's complement, which is the desired answer of 3

Part c There is no overflow because when the high-order bits of the operands are different there can be no overflow, even if a carry is generated when adding the high-order bit column.

Problem 2

Part a We can do long division in binary to get the binary representation of 1/7:

                 .001001001...
               ---------------------
           111 |1.000000000          
                  111
                -----
                    1000
                     111
                    ----
                       1000
                        111
                       ----
                          ...

So we see that the precise binary representation of one seventh is an infinite repetition of "001". However, we can only represent 4 bits of this in Brookshear's representation. We use an exponent of -2(decimal), which is 010 in excess 4 notation, and a mantissa of 1001. The high-order bit is a 1 to indicate the number is negative:

10101001

Another way to derive the mantissa is to subtract powers of 1/2:
1/7 = 1/8 + 1/56 = 1/8 + 1/64 + 1/448 > .001001 (binary)
which gives us enough to proceed.
Part b Yes, there is roundoff error. The floating point number actually represents -(1/8 + 1/64) = -9/64. Referring to the addition above, we see the floating point value is 1/448 too large.

Problem 3

Part a We want an exclusive-or of "Japan" and "China", but we must express it using AND, OR, and NOT. There are many correct answers. One is
(Japan OR China) AND ( NOT (Japan AND China))
Part b ( !x AND !y AND z ) OR ( x AND y AND !z )

Problem 4

Part a 11110 is not a legal code word.
Part b 11010 and 10110 are legal code words that are Hamming distance 2 apart (they differ in bits 2 and 3 numbering left-to-right). No two legal code words can be closer because if you change only one bit of a code word, you cannot maintain the correct relationship between the original 3 bits and the two appended bits.
Part c The code gives one bit error detection. (Calling this code an "error correction code" is a bit of a misnomer -- it gives no bits of correction.)

Problem 5

There are several correct solutions. I will present the shortest one I know. Any program that works will be given full credit. I will present both parts a and b together, with part b on the left and part a on the right:

Part b                           Part a                          
memory       
address   instruction            action in English
-------   -----------            -----------------
00        10F0                   load reg. 0 with contents of mem. loc. F0
02        11F1                   load reg. 1 with contents of mem. loc. F1
04        B108                   if contents reg. 0 = contents reg. 1, 
                                    go to instruction at memory address 08
06        2100                   load reg. 1 with value 00
08        31FF                   store the contents of reg 1 in mem. loc. FF
                                 (note that the contents depends on whether
                                  the instruction at 06 is jumped over )
0A        C000                   halt