A3Find the 2's complement (i.e. the negation) of the 8-bit number 0110 1100.
original 0110 1100 (= 108)
1's complement 1001 0011 (flip every bit)
add 1 1001 0100
1001 0100 — check: −128+16+4=−108 ✔
A44-bit numbers A = 0110 and B = 0011. Compute A − B using 2's complement addition.
1's complement of B = 1100
2's complement of B = 1100 + 1 = 1101 (= −3)
A: 0110
−B: 1101
-------
1 0011
↑ └──┘
carry result
Discard the carry-out. A − B = 0011 = +3 ✔ (6 − 3 = 3)
A5big★ State when overflow occurs, and check whether these 4-bit operations overflow: (a) 0110 + 0011 (b) 1001 − 0111 (c) 0101 − 0011
Rule: overflow occurs when the result has the wrong sign.
Operation
Operand A
Operand B
Result indicating overflow
A + B
≥ 0
≥ 0
< 0
A + B
< 0
< 0
≥ 0
A − B
≥ 0
< 0
< 0
A − B
< 0
≥ 0
≥ 0
(a) 0110 + 0011 = (+6) + (+3): 0110 + 0011 = 1001 = −7. Two positives gave a negative ⇒ OVERFLOW (true answer +9, but 4-bit range is only −8…+7).
(b) 1001 − 0111 = (−7) − (+7): 2's comp of 0111 = 1001. 1001 + 1001 = 10010 ⇒ result 0010 = +2. Negative minus positive gave a positive ⇒ OVERFLOW (true answer −14).
(c) 0101 − 0011 = (+5) − (+3): operands have the same sign in a subtraction, which is never a risky case. 0101 + 1101 = 10010 = +2. No overflow ✔
Multiplication ★
B1big★ State the three steps of the multiplication algorithm and give its time and space complexity.
Initialise Product = 0, then repeat n times (n = number of bits in the multiplier):
Test Multiplier₀ (the rightmost bit). If it is 1 ⇒ Product = Product + Multiplicand. If 0, do nothing.
Shift the Multiplicand register LEFT 1 bit.
Shift the Multiplier register RIGHT 1 bit.
Stop after the nth repetition.
Time = O(n) — one pass per multiplier bit. Space = O(n + m) — the product of an n-bit multiplicand and an m-bit multiplier is n+m bits long (slide form: O(5n)=O(n) for equal-width operands).
B2big★ Describe the hardware for the multiplication algorithm: name the registers and their widths for 32-bit operands.
Component
Width
Role
Multiplicand register
64 bits
shifts left each iteration
ALU (adder)
64 bits
adds Multiplicand into Product
Multiplier register
32 bits
shifts right each iteration
Product register
64 bits
accumulator, initialised to 0
Control test
—
reads Multiplier₀, drives the add / shift / write signals
The multiplicand register, ALU and product are double the operand width, because the multiplicand climbs into the upper half as it is shifted left.
B3bigMultiply 0011 × 0101 (3 × 5) using the algorithm. Show the register trace.
B4How does the algorithm handle signed multiplication?
Remember the signs, then convert both operands to positive. Run the algorithm for 31 iterations (32-bit operands, signs excluded from the calculation). Negate the product only if the original signs disagree.
B5Write MIPS code to compute $t0 = $t2 × $t1, and explain why two instructions are needed.
mult $t2, $t1
mflo $t0
A 32×32 product is 64 bits, too wide for one register, so MIPS puts it in the dedicated pair Hi (upper 32) and Lo (lower 32). mflo ("move from Lo") copies the low half into a general-purpose register. Use mfhi for the upper half.
Division
C1State the division algorithm and explain why it is called “restoring”.
Initialise Remainder = Dividend. For n+1 iterations:
Remainder = Remainder − Divisor
Test the remainder:
Rem ≥ 0 ⇒ shift Quotient left, set new rightmost bit to 1.
Rem < 0 ⇒ Remainder = Remainder + Divisor (undo it), shift Quotient left, set new rightmost bit to 0.
Shift the Divisor register right 1 bit.
The hardware can't tell in advance whether the divisor fits, so it subtracts unconditionally and restores (adds the divisor back) when the subtraction turns out to have been wrong. Time = O(n + 1) = O(n)
C2Give the quotient and remainder for all four sign combinations of 7 ÷ 2.
Rules: negate the quotient if the signs disagree; the remainder takes the sign of the dividend.
Operation
Quotient
Remainder
+7 ÷ +2
+3
+1
−7 ÷ +2
−3
−1
+7 ÷ −2
−3
+1
−7 ÷ −2
+3
−1
Each satisfies Dividend=Quotient×Divisor+Remainder.
C3After a MIPS div instruction, where are the quotient and remainder? Write the code for j = i % 2 with i in $s0 and j in $s1.
Lo = quotient, Hi = remainder.
addi $t0, $zero, 2
div $s0, $t0
mfhi $s1 # j = i % 2
Floating point ★
D1★ Draw the IEEE 754 single and double precision formats and write the value formula.
11 = 1011₂, so 11.3125₁₀ = 1011.0101₂ (normalized: 1.0110101×23).
D7Explain overflow and underflow in floating point, and give an example of each.
Overflow — a positive exponent becomes too large to fit in the exponent field. Underflow — a negative exponent becomes too large (too negative) to fit.
Overflow: 1.1 × 2¹²⁸ + 1.1 × 2¹²⁸ = 11.0 × 2¹²⁸ = 1.1 × 2¹²⁹
stored exponent 129 + 127 = 256 → won't fit in 8 bits.
Underflow: 1.111 × 2⁻¹²⁶ − 1.1 × 2⁻¹²⁶ = 0.011 × 2⁻¹²⁶ = 1.1 × 2⁻¹²⁸
stored exponent −128 + 127 = −1 → the field holds no
negative values, so it can't be represented.
Like integer overflow, both can raise interrupts.
D8What are ±∞ and NaN, and how are they encoded in single precision?
Exponent
Fraction
Represents
0
0
0 (sign bit may be 0 or 1)
0
nonzero
± denormalized number
1–254
anything
± ordinary floating-point number
255
0
± infinity
255
nonzero
NaN (Not a Number)
±∞ lets software carry on past a divide-by-0 instead of taking an interrupt. NaN is produced by invalid operations such as 0/0 or ∞−∞; its purpose is to let programmers postpone tests and decisions to a later, more convenient point in the program.