⬅ Exercises

Binary to decimal:

1. 0000 0110 = 6
2. 0000 1001 = 9
3. 0000 1111 = 15
4. 0010 0111 = 39
5. 0101 0000 = 80
6. 0111 1111 = 127

Decimal to binary:

1. 3 = 0000 0011
2. 13 = 0000 1101
3. 26 = 0001 1010
4. 55 = 0011 0111
5. 89 = 0101 1001
6. 104 = 0110 1000

Binary to hex:

1. 11 = 0x3 (not 0xC; don’t put 0s on the right side of the number!)
2. 10101 = 0x15 (not 0xA8; you get the idea)
3. 10001001 = 0x89
4. 11110001001 = 0x789
5. 10011001000010 = 0x2642
6. 10011010100111000100110 = 0x4D4E26

Hex to binary:

1. 0x55 = 0101 0101
2. 0xFFF = 1111 1111 1111
3. 0xC01B = 1100 0000 0001 1011
4. 0x287D9 = 0010 1000 0111 1101 1001
5. 0xE315BAD = 1110 0011 0001 0101 1011 1010 1101
6. 0xC0000005 = 1100 0000 0000 0000 0000 0000 0000 0101

1.

    11 11
  0001 0110 = 22
+ 0000 1111 = 15
-----------
  0010 0101 = 37

2.

  111   1
  0011 0011 = 51
+ 0101 0010 = 82
-----------
  1000 0101 = 133

Recall that in 2’s complement, the MSB place has a negative value. Here, it’s the -128s place. So if that place is 0, it’s positive; and if it’s 1, you start at -128 and add the value of the rest of the places onto it.

1. 0000 0110 = +6
2. 0101 1010 = +90
3. 0111 1111 = +127
4. 1000 0001 = -127
5. 1100 1110 = -50
6. 1111 1111 = -1

Remember, for signed numbers, there is one more negative than positives. (For signed numbers, the minimum value will always be exactly a power of two, but negative.)

1. 3 bits
   • unsigned: 0 to 7
   • signed: -4 to 3
2. 5 bits
   • unsigned: 0 to 31
   • signed: -16 to 15
3. 6 bits
   • unsigned: 0 to 63
   • signed: -32 to 31
4. 8 bits
   • unsigned: 0 to 255
   • signed: -128 to 127
5. 10 bits
   • unsigned: 0 to 1023
   • signed: -512 to 511
6. 12 bits
   • unsigned: 0 to 4095
   • signed: -2048 to 2047

1. 0000
   • zero-extended (unsigned): 0000 0000
   • sign-extended (signed): 0000 0000
2. 0011
   • zero-extended (unsigned): 0000 0011
   • sign-extended (signed): 0000 0011
3. 1001
   • zero-extended (unsigned): 0000 1001
   • sign-extended (signed): 1111 1001
4. 1111
   • zero-extended (unsigned): 0000 1111
   • sign-extended (signed): 1111 1111

For the unsigned patterns:

1. 0000 0111
   • Before: 7
   • Truncated: 0111
   • After: 7 ✅
2. 1000 0001
   • Before: 129
   • Truncated: 0001 (not 1000, truncation only gives you the lower (right) bits)
   • After: 1 ⚠️
     • You lost a bit!
     • You get this value because 129 % 16 == 1. When you truncate, if the value being truncated is too big, it will wrap around based on the number of values possible in the new size. Since we are truncating to 4 bits, that’s 2⁴ = 16.

For the signed patterns:

1. 0000 0111
   • Before: +7
   • Truncated: 0111
   • After: +7 ✅
2. 1111 1101
   • Before: -3
   • Truncated: 1101
   • After: -3 ✅
     • It seems a little weird that we threw out all those 1s and got the same value…
     • But negative 2’s complement numbers conceptually have an infinite number of 1s in front of them.
     • So, throwing those extra 1s away is no more “harmful” to the value than throwing away 0s in front of a positive number.
     • (Something like 1111 0000 however would not keep its value when truncated to 4 bits though. You have to keep at least one 1 at the beginning for it to stay negative.)
3. 1110 1111
   • Before: -17
   • Truncated: 1111
   • After: -1 ⚠️
     • This one got mangled. Oops.
     • One way of interpreting how we got -1 is to consider the number circle. The value -17 means “start at 0, then move left (counterclockwise) 17 locations.” If you do that on the 4-bit signed number circle, that will take you around one full revolution (16 locations), then one more, landing you at -1.
     • You could also get something similar with remainder/modulus but that gets into weird territory where people disagree so…

move copies values between registers.

.global main
main:
    li   t0, 100
    move t1, t0

The zero register is always 0.

.global main
main:
    li   t0, 0
    move t0, zero # does the same thing, but with more typing!

When you want to print the value of a register, you must move its value into a0. Otherwise, the syscall will never see the argument. You aren’t REQUIRED to use move to put the value in a0 for all print syscalls. It’s just that in this case, the value I want to print happens to be in another register, so I must move it. (In other cases I might use lw to load a variable’s contents into a0, or li a value directly into a0. Don’t overfit patterns!)

.global main
main:
    # t0 = 12
    li t0, 12

    # print(t0)
    move a0, t0
    li   v0, 1
    syscall

There are many possible registers that could be used to hold the intermediates. My reasoning:

• since I want to keep t0 and t1 unchanged, t2 is the next available temp register
• a0 is where I want the result to end up in so I can print it, so why not use it?
  • I could have used t3 and then move a0, t3, but that just adds an extra unnecessary step.
• Fewer registers = less stuff for you to remember = easier to understand.

.global main
main:
    li t0, 30
    li t1, 50

    # PEMDAS says add (parentheses) first, then multiply, then divide

    # remember: you can use constants as the last operand of math instructions!
    add t2, t1, 10  # t2 = (t1 + 10)
    mul a0, t0, t0  # a0 = t0 * t0
    div a0, a0, t2  # a0 = t0 * t0 / (t1 + 10)

    # aaaand print it
    li v0, 1
    syscall

This one is a little trickier, because you cannot use constants as the second operand to math instructions, and neither operation is commutative. So, the constants have to be put into a temporary register before each operation.

Notice I used t1 for both constants. You don’t have to keep the constant 50 in t1 after the sub, so don’t worry about reusing the register for another purpose. Hands, not variables.

.global main
main:
    li t0, 25

    # a0 = 50 - t0
    li  t1, 50
    sub a0, t1, t0

    # a0 = 1000 / (50 - t0)
    li t1, 1000
    div a0, t1, a0

    # aaaand print it
    li v0, 1
    syscall

If you’ve been doing the other exercises so far, this probably isn’t too challenging. But you may have to retrain your brain to stop seeing v0 as just “the register that chooses the syscall to do.” It’s mainly used for return values.

.global main
main:
    # read an integer...
    li v0, 5
    syscall

    # now, v0 is our temperature Celsius. do the conversion
    # into a0 cause we wanna print it out:
    mul a0, v0, 9
    div a0, a0, 5
    add a0, a0, 32

    # aaaand print it.
    li v0, 1
    syscall

    printInt(((50 - 3) * 13) % 600);

If you actually calculated it out and got printInt(11), well… that wasn’t the point lol

No variables needed. Call readInt(), multiply the return value by 1, then print it out. Order of operations applies to functions too - the call to readInt() happens first because it’s inside the outer set of parentheses.

    printInt(readInt() * 10);

• store x
  • we are only setting x here. load x here would be harmless, but unnecessary. We don’t care what the old value of x was (and since we are initializing x, it doesn’t have an old value).

• load numUsers
  • we are only getting the value of numUsers here. store numUsers is incorrect! stores are only used to set or change the value of a variable, and we are NOT changing its value here.

• load i, store min
  • again no need to load min here - we are only setting its value.
  • this is also the order in which they happen - we have to load the value of i first, so that we can store its value into min. (The order of loads and stores is important when you’re writing code, but if you see a question like this on the exam, order won’t matter.)

• load currentBest, load candidate, store currentBest
  • get the values of the variables to pass them as arguments to max; then store the return value into currentBest.

1. store i
2. load i
3. load i
4. load i, store i

Hopefully this one is simple for you to understand by now. Also, this is exactly the same as a for loop like this:

    for(int i = 0; i < 10; i++) // lines 1, 2, 4
        print(i);               // line 3

• load i, store i, store x
  • This is confusing code that you should not write. But if you use an increment/decrement operator inside a line of code, there can be multiple stores on one line!
  • Because this is a post-decrement, x will be assigned the old value of i, what it contained before being incremented. So if i was 4 before this line of code, then after this line of code, x == 4 and i == 5. This is confusing, and is exactly why people say to never do this.
  • …interestingly, all the “confusing, don’t write this” code has multiple stores in a single line. That’s not a coincidence. Changing the values of things is difficult for us to reason about, and doing multiple changes is even harder to understand. So don’t do it!

1. store array
   • this puts the address of the array object into the local variable named array.
   • array only holds an address! not the array itself.
   • this is what reference types really are - variables of reference types hold addresses.
2. load x, load array, load i, store array[i]
   • whooo, this one is a doozy.
   • We have to load x to get its value. That’s easy.
   • We have to load array, to get the address of the array object out of the array variable. Importantly, we’re not storing into array here. Yes, it’s on the left side of the =, but we’re not changing array. We’re not making it point to a new array object. We are instead changing an item INSIDE array.
   • We have to load i to get its value. This will be combined with the address we got out of array to get the memory location we ultimately want to store into.
   • And finally, we have to store the value we loaded out of x into array[i]. Array slots are variables so they can be used in loads and stores too.
   • The ordering of loads depends on the language and implementation and compiler and other factors. But the store will always be the last thing that happens.

• load System.out
  • System.out is a global variable (or in Java terminology, it’s a static class variable).
  • To call a method on System.out, we have to load it out of the variable. So that’s why there’s a load here.
  • Note that we don’t have to load System, because System is not a variable - it’s a class name. System.out is the full name of the variable we are accessing.

…….

If you want to get really technical, there are actually a couple more loads happening here. See, the way that virtual method calls work in Java is that the addresses of the methods are kept in an array pointed to by the object. The line of code above is really implemented more like:

t0 = System.out;    // load System.out into a register
t1 = t0.methods[7]; // load t0.methods (an array), then load t0.methods[7] (println)
t1(t0, "Hello!");   // call the method in t1 using t0 as the 'this' argument

The 7 above is just an arbitrary number I picked out of a hat. I have no idea if println is the 7th method in the methods array. But it doesn’t matter. The important bit is that the method code address is indexed out of an array.

You’ll also notice I explicitly passed the object - in t0 - as the first argument to the method. That is the this argument in Java, and it’s implicitly passed to every non-static method. a.method() passes a as the this argument to method. This, along with indexing the method out of an array, is what makes object-oriented programming with virtual methods work!

You use lw to load the value of a variable into a register. Here we’re loading directly into a0 because we’re gonna print its value. You can lw into any register; if you did lw t0, var then move a0, t0, that still works, but it’s more typing and more to think about.

If you tried to use li a0, var or move a0, var, you would get an assembler error, because those instructions copy values from other places, not from memory.

.data
    var: .word 5
.text
.global main
main:
    # print(var)
    lw a0, var
    li v0, 1
    syscall

As your programs get longer, you really should start breaking up sequences of instructions with whitespace and comments saying what the next few instructions do.

Also notice that I used as few registers as possible. t0 is a workhorse, being used in a majority of instructions. It’s my “right hand.” t1 gets some use too, when we want to pick up the values of two variables and add them together.

.data
    x: .word 0
    y: .word 0
    z: .word 0
.text
.global main
main:
    # x = 10
    li t0, 10
    sw t0, x

    # y = 20
    li t0, 20
    sw t0, y

    # z = x + y
    lw  t0, x
    lw  t1, y
    add t0, t0, t1
    sw  t0, z # it's really common to forget to store the value back!

    # print(z)
    # yes, I just stored the value of z in the last instruction. but
    # it's just easier for my brain to reload it with "lw" here.
    lw  a0, z
    li  v0, 1
    syscall

    printInt(x + 1);

You are only getting the value of x, not setting it, so x = x + 1 or x++ would be wrong.

Infinite loops are made with j (“jump”). Important things about my solution:

• I used a local label name (starts with an underscore) to label the top of the loop.
  • All control flow labels should start with an underscore.
• I used t0 as my loop counter register, but really any t register would be OK here.
• I’ve indented the code for clarity as to where the loop begins and ends, but it has no effect on how the code runs.

.global main
main:
    # i = 0
    li t0, 0

    _loop:
        # print(i)
        move a0, t0
        li v0, 1
        syscall

        # print('\n')
        li a0, '\n'
        li v0, 11
        syscall

        # i++
        add t0, t0, 1
    j _loop

• The solution below does not include the definition of the print_str macro for brevity.
• If you were having trouble with your solution printing “Odd!” for even numbers and “Even!” for odd numbers, you may have forgotten to invert the condition. See how I’m using bne to choose when to go to the else.
• If your program printed both “Even!” and “Odd!”, you forgot the jump to the _endif label.
• I’ve indented the code inside the if-else for clarity, but again it has no effect on how it runs.

.global main
main:
    print_str "Number? "

    # num = read_int()
    li v0, 5
    syscall

    # if((num % 2) == 0)...
    rem t0, v0, 2
    bne t0, 0, _else # "bne t0, zero, _else" works too
        print_str "Even!\n"
    j _endif
    _else:
        print_str "Odd!\n"
    _endif:

Despite using some weird stuff that we otherwise won’t use (.double, the float registers, l.d, syscall 3), this is not really that different from a loop over an array of ints.

I used t0 as the loop counter but you’re not required to. Any t register would have been fine.

.data
    constants: .double 1.41421, 2.71828, 3.14159
.text
.global main
main:
    li t0, 0
    _loop:
        mul t1, t0, 8
        l.d f12, constants(t1)
        li v0, 3
        syscall

        li a0, '\n'
        li v0, 11
        syscall
    add t0, t0, 1
    blt t0, 3, _loop # you can use constants in branches.

    if(width > MAX_WIDTH)
        print("too wide!\n");

The if condition in Java is the opposite of what it is in MIPS, because in MIPS, you are checking when to skip the code inside the if, and in Java, you are checking when to run the code inside the if.

By the way, it’s not called an “if loop.” It’s not a loop. It’s just an “if statement” or “an if”.

    for(int i = 0; i < 50; i++)
        System.out.print(i + " ");

It’s okay to take some liberties with the pseudocode to make it more natural. There’s no mention of a variable i in the MIPS, but that’s typically what you name for loop counter variables! Also, in Java you’d probably print the int and the space on a single line with string concatenation, rather than doing two print calls in a row.

    if(counter != 0)
        counter--;
    else
        counter = RESET_VALUE;

No variable needed here, even though the MIPS does some funny stuff by breaking up the decrement into a lw before the beq and then a sub-sw after it. The meaning of the Java code is the same, even if it doesn’t do the exact same steps as the original MIPS.

var is at address 0x10010000 (check the labels window when you assemble). 0xBEEFC0DE is 4 bytes long in memory. If the CPU is big-endian, then the byte at 0x10010000 will be the “big end” of the number - so it will be 0xBE. But unless you’re running MARS on a really strange computer, it’s probably little-endian, so the bytes will be in this order:

• address 0x10010000 holds 0xDE
• address 0x10010001 holds 0xC0
• address 0x10010002 holds 0xEF
• address 0x10010003 holds 0xBE

So, when we do lbu a0, var, it will load the byte at 0x10010000 - which is 0xDE.

The assembler places the variables at these locations:

• x at 0x10010000 (the first location in the .data segment)
• y at 0x10010004 (x was a .word, which is 4 bytes, so the next available spot is 0x10010004)
• z at 0x10010008 (same reason as above)

Importantly the addresses are measured in bytes, not bits. So y does not end up at 0x10010020 (0x20 = 32 in base 10), but instead 4 bytes after the start of x.

Also recall that the address of a multi-byte value is the address of its first byte. So for x, its address is 0x10010000, and since it is a .word, that means it also covers 0x10010001 through 0x10010003, but that is left implied.

One .byte is 1 byte. 🙃

So the assembler places them at these addresses:

• a at 0x10010000
• b at 0x10010001
• c at 0x10010002

Since each variable only takes up 1 byte, the “next available address” just increments by 1 for each declaration.

If you got different addresses, maybe you still have the other variables from the previous example? Delete those so that a, b, c are the only variables in the program.

The assembler places them at these addresses:

• b at 0x10010000
• w at 0x10010004!

You may have expected w to end up at 0x10010001, since it’s after a .byte variable. But no: because of alignment, a .word variable must be at an address that is a multiple of 4. So, the assembler skips ahead by 3 bytes and places w at 0x10010004 instead.

This is really what the .byte and .word commands do: they tell the assembler the alignment and size of each variable. As you will learn in the next exercise, they are not really “types” of the variables.

1. No, the assembler does not give an error about this, because there is no enforcement of type correctness. When you declare the variable as .byte, all that means is “make enough room in memory for a 1 byte variable.”
   • If you said “yes”, you’re thinking like a Java programmer! Which isn’t a bad thing. But it’s important to realize that there are no guard rails here. Nothing is stopping you from making this mistake.
2. Maybe the CPU will give an error for this. But it will not give a type error.
   • The CPU doesn’t know anything about types, or your variables’ names, or anything.
   • It could give an error, if little’s address happened to be a number that is not a multiple of 4. But that’s an alignment error.
   • But…
3. What actually happens is it prints 10.
   • We happened to get lucky here. But there’s a big difference between lucky and correct!
   • We got lucky that:
     1. little’s address happens to be a multiple of 4, so lw didn’t crash about alignment, and
     2. the bytes after little all happen to be 0s.
   • Remember that lw picks up 4 consecutive bytes of memory, glues them together, and puts the resulting 32-bit value into a register. That’s all it’s doing here. It’s just that those 4 bytes starting at the address of little happen to be:

    | 0A | 00 | 00 | 00 |
   

   and on a little-endian machine like yours, that gets glued together into 0x0000000A (decimal 10).

This time, the program prints 266. That’s 256 + 10. Why? Because this time, the memory starting at little looks like this:

| 0A | 01 | 00 | 00 |

So when lw glues those bytes together, it gets 0x0000010A (decimal 266).

If I reorder the variables like so:

    big: .word 10000
    another: .byte 1
    little: .byte 10

Now trying to do lw a0, little crashes with an alignment error. This is happening because the assembler assigns the address 0x10010005 to little. That isn’t a multiple of 4, so when you try to lw from it, lw crashes. Hey, at least the CPU sometimes tells you something is wrong! Just not most of the time…

1. lb/lbu will just pick up the “first” byte of big, sign- or zero-extend it, and put that in a0.
   • decimal 10000 is 0x2710, and since your computer is almost certainly little-endian, the “first” byte is 0x10 (decimal 16), so that’s what it will print.
2. lh/lhu pick up the first two bytes of big, sign- or zero-extend it, and put that in a0.
   • Since 0x2710 is only 2 bytes, this will seem to work properly and print 10000.
   • However, it only “works” because the value is small enough to fit in the range of a 16-bit integer.
   • If big held a bigger value (like 100000), it would get truncated in a similar way to using lb/lbu.
3. Depends on the number, but if you did put -10 in little and used lbu, you would get 246.
   • This is because -10 signed is the exact same bit pattern as 246 unsigned: 11110110 binary.
   • The choice of load instruction - lb vs lbu - is what interprets the number differently.
   • lb would sign-extend it to 32 bits, and lbu zero-extends it to 32 bits, giving different values in this case.

The code for printing would look something like:

    # print(arr[5])
    li  t0, 5       # t0 is the index
    mul t0, t0, 4   # multiply the index by the size of one item
    lw  a0, arr(t0) # and use it in the parens in the lw
    li  v0, 1
    syscall

1. It prints 42, which is the value of var.

2. This happens because arr and var are right next to each other in memory. If you look in the data segment view, you’ll see:

           1 |       2 |       3 |       4 |       5 |       42 |
   

   42 - the value of var - is exactly where index 5 of the array would be, if it were 6 items long. But the CPU doesn’t know that. It just does exactly what you tell it to do. lw a0, arr(t0) takes the address of arr, adds t0 to it, and loads a word from there. That’s all it can do.

3. Java solves this problem by implicitly checking the index every single time you access an array. That is, if you write arr[i] in Java, it inserts this right before:

    if(i < 0 || i >= arr.length)
        throw new ArrayIndexOutOfBoundsException();
   

   This prevents the problem, at the cost of doing these checks on every access, which does cost you a little bit of performance.

The code formatting/styling here is important. Assembly languages do not “have” functions, so it’s up to us to divide up our code visually. I like to use a comment with a horizontal line.

These functions take no arguments and return no values, so the a and v registers are unused.

These are examples of functions with side effects: they change their environment in some way. Global variables are part of the “environment,” because multiple functions can see them. Side effects can be useful, but they also make it harder to reason about what a piece of code does, because now you have to consider the function along with all the things it changes.

.data
    count: .word 0
.text

# --------------------------------------
.global main
main:
    # you can call these as many times as you want.
    jal count_up   # count = 1
    jal count_up   # count = 2
    jal count_up   # count = 3
    jal count_down # count = 2

    # print(count)
    lw a0, count
    li v0, 1
    syscall

    # it's important to exit at the end of main!
    li v0, 10
    syscall

# --------------------------------------
count_up:
    lw  t0, count
    add t0, t0, 1
    sw  t0, count
    jr  ra

# --------------------------------------
count_down:
    lw  t0, count
    sub t0, t0, 1
    sw  t0, count
    jr  ra

The code in main is a bit repetitive, but that’s not really the interesting bit. min compares its two arguments and returns the smaller by putting it in v0, which is the One And Only Valid Register to Return Stuff In.

.global main
main:
    # print(min(3, 5))
    li a0, 3
    li a1, 5
    jal min
    move a0, v0
    li v0, 1
    syscall

    print_str "\n"

    # print(min(7, 2))
    li a0, 7
    li a1, 2
    jal min
    move a0, v0
    li v0, 1
    syscall

    print_str "\n"

    # print(min(6, 6))
    li a0, 6
    li a1, 6
    jal min
    move a0, v0
    li v0, 1
    syscall

    # exit
    li v0, 10
    syscall

# -----------------------------------------------------------
# takes 2 arguments (a0, a1) and returns whichever is smaller
min:
    blt a0, a1, _a0_smaller
        move v0, a1
        j _endif
    _a0_smaller:
        move v0, a0
    _endif:
    jr ra

public static byte get_item(int i, int j) {
    return arr[i + j];
}

Who knows what this is for, but this is what it does. No variable needed to stand in for t0. Registers are not variables, sometimes they just hold intermediate values.

    draw_object(obj_x[current_obj], obj_y[current_obj], COLOR_GREEN);

See! One line.

    printInt(numbers[ask_user_for_number()]);

In Java, you don’t have to multiply the index by 4 when accessing an array of ints. You can tell it’s an array of ints in the MIPS code because of lw and multiplying the index by 4.

• print_some_variable
  • on line 4, it loads the value of the variable into t0 instead of a0.
  • To fix this, load into a0 to pass it to the syscall. They’re arguments, not targuments.
• check_input
  • it calls input_get_keys_held on line 4, which returns a value in v0.
  • that value is used on lines 6 and 11, in the ands, but…
  • on line 8, there is jal pressed_left. after line 8, you no longer know what is in v0.
  • So the and on line 11 is assuming v0 still contains the return value from input_get_keys_held, when it may contain something completely different instead.
  • To fix this, you could either:
    • call input_get_keys_held a second time before line 11, or
    • move the return value into an s register
      • (and push/pop that s register at the beginning/end of the function).
• print_array
  • it looks pretty good, it’s using an s register as the loop counter because there’s a jal in the loop, but…
  • it didn’t push s0 at the beginning and pop s0 at the end.
    • This can cause print_array to mess with its caller’s version of s0.
  • To fix this, just add those push/pop lines.

Sometimes there are multiple ways of drawing certain circuits. I’ve tried to include all options where possible.

1. “Y = A XOR (NOT B)”, or in all three conventions:
   • Y = A ⊕ ¬B
   • Y = A ^ ~B
   • Y = A ⊕ B̅
2. “Y = (A AND B) OR C”, or in all three conventions:
   • Y = (A ∧ B) ∨ C
   • Y = (A & B) | C
   • Y = AB + C (in this convention, AND is done before OR so no parentheses needed)
3. “Y = A AND B AND (NOT C)”, or in all three conventions:
   • Y = A ∧ B ∧ ¬C
   • Y = A & B & ~C
   • Y = ABC̅ (see how short this is? I think this is why engineers like it…)

1.

• unsigned addition: yes, overflow occurred, because the MSB carry-out was a 1.
• unsigned subtraction: no overflow, because the MSB carry-out was a 1 instead of 0.
• signed addition/subtraction: no overflow, because we added two negatives and got a negative.

2.

• unsigned addition: no overflow, because the MSB carry-out was a 0.
• unsigned subtraction: yes, overflow occurred, because the MSB carry-out was a 0.
• signed addition/subtraction: yes, overflow occurred, because we added two positives and got a negative.

The truth table looks like:

This is logical NOT. So you could replace the whole mux and constants with just a single NOT gate. Sometimes I see students making this big complicated MUX contraption and all it’s doing is a NOT, so now you know to avoid making this!

There are probably lots of ways of doing this, but here are the most straightforward solutions:

Aren’t they so nice and complementary?

1. 5 << 2 == 20
   • It’s like multiplying by 2² = 4.
2. 30 << 4 == 224, somehow??
   • 30 is a 5-bit number, so when you shift left by 4, you get a 9-bit number, 480.
   • The truncation chops off the topmost bit, leaving you with a weird result.
   • 224 is not arbitrary, it’s 480 % 256. When you chop off bits on the left side of a number, that’s like doing modulo by a power of 2.
3. 5 << 8 == 0… maybe.
   • So, on paper, you might expect all the bits of 5 to get shifted off the left, leaving you with 0s.
   • Some CPUs do exactly this. But not all.
   • On some other CPUs, the shift distance is actually interpreted modulo the number of bits in a register.
     • So shifting left by 8 here might be the same as shifting by 0, and give you 5! Weird!!
4. 100 >> 2 == 25
   • It copies the sign bit (0) into the two topmost places, keeping it positive.
5. -100 >> 2 == -25
   • Same thing, but negative this time.
6. 156 >>> 2 == 39
   • This is unsigned right shift, so the input/output are interpreted as unsigned.
   • (Did you notice 156 is the same bit pattern as -100?)

Each F is 4 bits; then you put a 1, 3, or 7 in front of it based on how many more bits you need.

1. 0xFF
2. 0x3FF
3. 0x1FFFF
4. 0x7FFFFFF

1. +1 = +1.0 x 2^0
2. -1001001 = -1.001001 x 2^6
3. +0.00001 = +1.0 x 2^-5
4. -11100.011 = -1.1100011 x 2^4
5. +10000000000000 = +1.0 x 2^13
6. -0.000000000000111 = -1.11 x 2^-13

1. +1.0 x 2^0
   • sign: 0
   • exponent: 0111 1111 (= 0 + 127)
   • fraction: 000 0000 0000 0000 0000 0000 (the 1 before the binary point is not encoded!)
2. -1.001001 x 2^6
   • sign: 1 (negative)
   • exponent: 1000 0101 (= 6 + 127)
   • fraction: 001 0010 0000 0000 0000 0000 (you do NOT flip the bits. floats use sign-magnitude.)
3. +1.0 x 2^-5
   • sign: 0
   • exponent: 0111 1010 (= -5 + 127)
   • fraction: 000 0000 0000 0000 0000 0000
4. -1.1100011 x 2^4
   • sign: 1
   • exponent: 1000 0011 (= 4 + 127)
   • fraction: 110 0011 0000 0000 0000 0000
5. +1.0 x 2^13
   • sign: 0
   • exponent: 1000 1100 (= 13 + 127)
   • fraction: 000 0000 0000 0000 0000 0000
6. -1.11 x 2^-13
   • sign: 1
   • exponent: 0111 0010 (= -13 + 127)
   • fraction: 110 0000 0000 0000 0000 0000

1. 0 | 1000 1100 | 000 0111 0000 0000 0000 0000 = +1.0000111 x 2^13
   • 1000 1100 is decimal 140; 140 - 127 = 13.
2. 1 | 1000 0111 | 010 0110 1000 0000 0000 0000 = -1.01001101 x 2^8
3. 0 | 0111 1110 | 000 0100 0000 0000 0000 0000 = +1.00001 x 2^-1

Here are the terms. There should be bars over some of the letters. If they’re not showing up correctly, I’ve also included an English description of the term so you can check your interpretation.

The final expression: Y = A̅B̅C + AB̅C̅ + ABC̅

The clock LED flashes once per second: it’s on for half a second, then off for half a second. But the one connected to the output of the flip-flop is flashing at half that speed: it’s on for a second, then off for a second.

It flashes at 1/4 the speed of the original clock. The first divider divides by 2, and then its output becomes the clock signal for the second divider, which divides by 2 again.

15 stages. 32,768 = 2¹⁵, so we have to divide by 2¹⁵ to get to 1. And this is exactly what’s in every quartz clock - a little chip that has a 15-stage clock divider with the crystal as the input and the second hand as the output. Basically.

The lights are counting down in binary. The clock is the 1s place, the output of the first stage is the 2s, the output of the second stage is the 4s, etc. That’s why I said “try looking at it in a mirror” - that will put the 8s place on the left and the 1s place on the right.

When you reset (ctrl/cmd+R), it starts off as 0000. The first clock tick takes it to 1111 (15). Then the next takes it to 1110 (14), then 1101 (13), and so on. So apparently this circuit is a clock divider AND a counter! In fact there are commonly-used chips that act as counters or clock dividers depending on how you configure them, like the 74LS68.

1. 2 bits.
   • There are 4 states (A, B, C, D), and the smallest power of 2 that can represent that is 2² = 4.
2. This could really be anything, but some ideas:
   • Maybe this is an FSM that is run when some machine first turns on, and it initializes something and then stops running until the next time you turn it on.
   • Maybe D is an “error” state which means something really bad happened and we don’t want to ever continue.
   • Or maybe this machine is looking for some pattern of inputs, and D is a “success” state which means it saw that pattern at least once.
     • If you ever learned about regular expressions (or in the future, you learn about them), this is a very normal thing to do!

3. The order of the rows doesn’t matter but your table should have all the same rows. Note that the last row is that arrow with nothing on it - so it “doesn’t care” about either input, and always goes back to D.

   Sn	i	j	Sn+1
   A	0	X	C
   A	1	X	B
   B	0	0	C
   B	0	1	A
   B	1	0	B
   B	1	1	D
   C	0	X	C
   C	1	X	B
   D	X	X	D

If you multiply together two n-bit numbers, you can get a product with at most 2n bits. So for these bit sizes:

1. 16
2. 40
3. 128

Multiplication:

1. hi and lo, “glued together,” represent 0x0000000100000000. Thats a 9-digit hex number, or a 33-bit binary number.
2. You could detect the overflow by using mfhi to get the high-order 32 bits, and testing if they’re 0. For unsigned multiplications, the upper 32 bits will be 0 if the number is < 33 bits. If they’re non-0, an overflow occurred. (It’s kind of an extension of the rule used for detecting overflow in unsigned addition, except now you can get up to 32 bits of “carry out” instead of just 1.)

Division: If you divide the most negative integer (-2^n-1) by -1, you will get a number too big to be represented. E.g. if you are dealing with 4-bit numbers, the most negative integer is -8. -8 / -1 = +8, but there is no +8, because the positives only go up to +7. If you want to see this in action in MARS, put 0x80000000 into a register, and then divide that register by -1. It will stay 0x80000000!

Spec 1:

• A
  • position = 12
  • size = 4 bits
  • mask = 0xF
• B
  • position = 10
  • size = 2 bits
  • mask = 0x3
• C
  • position = 0
  • size = 10 bits
  • mask = 0x3FF

Spec 2:

• opc1
  • position = 27
  • size = 5 bits
  • mask = 0x1F
• r1
  • position = 24
  • size = 3 bits
  • mask = 0x7
• r2
  • position = 21
  • size = 3 bits
  • mask = 0x7
• r3
  • position = 18
  • size = 3 bits
  • mask = 0x7
• opc2
  • position = 16
  • size = 2 bits
  • mask = 0x3
• imm
  • position = 0
  • size = 16 bits
  • mask = 0xFFFF

Something like this. I haven’t even tried compiling this because it doesn’t matter.

    short encode(int A, int B, int C) {
        // here would be a good place to check ranges of A, B, C for validity.
        return (A << 12) | (B << 10) | C; // or (C << 0)
    }

    int getA(short encoded) {
        return (encoded >> 12) & 0xF;
    }

    int getB(short encoded) {
        return (encoded >> 10) & 0x3;
    }

    int getC(short encoded) {
        return encoded & 0x3FF; // or (encoded >> 0) & 0x3FF
    }

1. 1.34 x 10²
2. 7.4 x 10³
3. 9.9823 x 10⁵
4. 1.0 x 10^-1
5. 5.6 x 10^-3
6. 3.72 x 10^-9

1. 13 ns =
   • Engineering: 13 x 10^-9 s (don’t forget the unit - s)
   • Scientific: 1.3 x 10^-8 s (decimal point moves left = add)
2. 750 µs =
   • Engineering: 750 x 10^-6 s
   • Scientific: 7.5 x 10^-4 s
3. 66 MHz =
   • Engineering: 66 x 10⁶ Hz
   • Scientific: 6.6 x 10⁷ Hz
4. 3.5 GHz =
   • Engineering: 3.5 x 10⁹ Hz
   • Scientific: (it’s already in scientific notation)

1. 600 x 10⁶ Hz = 600 MHz (NOT 0.6 GHz. That looks kind of weird.)
2. 1.34 x 10⁶ Hz = 1.34 MHz (NOT 1340 kHz. That also looks weird.)
3. 7.18 x 10³ Hz = 7.18 kHz (it’s already in engineering notation)
4. 680 x 10^-6 s = 680 µs
5. 228 x 10^-9 s = 228 ns (it’s already in engineering notation)
6. 9.4 x 10^-12 s = 9.4 ps

These answers are written using MathJaX, so if you have something like NoScript in your browser, allow the cloudflare CDN to load MathJaX.js so they will render properly.

1. 500 ps = 2 GHz
   •  \(500 \mathrm{\ ps} = 500 \times 10^{-12} \mathrm{\ s} = 5 \times 10^{-10} \mathrm{\ s}\)
   •  \(\frac{1}{5 \times 10^{-10} \mathrm{\ s}} = 0.2 \times 10^{10} \mathrm{\ Hz} = 2 \times 10^{9} \mathrm{\ Hz} = 2 \mathrm{\ GHz}\)
2. 40 ns = 25 MHz
   •  \(40 \mathrm{\ ns} = 40 \times 10^{-9} \mathrm{\ s} = 4 \times 10^{-8} \mathrm{\ s}\)
   •  \(\frac{1}{4 \times 10^{-8} \mathrm{\ s}} = 0.25 \times 10^{8} \mathrm{\ Hz} = 25 \times 10^{6} \mathrm{\ Hz} = 25 \mathrm{\ MHz}\)
3. 250 ns = 4 MHz
   •  \(250 \mathrm{\ ns} = 250 \times 10^{-9} \mathrm{\ s} = 2.5 \times 10^{-7} \mathrm{\ s}\)
   •  \(\frac{1}{2.5 \times 10^{-7} \mathrm{\ s}} = 0.4 \times 10^{7} \mathrm{\ Hz} = 4 \times 10^{6} \mathrm{\ Hz} = 4 \mathrm{\ MHz}\)
   • remember that \(2.5 = \frac{5}{2}\), so the reciprocal is \(\frac{2}{5} = 0.4\).
   • Don’t torture yourself with long division when you don’t need it!
4. 800 MHz = 1.25 ns
   •  \(800 \mathrm{\ MHz} = 800 \times 10^{6} \mathrm{\ Hz} = 8 \times 10^{8} \mathrm{\ Hz}\)
   •  \(\frac{1}{8 \times 10^{8} \mathrm{\ Hz}} = 0.125 \times 10^{-8} \mathrm{\ s} = 1.25 \times 10^{-9} \mathrm{\ s} = 1.25 \mathrm{\ ns}\)
5. 3 GHz = 333 ps (it’s 333.3 repeating exactly, but whatever)
   •  \(3 \mathrm{\ GHz} = 3 \times 10^{9} \mathrm{\ Hz}\)
   •  \(\frac{1}{3 \times 10^{9} \mathrm{\ Hz}} = 0.333 \times 10^{-9} \mathrm{\ s} = 333 \times 10^{-12} \mathrm{\ s} = 333 \mathrm{\ ps}\)

1. Program A’s CPI is 5.25
   •  \((4 \times 0.6) + (5 \times 0.2) + (3 \times 0.05) + (12 \times 0.1) + (10 \times 0.05)\)
2. Program B’s CPI is 7.6
   • You get the idea ;o
3. Program C’s CPI is 6.2

CPU Design 1

1. Program A when run on CPU Design 1 will take 976 s.
   •  \(n = 8 \times 10^{10} \mathrm{\ instructions}\)
   •  \(\mathrm{CPI} = 6.1 \mathrm{\ \frac{cycles}{instruction}}\)
   •  \(f = 500 \times 10^{6} \mathrm{\ Hz} = 5 \times 10^{8} \mathrm{\ Hz}\)
     •  if we want time instead of frequency, \(t = \frac{1}{f} = \frac{1}{5 \times 10^{8} \mathrm{\ Hz}} = 0.2 \times 10^{-8} \mathrm{\ s} = 2 \times 10^{-9} \mathrm{\ s}\)
   • if we calculate using clock frequency:
   \[\frac{n \times \mathrm{CPI}}{f} = \frac{8 \times 10^{10} \times 6.1}{5 \times 10^{8}} = \frac{48.8}{5} \times \frac{10^{10}}{10^{8}} = 9.76 \times 10^{2} = 976 \mathrm{\ s}\]
   • if we calculate using clock cycle time:

   \(n \times \mathrm{CPI} \times t = 8 \times 10^{10} \times 6.1 \times 2 \times 10^{-9} = (8 \times 6.1 \times 2) \times (10^{10} \times 10^{-9}) = 97.6 \times 10^{1} = 976 \mathrm{\ s}\)

   • idk about you, but I think doing \(48.8 \times 2\) is easier than \(48.8 \div 5\).
2. Program B when run on CPU Design 1 will take 4000 s.
   • The clock frequency/time remain the same, so we can reuse those numbers.
   • If we do the calculation using clock frequency, it’s:
   \[\frac{5 \times 10^{11} \times 4}{5 \times 10^{8}} = 4 \times 10^{3} = 4000 \mathrm{\ s}\]
   • If we do the calculation using clock cycle time, it’s:
   \[5 \times 10^{11} \times 4 \times 2 \times 10^{-9} = 40 \times 10^{2} = 4000 \mathrm{\ s}\]

CPU Design 2

1. Program A when run on CPU Design 2 will take 352 s.
   •  \(f = 1 \times 10^{9} Hz\)
   • so, \(t = 1 \times 10^{-9} s\)
   • calculation using clock cycle time (using frequency will be very similar since it’s such a simple number):
   \[8 \times 10^{10} \times 4.4 \times 1 \times 10^{-9} = 35.2 \times 10^{1} = 352 \mathrm{\ s}\]
2. Program B when run on CPU Design 2 will take 1250 s.
   • again using clock cycle time:
   \[5 \times 10^{11} \times 2.5 \times 1 \times 10^{-9} = 12.5 \times 10^{2} = 1250 \mathrm{\ s}\]