reveal.js

## Exam Information, Non-Leaf Procedures, Negative Binary Numbers

---

CS 130 // 2025-09-22

# Exam 1

## Exam Info

* In class Monday 9/29
* If you need accomodations, make arrangements with me before we meet again on *Wednesday*
* **Material:** Everything we've covered, including today and the next class
* **Primary resource:** In-class slides and exercises
* Worth about 10% of your overall grade for the course
* **Kinds of questions:** short  MIPS coding, short answer, multiple choice

### What am I allowed to use during the exam?

- A writing utensil
- One 8.5" x 11" sheet of paper with your hand-written notes on it
    * you can write on both sides 
    * you can write really small (but you probably don't need to)
    * must be prepared by you 
    * nothing printed or photo-copied
    * you will turn it in 
- Nothing else - no books, laptops, phones, ear buds, etc.

### How should I study

* Review slides, use textbook if needed 
* Practice exercises from class, especially ones you were fuzzy on the first time around
* Prepare your note sheet
    * Prioritize and organize the knowledge you need to answer questions
* Practice using the Review Exercises for Exam 1 item on Blackboard
    * Contains actual problems I've used in exams in the past 
    * Probably longer than the actual exam will be
    * May not be quite the same distribution of questions

# Review

## Calling a Procedure

1. Put parameters in appropriate registers
  + `$a0`, `$a1`, `$a2`, `$a3`
2. Transfer control to the procedure: *jump and link*
  + `jal ProcedureLabel`
    - puts the current instruction's address into `$ra`
3. Perform task
4. Place result in a location the callee can find
  + `$v0`, `$v1`
5. Return control to the caller: *jump to addr. in register*
  + `jr $ra`

## Stack
- The **called** procedure is responsible for restoring these registers before returning
    * any saved registers `$s0`, ..., `$s7`
    * `$ra` the return address register
    * the stack pointer `$sp` register 
- 
 Any other register may be used without restoration, so the **calling** procedure is responsible for saving any data before making the call
    * e.g., if you use `$t0`, `$a0`, or `$v0` the other function might change them!

## Stack Frames
![Procedure frame](/Fall2025/CS130/assets/images/COD/stack-frame.png)

## Exercise
- Convert the following Python code into MIPS

```python
def double_it(e):
    return e + e

def calc(c):
    d = double_it(7)
    return c + d

def main():
    a = 5
    b = calc(a)
```

## Exercise Solution: double_it

```python
def double_it(e):
    return e + e
```

```mips
double_it: add $v0, $a0, $a0    # returns e + e
         jr $ra
```

## Exercise Solution: Calc - Take 1

```python
def calc(c):
    d = double_it(7)
    return c + d
```

```mips
calc: li  $a0, 7          # puts 7 in a0
      jal double_it         # calls compute(7)
      add $v0, $v0, $a0   # adds argument to result
      jr  $ra
```

- 
 Unfortunately this will fail. Why?
    + 
 Both `$a0` and `$ra` will be erased!

## Exercise Solution: Calc - Take 2

```python
def calc(c):
    d = double_it(7)
    return c + d
```

```mips
calc: addi $sp, $sp, -8    # allocates space
      sw   $a0, 0($sp)     # stores c on the stack
      sw   $ra, 4($sp)     # stores $ra on the stack
      li   $a0, 7          # puts 7 in a0
      jal  double_it       # calls double_it(7)
      lw   $ra, 4($sp)     # restores $ra
      lw   $a0, 0($sp)     # restores argument
      addi $sp, $sp, 8     # deallocates space
      add  $v0, $v0, $a0   # adds argument to result
      jr   $ra
```

## Exercise Solution: Main

```python
def main():
    a = 5
    b = calc(a)
```

```mips
main:    li   $s0, 5          # a = 5
         move $a0, $s0        # loads a into argument
         jal  calc            # calls calc(5)
         move $s1, $v0        # b = result
```

## Assignment

- [Assignment 3](../../assignments/assignment-3/)
  - Translate a Python program that has functions and Arrays
  - 8 points
  - Part of it has been done - you'll do a "middle" function.

# Negative Numbers

## Negative Numbers in Binary
- We usually represent negative numbers by including a "minus sign" at the beginning of a number: $-437$
- 
 However, when representing numbers for logic circuits, we can **ONLY** use $0$s and $1$s.
- 
 So what do we do?

## Idea 1: Using a Sign Bit
- We could treat the first bit of a number as the "sign" bit where $0$ means positive and $1$ means negative
    + $10010$ is the same as $-0010$
    + $01010$ is the same as $+1010$
- 
 Drawbacks
    + Multiple representations for $0$
    + 
 Addition/subtraction is not as convenient

## Idea 2: Wrap Around

![Odometer rollover](/Fall2025/CS130/assets/images/Odometer_rollover.jpg)

- Numbers "wrap around" from the **largest** number $999999$ to the **smallest** $000000$
- 
 We can do the same thing in binary!
    + 
 If you add one to the largest number, it "wraps around" to the smallest negative number

# Two's Complement

## Two's Complement
- Most computers use **two's complement** to encode signed integer values
- What is it exactly?
    + 
 Non-negative numbers are represented as usual<br>$0000$, $0011$, $0110$
    + 
 To negate a number, you do the following:
        1. Flip all the bits: $0\rightarrow 1$ and $1\rightarrow 0$
        2. Add 1 to the result
    + 
 $0000$, $1101$, $1010$

## Two's Complement
- Most processors are 32-bit or 64-bit, which means values sent to the processor are encoded in 32 or 64 bits, respectively
- 
 In this class, we are using the MIPS 32-bit architecture
- 
 Another way to think about two's complement is:

$1000\\;1001\\;1100\\;1010\\;0110\\;0110\\;0001\\;1110$

$(x_{31}\cdot -2^{31}) + (x_{30}\cdot 2^{30}) + \cdots + (x_{1}\cdot 2^{1}) + (x_{0}\cdot 2^{0})$

## Exercise
### Two's Complement Practice
- Convert each of the following numbers to decimal:

---

- $1111\\;1111\\;1111\\;1111\\;1111\\;1111\\;1111\\;1111$
- $1111\\;1111\\;1111\\;1111\\;1111\\;1111\\;1110\\;0101$
- $0000\\;0000\\;0000\\;0000\\;0000\\;0000\\;0000\\;0101$

## Demo: Adding two binary numbers

* Let's use some 8-bit binary numbers 
<pre>
      0010 0011       0001 1000
    + 1111 0100     - 0011 0110
    ------------    ------------
</pre>

## Exercise

* Using 8-bit binary numbers, show how to compute 
    - 68 - 55
    - 20 + 40
    - 30 - 127
    - -10 + -3