Question 2 of 6

Question 2 (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) 16-bit registers A=0xFFF0, B=0x0010. (b) 32-bit unsigned multiplication in general. (c) the paper's IEEE-754-style single-precision format (bias 128), three arbitrary floats A, B, C. (d) a 16×8 array of 4-byte elements starting at 0x2000.

Find. (a) A+B under both interpretations, with the overflow explanation. (b) whether unsigned 32-bit multiplication is always representable, with a counter-example if not. (c) whether floating-point multiplication distributes over addition. (d) the storage layout and address formula for A[R][C].

Approach. (a) add the raw bit pattern once, then interpret the same result two ways and check each interpretation's overflow rule; (b) find the smallest counter-example; (c) reason from finite-precision rounding at each operation; (d) apply the standard row-major 2-D array address formula.

1. Part (a) — unsigned and signed addition of 0xFFF0 + 0x0010 (16-bit registers). The registers hold the same bit pattern regardless of interpretation, so the hardware performs one addition: $$0\text{xFFF0}+0\text{x0010} = 1111111111110000_2+0000000000010000_2 = 10000000000000000_2$$ This 17-bit result truncates to 16 bits in the register, giving stored bits $0000000000000000_2=0\text{x}0000$. (i) Unsigned: $A=65{,}520,\ B=16$, true sum $=65{,}536$. Since 65,536 exceeds the 16-bit unsigned range (0–65,535), the register instead holds $65{,}536\bmod65{,}536=\boxed{0}$, with the carry-out bit signalling unsigned overflow — the arithmetically correct answer (65,536) cannot be represented in 16 bits. (ii) Signed (2's complement): $A=0\text{xFFF0}=-16$, $B=0\text{x0010}=+16$, true sum $=-16+16=\boxed{0}$. Since $-32{,}768\le0\le32{,}767$, this fits exactly in 16-bit signed range — no signed overflow occurred. Both interpretations happen to read the same stored bit pattern (0x0000), but the unsigned view suffered overflow (the true value 65,536 was lost) while the signed view did not (the true value 0 was preserved exactly) — overflow is a property of the interpretation applied to the bits, not of the bits themselves.
2. Part (b) — can 32-bit unsigned A×B always be represented in 32 bits? No. Unsigned 32-bit values range 0 to $2^{32}-1=4{,}294{,}967{,}295$; multiplying two $n$-bit values can produce a result needing up to $2n$ bits, so a 32-bit × 32-bit product can need up to 64 bits. Example: $A=B=0\text{xFFFFFFFF}=4{,}294{,}967{,}295$. The true product is $$A\times B = 4{,}294{,}967{,}295^2 = 18{,}446{,}744{,}065{,}119{,}617{,}025$$ which needs 64 bits to hold exactly — far more than the 32-bit register can store; only the low-order 32 bits would remain if truncated, with the true product lost. Unsigned multiplication of two $n$-bit operands can produce up to a $2n$-bit result, so a single $n$-bit register cannot always hold A×B; hardware handles this with a double-width result register (e.g. a 64-bit HI:LO pair) or an explicit overflow/carry indication.
3. Part (c) — does $(A+B)\times C=(A\times C)+(B\times C)$ hold in floating point? Not in general. The distributive law is an identity of exact real-number arithmetic, but IEEE-754-style floating point rounds the result of every single operation to the nearest representable value with a finite (24-bit, 1 implicit + 23 explicit) mantissa. The left-hand side performs one addition then one multiplication (two roundings); the right-hand side performs two multiplications then one addition (three roundings), and the intermediate values being rounded differ between the two computation paths. A representative case: let $A$ and $B$ be nearly equal but opposite in sign so that $A+B$ is a small, exactly-representable difference, while $A\times C$ and $B\times C$ are individually large in magnitude; computing $A\times C$ and $B\times C$ separately and then subtracting/adding them can suffer catastrophic cancellation (loss of significant digits when subtracting two close large numbers) that computing $(A+B)$ first avoids entirely, because the cancellation happens on the exact (small-magnitude) values before any rounding-sensitive multiplication occurs. $(A+B)\times C\neq(A\times C)+(B\times C)$ in general — the two sides round at different points in the computation and can disagree, most visibly when catastrophic cancellation is possible on one side but not the other.
4. Part (d) — 2-D array storage and address of A[R][C]. A 2-D array with 16 rows and 8 columns of 4-byte elements is stored row-major: all 8 elements of row 0 occupy the first $8\times4=32$ bytes, then all 8 elements of row 1 occupy the next 32 bytes, and so on — there is no padding between rows or elements. To locate A[R][C], first skip over $R$ complete rows (each row is $8\times4=32$ bytes), then skip over $C$ elements within the target row (each element is 4 bytes): $$\text{addr}(A[R][C]) = \text{base} + (R\times8 + C)\times4 = 0\text{x2000} + 32R + 4C$$ For example $A[0][0]=0\text{x2000}$, $A[1][0]=0\text{x2000}+32=0\text{x2020}$, and the last element $A[15][7]=0\text{x2000}+32\times15+4\times7=\boxed{0\text{x21FC}}$.