CS 61C Fall 1994 Midterm 1 solutions
1. Binary to hex.
Divide the binary number into groups of four bits:
1010 1011 1011 1010
Then convert each group to a hex digit:
A B B A
So the answer is 0xABBA. There's no need to convert to
decimal as an intermediate step; if you did that, you're
not understanding the whole point of hex! We use it as
a quick, easy abbreviation for binary.
We also accepted -0x5446, although hex numerals are almost
always taken as unsigned.
Scoring: one point, right or wrong.
2. What's the address?
start address size in bytes
.data
a: .word 0 0xff00 4
b: .word 1:2 0xff04 8
c: .byte 3:4 0xff0c 4
(Each number in the "start address" column is computed by adding
the previous size to the previous start address.)
So, the last element of c is c[3], which is at address 0xff0f,
which is 0xff0c + 3.
A few people thought that the addresses would count downward
because these variables are on the stack. Nope. The stack
is for local variables of procedures. Things that you declare
in the data area are *global* variables; they live in between
the program code and the heap.
Scoring: 2 points if correct. We gave 1 point for 0xff10 (the
address *after* the last element of c) and for 0xff15 (what you
get by adding 15 decimal to 0xff00 and not noticing that you
can't do that). Otherwise zero.
3. Find the errors.
There were five errors:
1. Register $0 is always zero and can't be used as a destination.
2. The LW instruction should be SW (store word).
3. The memory argument must come after the register argument
in LW and SW instructions.
4. The offset 2 should be 8 because we're using an array of words,
not bytes.
5. The base register should be $10, not $8.
The correct program is
__start:li $8, 1
li $9, 1
ADD $11, $8, $9
la $10, array
SW $11, 8($10)
done
Only the two instructions shown in capital letters need be changed.
Note: You can't use the MOVE instruction with a memory operand.
MOVE only works with two register operands.
Scoring: One point for each error corrected, to a maximum of four
(so you could miss one of them), minus one point for each non-error
that you thought you had to correct.
A few people completely rewrote the program instead of correcting
this one; they got 2 points if their program worked.
4. Why is twos complement better?
Reason 1: The same algorithm (and therefore the same hardware) that
adds unsigned integers works for signed integers in twos complement.
The other two representations must treat signed arithmetic specially.
Reason 2: In twos complement there is only one representation for
zero. This is good because testing for equality doesn't have to
recognize two different bit patterns with equal values.
There were several answers to which we gave partial credit. Most of
them seemed to us to have been copied from the book without full
understanding. For example:
"The same hardware works for adding positive and negative numbers."
This property distinguishes twos and ones complement from sign-
magnitude, but doesn't distinguish twos from ones complement.
What distinguishes those formats is that for signed arithmetic,
ones complement format requires extra hardware -- wrapping the
carry out from the leftmost bit into the rightmost bit -- that
isn't used for unsigned arithmetic.
"Addition of negative numbers works." Pfui. All of these
representations can be made to work; I grew up with sign-magnitude
computers, and they added and subtracted signed integers just fine.
What you meant was that *the same algorithm that adds unsigned
integers* also works for signed arithmetic.
"Arithmetic is easier." Well, yes, but why? This answer didn't
convince us that you really understand anything about what makes
one representation better than another.
Less impressive than any of those was "A larger range of values can be
represented, down to -2^(N-1) instead of -(2^(N-1) - 1)." This is
essentially the same answer as "there's only one zero" and it focuses on the
least important aspect of that reason. Out of four billion representable
numbers, one additional number is an improvement of 0.0000000025%, not
very interesting.
The absolutely worst answer we saw was "A larger range of values can
be represented, from -2^N to 2^N instead of from -2^(N-1) to 2^(N-1)"!
That would be a good trick, if using a different representation could
change the fundamental law that N bits can represent 2^N values.
Scoring: Two points per reason, with partial credit as above.
5. Translate C to MAL.
Here is the most straightforward solution. It uses registers $16,
$17, and $18 to hold x, y, and z, respectively.
foo: add $sp, $sp, -24 # prologue
sw $31, 0($sp)
sw $16, 4($sp)
sw $17, 8($sp)
sw $18, 12($sp)
sw $4, 16($sp) # preserve original arguments
sw $5, 20($sp)
sll $4, $4, 6 # a << 6
jal fun
move $17, $2 # y = fun(a << 6)
lw $4, 20($sp) # b
jal fun
move $18, $2 # z = fun(b)
lw $8, 16($sp) # a
lw $9, 20($sp) # b
add $8, $8, $18 # a + z
add $9, $9, $19 # b + y
mul $16, $8, $9 # x = (a + z) * (b + y)
move $2, $16 # return x
lw $31, 0($sp) # epilogue
lw $16, 4($sp)
lw $17, 8($sp)
lw $18, 12($sp)
add $sp, $sp, 24
jr $31
By using saved registers more frugally, it is possible to write
correct solutions using as few as 16 bytes of stack space. But
a lot of people who tried that didn't succeed.
Several people during the exam wanted to know more about the procedure
fun. But, you see, the whole point is that the C compiler doesn't
know what fun does either! The reason for register and stack
conventions is precisely so that you can compile one procedure without
having to see the procedures it calls or the procedures that call it.
Scoring:
6 correct
3-5 has the idea
1-2 has an idea
0 other
Some typical mistakes and their scores:
5 Program works but violates register/stack conventions
4 Assumes that fun will not change $5
3 Doesn't save the saved registers
2 Doesn't even save $31
1 Doesn't call fun twice
0 Calls putc or some such I/O thing instead of returning a value
6. Recursive function in MAL.
One saved register will be needed to preserve the value returned by
the first recursive call during the second one.
pascal: add $sp, $sp, -16 # prologue
sw $31, 0($sp)
sw $4, 4($sp)
sw $5, 8($sp)
sw $16, 12($sp)
li $2, 1 # return 1 if base case
beqz $5, ret
beq $4, $5, ret
addi $4, $4, -1
addi $5, $5, -1
jal pascal
move $16, $2 # save pascal(n-1, r-1)
lw $4, 4($sp) # get original args back
lw $5, 8($sp)
addi $4, $4, -1
jal pascal # pascal(n-1, r)
add $2, $2, $16 # return pascal(n-1, r-1) + pascal(n-1, r)
ret: lw $31, 0($sp) # epilogue
lw $16, 12($sp)
add $sp, $sp, 16
jr $31
Again, it's possible to save a little stack space by being very clever.
You can write pascal in a way that preserves the values in $4 and $5,
and rely on that to avoid having to save them on the stack. But a
compiler would have to be very clever indeed to work that out, and
most people who tried it messed up.
Scoring:
7 correct
4-6 has the idea
1-3 has an idea
0 other
Some typical mistakes and their scores:
6 Program works but violates register/stack conventions
5 Assumes that recursive call will not change $4, $5, or $8
4 Doesn't save the saved register
3 Doesn't even save $31
2 Tries to use looping instead of recursion
1 No procedure calls at all
0 Calls putc or some such I/O thing instead of returning a value