# Arithmetic

## 20 September 2005

• Arithmetic and its implementation

• Exam next Thursday

## Arithmetic

• Where we've been:

• Abstractions

• Instruction Set Architecture

• Assembly Language and Machine Language

• Implementing the Architecture

## Numbers

• Bits are just bits (no inherent meaning)

• conventions define relationship between bits and numbers

• Binary numbers (base 2)

• binary: 0 1 10 11 100 101 110 111 1000 ...

• decimal: 0...2^n-1

• Of course it gets more complicated:

• numbers are finite (overflow)

• fractions and real numbers

• negative numbers

• - e.g., no MIPS subi; addi can add a negative number)

• How do we represent negative numbers?

• which bit patterns will represent which numbers?

## Possible Representations

 Bits Sign Magnitude 1's complement 2's complement 000 +0 +0 +0 001 +1 +1 +1 010 +2 +2 +2 011 +3 +3 +3 100 -0 -3 -4 101 -1 -2 -3 110 -2 -1 -2 111 -3 -0 -1
• Issues: balance, number of zeros, ease of operations

• Which is best? Why?

## MIPS uses 2's complement

• 32-bit signed numbers

```0000 0000 0000 0000 0000 0000 0000 0000 = 0
0000 0000 0000 0000 0000 0000 0000 0001 = +1
0000 0000 0000 0000 0000 0000 0000 0010 = +2
...
0111 1111 1111 1111 1111 1111 1111 1110 = +2,147,483,646
0111 1111 1111 1111 1111 1111 1111 1111 = +2,147,483,647
1000 0000 0000 0000 0000 0000 0000 0000 = –2,147,483,648
1000 0000 0000 0000 0000 0000 0000 0001 = –2,147,483,647
1000 0000 0000 0000 0000 0000 0000 0010 = –2,147,483,646
...
1111 1111 1111 1111 1111 1111 1111 1101 = – 3
1111 1111 1111 1111 1111 1111 1111 1110 = – 2
1111 1111 1111 1111 1111 1111 1111 1111 = – 1
```

## 2's complement operations

• Negate a 2's complement number by inverting all bits and add 1

• remember: “negate” and “invert” are quite different!

• -3 == -(0011) == ~0011 + 1 == 1100 + 1 == 1101

• Converting n bit numbers into numbers with more than n bits:

• MIPS 16 bit immediate gets converted to 32 bits for arithmetic

• copy the most significant bit (the sign bit) into the other bits

• 0010 -> 0000 0010

• 1010 -> 1111 1010

• "sign extension" (lbu vs. lb)

Just like in grade school (carry/borrow 1's)

 00111 00111 00110 + 00110 - 00110 - 00101 01101 00001 00001

2's complement operations are easy

 00000111 00000111 - 00000110 + 11111010 00000001

Overflow (result too large for finite word)

 01110000 + 00010000 10000000

## Detecting Overflow

• No overflow when adding a positive and a negative number

• No overflow when signs are the same for subtraction

• Overflow occurs when the value affects the sign:

• overflow when adding two positives yields a negative

• or, adding two negatives gives a positive

• or, subtract a negative from a positive and get a negative

• or, subtract a positive from a negative and get a positive

• Consider the operations A + B, and A – B

• Can overflow occur if B is 0 ?

• Can overflow occur if A is 0 ?

## Effects of Overflow

• An exception (interrupt) occurs

• Control jumps to predefined address for exception

• Interrupted address is saved for possible resumption

• Details based on software system / language

• example: flight control vs. homework assignment

• Don't always want to detect overflow

• - new MIPS instructions: addu, addiu, subu - note: addiu still sign-extends the operand - note: sltu, sltiu for unsigned comparisons

## Boolean Algebra & Gates

• Consider a logic function with three inputs: A, B, and C.

• Output D is true if at least one input is true

• Output E is true if exactly two inputs are true

• Output F is true only if all three inputs are true

• Show the truth table for these three functions.

• Show the Boolean equations for these three functions.

## Truth Table

 A B C D E F 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1

D=A|B|C   E=(~A&B&C)|(A&~B&C)|(A&B&~C)   F=A&B&C

## An ALU

Let's build an ALU to support andi and ori instructions. We'll build a 1 bit ALU and use 32 of them.

## ALU truth table

 op a b result 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

~op & (a|b) | op & a & b == ~op&a | ~op&b | op&a&b

## Multiplexor

Selects one of the inputs to be the output

• Not easy to decide the "best" way to build something

• Don't want too many inputs to a single gate

• Don't want to have to go through too many gates

• Ease of comprehension is most important to us

 a b cin sum cout 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1
```Cout = a&b | a&Cin | b&Cin
sum = a&~b&~Cin | ~a&b&~Cin | ~a&~b&Cin | a&b&Cin```

## Building a 32 bit ALU

2's complement: just negate b and add, how?

## Tailoring the ALU to MIPS

• Need to support the set-on-less-than instruction (slt)

• remember: slt is an arithmetic instruction

• produces a 1 if rs < rt and 0 otherwise

• use subtraction: (a-b) < 0 implies a < b

• Need to support test for equality (beq \$t5, \$t6, \$t7)

• use subtraction: (a-b) = 0 implies a = b

## Conclusion

• We can build an ALU to support the MIPS instruction set

• key idea: use multiplexor to select the output we want

• we can efficiently perform subtraction using two’s complement

• we can replicate a 1-bit ALU to produce a 32-bit ALU

• all of the gates are always working

• the speed of a gate is affected by the number of inputs to the gate

• the speed of a circuit is affected by the number of gates in series (on the “critical path” or the “deepest level of logic”)

• Our primary focus: comprehension, however,

• Clever changes to organization can improve performance (similar to using better algorithms in software)

## Educational Highlight

Work in a team to design a computer-based application that makes the world a better place

last edited 2005-09-20 17:28:34 by GaryBishop