Arithmetic

Two’s Complement

Subtraction

$$\begin{array}{rl}A-B& =A+(-B{)}_{2^{\prime }s}\\ & =A+(\underset{111\dots 11}{\underbrace{2^n-1}}-B+1)\\ & =A+(2^n-B)\\ & =\underset{\text{Ignore}}{\underbrace{2^n}}+\underset{\text{Result}}{\underbrace{(A-B)}}\end{array}$$

Overflow

Operation	Sign Bit of X	Sign Bit of Y	Sign Bit of Result	Sign Bit of Expected
Adding two +ve (0)
X + Y	0	0	1	X + Y = 0
X - Y	0	1	1	(X - (-Y)) = 0
Subtracting two -ve (1)
X + Y	1	1	0	((-X) + (-Y)) = 1
X - Y	1	0	0	((-X) - Y) = 1

MIPS “Unsigned”

• Sign extension (arithmetic operations)
  • addi
  • addiu
  • slti
  • lh
  • lb
• Zero extension (logical operations)
  • andi
  • ori
  • lhu
  • lbu

Important

Immediate operand in MIPS is always sign extended

Arithmetic Logic Unit (ALU)

1-Bit Full Adder

A	B	Carry In	Carry Out	Sum Out	a + b + CarryIn
0	0	0	0	0	0 + 0 + 0 = 00
0	0	1	0	1	0 + 0 + 1 = 01
0	1	0	0	1	0 + 1 + 0 = 01
0	1	1	1	0	0 + 1 + 1 = 10
1	0	0	0	1	1 + 0 + 0 = 01
1	0	1	1	0	1 + 0 + 1 = 10
1	1	0	1	0	1 + 1 + 0 = 10
1	1	1	1	1	1 + 1 + 1 = 11

Note that $A+\bar{A}B=A(1+B)+\bar{A}B=A+AB+\bar{A}B=A+B(A+\bar{A})=A+B$

$$\begin{array}{rl}{C}_{out}& =\bar{A}BC+A\bar{B}C+AB\bar{C}+ABC\\ & =BC(\bar{A}+A)+A\bar{B}C+AB\bar{C}\\ & =C(B+A\bar{B})+AB\bar{C}\\ & =C(A+B)+AB\bar{C}\\ & =BC+A(C+B\bar{C})\\ & =AB+AC+BC\end{array}$$

Note that $\overline{A\oplus B}=\overline{A\bar{B}+\bar{A}B}=(\bar{A}+B)(A+\bar{B})=\bar{A}A+\bar{A}\bar{B}+BA+B\bar{B}=\bar{A}\bar{B}+AB$

$$\begin{array}{rl}S& =\bar{A}\bar{B}C+\bar{A}B\bar{C}+A\bar{B}\bar{C}+ABC\\ & =C(\bar{A}\bar{B}+AB)+\bar{C}(\bar{A}B+A\bar{B})\\ & =C(\overline{A\oplus B})+\bar{C}(A\oplus B)\\ & =C\oplus (A\oplus B)\end{array}$$

• Bin and Cin can be combined

	BInvert	CarryIn
AND	0	x
OR	0	x
NOT	0	0
SUB	1	1

• slt
  • operation 3 for slt
  • alu1 - alu31 set = 0
  • alu0 set = alu31 set

Overflow

Operation	Sign A	Sign B	Sign Result	BInvert	a3	b3	set
A + B	0	0	1	0	0	0	1
A + B	1	1	0	0	1	1	0
A - B	0	1	1	1	0	1	1
A - B	1	0	0	1	1	0	0

beq (A - B == 0)

• BInvert = 1
• Operation = 2
• Check if all bits 0, and then NOT

Multiplication

• Multiplier, stored in product
• Multiplicand (M), 32 bits
• Product (P), 32 + 32 = 64 bits
  • Initially zero extended
  • Left(P) is 0
  • Right(P) is the multiplier

1. If Product0 is 1
   1. Left(P) = Left(P) + M
2. P >> 1
3. Exit on the 32nd repetition

Signed Multiplication

• Do the above calculation based on the absolute value
• Negate result based on sign of multiplicand/multiplier
• Booth’s algorithm

Unsigned Overflow

No overflow if Hi is 0

multu $s0, $s1
mfhi $at
mflo $s2

beq $at, $0, no_overflow
    # overflow
no_overflow:
    # no overflow

Signed Overflow

No overflow if every bit in Hi is same as sign bit of Lo

sra $t0, $s2, 31 will turn 0...x to 0...0, making all bit to the sign of Lo, then compare it with Hi

mult $s0, $s1
mfhi $at
mflo $s2

sra $t0, $s2, 31 # shift right arithmetic
beq $at, $t0, no_overflow
    # overflow
no_overflow:
    # no overflow

Division

• Quotient, stored in remainder
• Dividend, stored in remainder
• Divisor (D), 32 bits
• Remainder (R), 32 + 32 = 64 bits
  • Initially zero extended
    • Left(R) is 0
    • Right(R) is dividend
  • Quotient appear from the right by shifting
  • Remainder will appear at the left at the end

1. R << 1, now the lsb is the useless 0
2. Left(R) = Left(R) - D
3. If Left(R) < 0
   1. Left(R) = Left(R) + D, to undo subtraction
   2. R << 1
   3. R_0 = 0
4. If Left(R) >= 0
   1. R << 1
   2. R_0 = 1
5. Exit on 32nd repetition
6. Left(R) >> 1

If divisor is 0, quotient will be all 1

Signed Division

• Sign of dividend and remainder is same
• Deduce sign of quotient by looking at divisor

Dividend	Divisor	Quotient	Remainder
+	+	+	+
-	+	-	-
+	-	-	+
-	-	+	-