reveal.js

# Machine Code and Logic Operations

---

CS 130 // 2024-09-10

### Video shared by Jacob

Binary counting animation

https://www.reddit.com/r/Damnthatsinteresting/comments/ljyzoh/binary_to_20_visually_explained/

![Career Fair flyer](/Fall2024/CS130/assets/images/careerfair2024.png)

# Negative Numbers in Binary

## 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
    + 
 Confusion over where the sign bit should be

## Idea 2: Wrap Around

![Odometer rollover](/Fall2024/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$

## Assignment is up

- [Assignment 2](../../assignments/assignment-2/)
  - pen-and-paper 
  - convert some numbers between decimal, hexadecimal, and binary

# MIPS Machine Code

## MIPS Machine Code
- Each MIPS instruction is encoded in 32-bits
    + 
 `add` `$t0`, `$s1`, `$s2`
    + 
 000000 10001 10010 01000 00000 100000

---

![R-Type Instruction](/Fall2024/CS130/assets/images/COD/r-type-instruction.png)

## R-Type Instructions
![R-Type Instruction](/Fall2024/CS130/assets/images/COD/r-type-instruction.png)

---

1. 
 `op` (6 bits): Opcode
2. 
 `rs` (5 bits): First operand register
3. 
 `rt` (5 bits): Second operand register
4. 
 `rd` (5 bits): Destination register (result)
5. 
 `shamt` (5 bits): Shift amount
6. 
 `funct` (6 bits): Function code

## I-Type Instructions
![I-Type Instruction](/Fall2024/CS130/assets/images/COD/i-type-instruction.png)

---

1. `op` (6 bits): Opcode
2. `rs` (5 bits): First operand register
3. `rt` (5 bits): Second operand register
4. 
 `data` (16 bits): Constant or address

## Exercise

- Use Mars to figure out how each of the following is represented in bits (convert from hex!).
```mips
add $t2, $t1, $t0
sub $t2, $t1, $t0
addi $t0, $t0, 3
```
- What are the opcodes for `add`, `sub`, and `addi`?

## R-Type VS I-Type
- Why do we need the I-type? Why not just implement `addi`, `lw`, and `sw` using the R-type format?
    + 
 Allows us to specify larger addresses and constants
    + 
 $2^5 = 32$ and $2^{16} = 65536$

# Logical Operations

## Boolean values
- Suppose I create a `bool` variable in Python:
    ```py
    b = True
    ```
- 
 How many bits of memory were just allocated?
    + 
 An entire word!
    + 
 `b` is a **memory address** that "points to" `True`

## Logical operator investigation

Before executing: guess what you think `$t0`-`$t5` will be

Execute it: were you right?

Is this how `and` and `or` behave in Python?
</div>
<div>

```mips
   .text

li $s0, 0
   li $s1, 1
   li $s2, 2
   li $s3, 3
   
   and $t0, $s0, $s1
   or $t1, $s0, $s1
   andi $t2, $s1, 1
   ori $t3, $s1, 0
   
   or $t4, $s1, $s2
   and $t5, $s2, $s3
```

</div>

## Set on Less Than investigation

Before executing: guess what you think `$t0`-`$t5` will be

Execute it: were you right?

What do `sle` and `sgt` mean? What do they get translated into by the assemler?
</div>
<div>

```mips
.text

li $s1, 2
li $s2, 2
li $s3, 3

#slt: "set on less than"
slt $t0, $s2, $s3
slt $t1, $s1, $s2
slt $t2, $s3, $s2
slti $t3, $s3, 10

#psuedoinstructions
sle $t4, $s1, $s3
sle $t5, $s1, $s2
sgt $t6, $s3, $s2
```

</div>

## Shifting investigation

Execute it: what do `sll` and `srl` do?

What happens if you shift an odd number?

Are these R-Type or I-Type instructions?
</div>
<div>

```mips
.text

li $s0, 16

#shift left logical
sll $t0, $s0, 1
sll $t1, $s0, 2

#shift right logical
srl $t2, $s0, 2
```

</div>

# Conditionals

## Branching
- **Branching** allows MIPS programs to skip around to different parts of the program
- Useful for
    - conditional statements (if, if-else, etc.)
    - loops

- continue executing at the line labeled `my_label`
```mips
b my_label
#...
my_label:
```
- 
 continue executing at the line labeled `my_label` if `$s0` and `$s1` are equal
```mips
beq $s0, $s1, my_label
```
- 
 continue executing at the line labeled `my_label` if `$s0` and `$s1` are _not_ equal
```mips
bne $s0, $s1, my_label
```

## Compiling an `if` Statement

```python
    if i == j:
        k = 1

print("The value of k is",k)
```

</div>
<div>

```mips
.data

i: 5
j: 8
k: 0
message: .asciiz "The value of k is "

.text

lw $s0, i
	lw $s1, j
	
	bne $s0, $s1, disp_msg
	li $s2, 1
	sw $s2, k

disp_msg:
	li $v0, 4 #4 is the code for printing a string
	la $a0, message #the argument for the syscall
	syscall 
	
	li $v0, 1 #1 is the code for printing an int
	lw $a0, k #the argument for the syscall
	syscall 
```
<div>

## Exercise

- Run the above program in Mars, observe the output
- Change it so `i` and `j` are equal, run again
- Translate the following Python program into MIPS
```python
    if i == j:
        k = 1
    else:
        k = 2

print("The value of k is",k)
```