The exam will consist of short-answer questions and writing your own code. A significant portion will consist of writing code (more than half the points), so you should be prepared to do this.
The review below, in addition to Lab 1, Lab 2, and Lab 3, are all fair game for the exam. For the labs, this includes both code you've written and questions you've answered. Between this review and the first three labs, this information is intended to be comprehensive; there will be no material on the exam which isn't touched by either the labs or this review.
If you're pushed for time, my personal recommendation is to spend the majority of your time studying what you wrote for your labs, both code and questions. You'll find the review below to be largely (though not entirely) redundant with that information.
Convert the decimal number 39 into 8-bit binary.
00100111
Convert the decimal number 40 into a two-digit hexadecimal number.
0x28
Convert the hexadecimal number 0x45 into decimal.
69
Convert the hexadecimal number 0x1F into decimal.
31
Convert the unsigned binary number 1001 into decimal.
9
Convert the signed binary number 1001 into decimal.
-7
Convert -5 into binary, using two's complement.
1011
Negate the number 7 using two's complement, and show its 4-bit binary representation.
1001
Negate the binary number 0110 using two's complement, showing the result in binary.
1010
What's the quickest way to tell if a number in two's complement is negative?
It is negative if its left-most bit is a 1.
In 5 bits, what is the most negative value representable in signed form, using two's complement? Express your answer in both binary and decimal.
In 5 bits, what is the most positive value representable in signed form, using two's complement? Express your answer in both binary and decimal.
In 5 bits, what is the most negative value representable in unsigned form? Express your answer in both binary and decimal.
You cannot represent a negative value in unsigned form; unsigned form means that all the bits are used for representing positive values.
In 5 bits, what is the most positive value representable in unsigned form? Express your answer in both binary and decimal.
Suppose you are given the following 4-bit binary number, shown in two's complement:
0110You're not told whether or not the number is signed or unsigned. Is this information important in knowing what the value of the number is, in decimal? That is, do you need to know if it's signed or unsigned to say what the decimal value is? Why or why not?
First of all, we know that it's signed because it's in two's complement. However, even we hadn't been told that it's in two's complement and only been told it's a binary number, we wouldn't need to be told if it's signed or not because the left-most bit is a 0, meaning it will be positive a number regardless of whether the number was signed or unsigned. It is equal to 6 decimal in either case.
Suppose you are given the following 4-bit binary number, shown in two's complement:
1001You're not told whether or not the number is signed or unsigned. Is this information important in knowing what the value of the number is, in decimal? That is, do you need to know if it's signed or unsigned to say what the decimal value is? Why or why not?
Like the previous question, we know it's signed because it's in two's complement. If we hadn't been told it was two's complement, then because of the left-most bit being a 1, we would be unable to determine the value of the number unless more information was given. This is because the left-most bit would make it a negative number if the number was signed, and a different positive number if the number was unsigned.
Suppose that a binary addition was performed in a processor, and the processor set the carry bit at the end of the computation. What does this mean? That is, what is the significance of the carry bit being set after an addition is performed?
After addition, the carry bit being set means that the result of the addition did not fit into the number of bits alloted. For example, adding two unsigned 4-bit binary numbers 5 and 11:
0101
+ 1011
------
10000
Notice that the result is 5 bits wide, but we only have 4 bits to store the number in.
Therefore, the result of the additon is actually 0000with a carry set (the carry corresponding to the bit that would have been in position 4 if we had a 5 bits available).
Suppose that a binary addition was performed in a processor, and the processor set the overflow bit at the end of the computation. What does this mean? That is, what is the significance of the overflow bit being set after an addition is performed?
After addition, the overflow bit being set means that the result of adding two same-signed numbers resulted in a number of a different sign (just like in decimal, if you add two positive numbers, you must get a positive number, and if you add two negative numbers, you must get a negative number). For example, here we add two signed 4-bit binary numbers 5 and 7:
0101
+ 0111
------
1100
The resulting number, because we are dealing with signed numbers, is not 12 as it should be, but is instead -4 (because of two's complement).
Both numbers were positive, but we got a negative result, thus we have overflow.
Generally, the carry bit is ignored when performing signed arithmetic. Why?
The carry bit is used to signify that we do not have enough bits to represent the result of a computation using unsigned arithmetic, and doesn't correspond to anything interesting in a signed setting.
Generally, the overflow bit is ignored when performing unsigned arithmetic. Why?
The overflow bit is set when the two inputs have the same sign, but the output lacks this same sign. In an unsigned setting, because there are no such things as negative numbers, this distinction is meaningless.
In MIPS, what is the difference between the add and addu instructions?
add causes an exception (stops normal execution of the program and goes to the exception
handler or aborts) if the result of the addition causes an overflow.
addu does not cause an exception if the result of the addition causes an overflow.
Other than that, they are identical.
Consider the following C code:
signed int x = -1; // line 1 signed int y = 5; // line 2 signed int result = x + y; // line 3
In generating the assembly code for line 3, MIPS compilers will generally use the addu instruction, which is for unsigned addition.
This is not a bug in the compiler, and result will, in fact, end up holding the correct result.
There are two questions here:
Why does addu return the correct result, despite being intended for unsigned addition?
The addu instruction exists to allow programmers to add numbers and ignore any overflow that
occurs. It does not mean that the operands of the instructions are automatically made unsigned; they
will remain negative if they are already negative. Thus, the computation produces the correct result, even
when using addu. (For more details, see the "Elaboration" paragraph in your book on page 180.)
What feature of C allows compilers to use addu here instead of add?
C considers signed integer overflow to be undefined behavior, and programs which trigger undefined behavior semantically have no meaning.
This means that a compiler writer is free to assume that signed integer overflow will never occur, according to the standard.
As such, compilers will pick addu over add, as it is simpler.
Perform the following two's complement addition, noting whether or not the carry bit (C) and/or the overflow bit (V) get set:
01111111 +11111111 --------- 01111110 C
Perform the following two's complement addition, noting whether or not the carry bit (C) and/or the overflow bit (V) get set:
00100101 +10110111 --------- 11011100
Perform the following two's complement subtraction, noting whether or not the carry bit and/or the overflow bit get set:
01111111 -11111111 --------- 10000000 V
Perform the following two's complement subtraction, noting whether or not the carry bit and/or the overflow bit get set:
00100101 -10110111 --------- 01101110
Consider the following C code:
signed char x;
for (x = 1; x > 0; x++) {
printf("Hello\n");
}
printf("Goodbye\n");
Assume the compiler performs a naive translation to assembly, and doesn't exploit any special features of C. Some questions follow:
Does "Goodbye\n" ever get printed out?
Why or why not?
"Goodbye\n" will be printed out. Since a char is represented with one 8-bit byte,
the initial value of x will be 1, and then x is incremented continually. It will eventually reach the largest positive 8-bit
number, which, because this is signed two's complement, is (2^8)-1, 127 in decimal, or 01111111 in binary. Adding one
more to that results in 10000000 (binary), which is -128. Since -128 is less than 0, it finally exits the loop and prints
the final "Goodbye\n".
Why is it important that a C compiler not exploit any special features of C here? In particular, what feature of C might cause this program to do something differently?
C considers signed integer overflow to be undefined behavior, and programs which trigger undefined behavior semantically have no meaning.
This means that a compiler writer is free to assume that signed integer overflow will never occur, according to the standard.
As such, according to the standard, the compiler may transform this into an infinite loop, or do any one of another transformations which would effect whether or not "Goodbye\n" gets printed.
Consider the following C code:
unsigned char x;
for (x = 0; x <= MAX_UNSIGNED_CHAR; x++) {
printf("Hello\n");
}
printf("Goodbye\n");
Assume that MAX_UNSIGNED_CHAR holds the maximum value representable in an unsigned char, which is defined previously in the code.
Some questions about this code follow:
Does "Goodbye\n" ever get printed out?
The word "Goodbye\n" will never get printed out. A character is represented using 8 bits, and because x is unsigned,
it will be incremented until it reaches it's largest value, which is 1111111 in binary (255 in decimal), which is also equal to MAX_UNSIGNED_CHAR.
When you add one to the largest unsigned 8-bit value, it wraps around back to 0 and continues incrementing, forever. Thus, the comparison x <= MAX_UNSIGNED_CHAR
will stay true for any of the possible values x gets.
Unlike with the previous review question, it was not stipulated whether or not we assume the compiler exploits any special features of C. Is this information relevant to this question? Why or why not?
Interestingly enough, while signed integer overflow is undefined in C, this sort of wrapping done by unsigned values is defined. That is, this program does not trigger undefined behavior, so we can assume the compiler will translate this into something similar. It's just that in this case, it's unlikely that the behavior observed is what was intended.
In the following questions, & refers to bitwise AND, | refers to bitwise OR, ^ refers to bitwise XOR, << refers to shift left, and >> refers to shift right.
00011101 &11011010 --------- 00011000
00011101 |11011010 --------- 11011111
00011101 ^11011010 --------- 11000111
Consider the following C code, which is intended to extract the lowest 7 bits of the given input i, leaving the bits in their original position:
int unsignedBits0through6(int i) {
return __________;
}
Fill in __________ with a single bitwise expression which will make the code do what it is intended to do.
(i & 0x0000007F)
Consider the following C code, which is intended to extract the next 7 bits of the given input i, leaving the bits in their original position:
int unsignedBits7through13(int i) {
return __________;
}
Fill in __________ with a single bitwise expression which will make the code do what it is intended to do.
(i & 0x00003F80)
Consider the following C code, which is intended to extract the lowest 7 bits of the given input i, treating the result as a signed value, leaving the bits in their original position:
int signedBits0through6(int i) {
__________;
return __________;
}
Fill in the blanks with valid C code which will make the function do what it is intended to do.
int signedBits0through6(int i) {
int u = i & 0x0000007F;
if (u & 0x00000040) {
u |= 0xFFFFFF80;
}
return u;
}
Consider the following C code, which is intended to extract the next 7 bits of the given input i, treating the result as a signed value, putting the bits in the rightmost position:
int signedBits7through13(int i) {
__________;
return __________;
}
Fill in the blanks with valid C code which will make the function do what it is intended to do.
int signedBits7through13(int i) {
int u = (i & 0x00003F80) >> 7;
if (u & 0x00000040) {
u |= 0xFFFFFF80;
}
return u;
}
DecodeCode.c.
I'm not including those questions directly here because it is redundant, and because I won't post the answers to them (which would give the world the solutions to the lab!).
Consider the binary value 00001011, stored in $s0.
How can this be multiplied by 4, without using an instruction intented for division or multiplication?
sll $s0, $s0, 2
Consider the signed binary value 00001011, stored in $s0.
How can this be divided by 4, without using an instruction intented for division or multiplication?
sra $s0, $s0, 2
There is only one form of shift left, but there are two forms of shift right. Some questions follow about this fact:
Why are there two forms of shift right?
One is for signed values in two's complement, and the other for unsigned values. For example, consider the following 4-bit number:
1011
Let's say we shift right two places, like so:
XX10
...where XX are the two bit positions on the left we need to fill in.
If the original value was unsigned, then we should always fill in with zeros.
However, if the value was signed, then we'd potentially have a problem if we're using shift right to divide: if we only fill in zeros, then the number becomes positive.
That is, we could end up getting a positive result back if we divide a negative number by a positive number, which wouldn't be correct.
To address this problem, there is a version of shift right (arithmetic shift right) which will fill in the XX's above with whatever the leftmost bit remaining is (in this case, 1).
In summary, this means that the non-arithmetic version of shift right always fills in zeros on the left (resulting in 0010 in the above example), and the arithmetic version fills in whatever bit preserves the signedness of the original value (resulting in 1110 in the above example).
What do the two different forms of shift right do?
Fill in higher order bits with 0s or 1s, according to the mechanism described in the previous answer..
Why is there only one form of shift left?
There are no leftmost bits to fill in. Substituting zeros on the right is the correct behavior regardless of the signedness of the value.
Division by a power of two can be achieved via the clever use of shift right. However, this won't always get the same result as actual division would. Some questions follow about these facts:
Under what conditions will shift right and division not return the same result?
When the dividend is negative.
The difference in results is viewable in a difference between rounding. What is the difference in rounding here?
Integer division rounds towards zero, whereas shift right rounds towards negative infinity.
When dealing with positive values, this distinction is meaningless, as there is no situation under which the behavior is different.
However, with negative values, this causes problems.
To demonstrate, consider -5 / 2.
Mathematically, this results in -2.5.
Using integer division gets -2, but using shift right on the equivalent binary values results in -3.
What does the li pseudoinstruction do?
It loads the immediate value (2nd operand) into the target register (first operand). For example:
li $t0, 7
...puts the value of 7 into register $t0.
Why isn't li an actual MIPS instruction?
All MIPS instructions are exactly 32 bits large.
li can be used to load a 32 bit constant into a register.
Therein lies a problem: the constant's entire value couldn't possibly be held in a single instruction, because there aren't enough bits (in addition to the 32 bits of the constant, there would need to be other bits to encode what the instruction is, which requires in total more than 32 bits).
It is for this reason that li is a psuedoinstruction which can be automatically translated to multiple instructions, whenever we need to specify a constant using the full 32 bits.
li to a form that uses only actual instructions (no pseudoinstructions):
li $t0, 0xFFFFFFFF # is translated into: lui $t0, 0xFFFF ori $t0, $t0, 0xFFFF
Translate the following C code into MIPS assembly.
The variables used below should be placed in the register with the same name.
For example, variable s0 should be placed in register $s0.
If you need additional registers than what the code below uses, use registers $t0 - $t9.
You do not need to exit the program properly.
int s0 = 82; int s1 = s0 << 2; int s2 = s1 * 20; int s3 = s2 + 7; int s4 = s3 - 24; int s5 = s4 / 3; main: li $s0, 82 # int s0 = 82; sll $s1, $s0, 2 # int s1 = s0 << 2; li $t0, 20 # int s2 = s1 * 20 (part 1 of 3) mult $s1, $t0 # (part 2 of 3) mflo $s2 # (part 3 of 3) addi $s3, $s2, 7 # int s3 = s2 + 7 li $t1, 24 # int s4 = s3 - 24 (part 1 of 2) sub $s4, $s3, $t1 # (part 2 of 2) li $t2, 3 # int s5 = s4 / 3 (part 1 of 3) div $s4, $t2 # (part 2 of 3) mflo $s5 # (part 3 of 3)
Translate the following C code into MIPS assembly.
Where <<read integer from the user>> is used, you should use special functionality provided by SPIM to read in an integer from the console.
Where <<print integer s1>> is used, you should use special functionality provided by SPIM to print the integer stored in s1 to the console (you might not be able to do this directly, in which case you'll need to copy the value of s1 into another register first).
The variables used below should be placed in the register with the same name.
For example, variable s0 should be placed in register $s0.
If you need additional registers than what the code below uses, use registers $t0 - $t9.
You do not need to exit the program properly.
int s0 = <<read integer from the user>>;
int s1 = 2;
if (s0 < 7) {
s1 = 3;
}
<<print integer s1>>
main:
# read integer from user
li $v0, 5
syscall
# save integer from user
move $s0, $v0
# store 2 in s1
li $s1, 2
# check if s0 < 7
li $t0, 7
slt $t1, $s0, $t0
# if it's NOT less than 7, skip the body of the if
beq $t1, $zero, printmsg
# we didn't branch, meaning s0 < 7
li $s1, 3
printmsg:
# print s1
li $v0, 1
move $a0, $s1
syscall
Translate the following C code into MIPS assembly.
Where <<read integer from the user>> is used, you should use special functionality provided by SPIM to read in an integer from the console.
Where <<print integer s1>> is used, you should use special functionality provided by SPIM to print the integer stored in s1 to the console (you might not be able to do this directly, in which case you'll need to copy the value of s1 into another register first).
The variables used below should be placed in the register with the same name.
For example, variable s0 should be placed in register $s0.
If you need additional registers than what the code below uses, use registers $t0 - $t9.
You do not need to exit the program properly.
int s0 = <<read integer from the user>>;
int s1 = 2;
if (s0 < 7) {
s1 = 3;
} else {
s1 = s0 + s0;
}
<<print integer s1>>
main:
# read in the integer from the user, and initialize s1
li $v0, 5
syscall
move $s0, $v0
li $s1, 2
# check if $s0 < 7
li $t0, 7
slt $t1, $s0, $t0
# jump to the else branch if this isn't true
beq $t1, $zero, else_branch
# fall through to the true branch
li $s1, 3
j print
else_branch:
add $s1, $s0, $s0
# fall through to the print
print:
li $v0, 1
move $a0, $s0
syscall
Translate the following C code into MIPS assembly.
The variables used below should be placed in the register with the same name.
For example, variable s0 should be placed in register $s0.
If you need additional registers than what the code below uses, use registers $t0 - $t9.
You do not need to exit the program properly.
int s0;
int s1 = 1;
for (s0 = 0; s0 < 10; s0++) {
s1 = s1 * s0;
}
main:
# initialize variables
li $s0, 0
li $s1, 2
loop:
# check loop condition
li $t0, 10
slt $t1, $s0, $t0 # s0 < 10?
beq $t1, $zero, loop_exit # if not, jump to loop_exit
# do body of the loop
mult $s1, $s0
mflo $s1
# increment counter
addi $s0, $s0, 1
j loop
loop_exit:
# this is past the loop