CS61C, Spring 2008
[TA] Ben Sussman - And other, more ancient ones
Due Wednesday, Feb 20, 2007 @ 11:59:59pm
Copy the contents of ~cs61c/hw/03 to a suitable location in your home directory.
$ cp -r ~cs61c/hw/03/ ~/hw3 |
Rewrite the bitcount function on page 50 of K&R such that it doesn't use any conditional statements (meaning no if, switch, ?: expression statements).
/* bitcount: count 1 bits in x */ int bitcount(unsigned x) { int b; for (b = 0; x != 0; x >>= 1) { if (x & 01) { b++; } } return b; } |
Complete Exercise 6-5 on page 145 of K&R. All the code from section 6.6 is provided in hash.c already, with some quick test code around it. Just fill in the blank for the undef function definition -- remember to free the appropriate malloc'd space used and to correctly deal with deleting a node from a linked list (i.e. the next pointers). The return values are there for you to use (return values of 0 and 1 are straightforward and -1 if you feel like you need it).
The relevant reading is available here if you don't have the book: Chapter 6.6
Some test input you may try with hash.c:
Compile the program and run using the following command:
$ gcc -g hash.c && ./a.out |
P&H 2.29 (2.3, 2.6, 2.9) and write the C equivalent:
Add comments to the code and describe in one sentence what this code does. Assume that$a0and
$a1are used for input and both initially contain the integers a and b, respectively. Assume that
$v0is used for the output.
Also, convert this MIPS code to C (you may find it easier to understand if you do this first!).
add | $t0, $zero, $zero | |
loop: | beq | $a1, $zero, finish |
add | $t0, $t0, $a0 | |
sub | $a1, $a1, 1 | |
j | loop | |
finish: | addi | $t0, $t0, 100 |
add | $v0, $t0, $zero |
P&H 2.30 (2.3, 2.6, 2.9) and write the C equivalent:
The following code fragment processes two arrays and produces an important value in register$v0. Assume that each array consists of 2500 words indexed 0 through 2499, that the base addresses of the arrays are stored in
$a0and
$a1respectively, and their sizes (2500) are stored in
$a2and
$a3, respectively. Add comments to the code and describe in one sentence what this code does. Specifically, what will be returned in
$v0?
Also, convert this MIPS code to C (you may find it easier to understand if you do this first!).
sll | $a2, $a2, 2 | |
sll | $a3, $a3, 2 | |
add | $v0, $zero, $zero | |
add | $t0, $zero, $zero | |
outer: | add | $t4, $a0, $t0 |
lw | $t4, 0($t4) | |
add | $t1, $zero, $zero | |
inner: | add | $t3, $a1, $t1 |
lw | $t3, 0($t3) | |
bne | $t3, $t4, skip | |
addi | $v0, $v0, 1 | |
skip: | addi | $t1, $t1, 4 |
bne | $t1, $a3, inner | |
addi | $t0, $t0, 4 | |
bne | $t0, $a2, outer |
Show the single MIPS instruction or minimal sequence of instructions for the following C statements:
b = 25 | a;
x[4] = x[5] + a;
acorresponds to register
$t0and
bcorresponds to register
$t1.
acorresponds to register
$t3and the array
xhas a base address of 6,400,000ten.
$a0is an integer argument while
$a1is a pointer to (ie: the address of) a large array. The value in
$a0can be any integer and the size of the array that
$a1points to is big enough (as long as you don't dereference memory before $a1, you won't be accessing memory that isn't yours) for the code to work correctly.
addi | $t1 $zero 31 | |
addi | $t0 $zero 31 | |
loop: | srlv | $t3 $a0 $t1 |
andi | $t3 $t3 1 | |
addi | $t3 $t3 48 | |
sub | $t4 $t0 $t1 | |
add | $t2 $a1 $t4 | |
sb | $t3 0($t2) | |
beq | $t1 $zero done | |
subi | $t1 $t1 1 | |
j | loop | |
done | sb | $zero 1($t2) |
jr | $ra |