Question 2 of 6: Signed/Unsigned Arithmetic, Floating-Point Precision, and Array Addressing

Question 2: Signed/Unsigned Arithmetic, Floating-Point Precision, and Array Addressing (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) 32-bit registers $A=\texttt{0xFFFFFFFF}$, $B=\texttt{0x00000010}$. (b) IEEE-754 single precision: 1 sign bit, 8-bit exponent $E$ (bias 128 per the question's own formula), 23-bit mantissa $M$; value $=(-1)^S\times2^{(E-128)}\times1.M$. (c) A $128\times64$ array of 32-bit (4-byte) elements, base address 0x1000.

Find. (a) $A+B$ under unsigned and signed 2's-complement interpretation. (b) whether $A+B$ is always exactly representable, and if not, how many extra sign/exponent/mantissa bits would guarantee it is. (c) the storage layout and the address formula for $A[R][C]$.

Approach. (a) add the raw bit patterns modulo $2^{32}$, then separately interpret the same result bits as unsigned and as 2's-complement, checking each interpretation's own overflow condition. (b) align mantissas by the exponent difference before adding, and see how many bits that alignment can cost. (c) apply row-major base-plus-stride addressing.

1. Part (a) — unsigned vs. signed addition of the same bits. Adding the raw 32-bit patterns gives $\texttt{0xFFFFFFFF}+\texttt{0x00000010}=\texttt{0x10000000F}$, a 33-bit result; keeping only the low 32 bits (what the register actually stores) leaves $$\boxed{\texttt{0x0000000F}=15}$$ as the stored bit pattern — identical for both interpretations, since addition is performed on bits, not on a chosen interpretation.
   (i) Unsigned: $A=4{,}294{,}967{,}295$, $B=16$; the true sum $4{,}294{,}967{,}311$ exceeds the unsigned range ($\le2^{32}-1$), so a carry out of bit 31 is generated and discarded — the register ends up holding $15$, and this IS an (unsigned) overflow: the true mathematical sum could not fit.
   (ii) Signed 2's complement: the same bit pattern $A=\texttt{0xFFFFFFFF}$ is $-1$, and $B=\texttt{0x00000010}$ is $+16$; the true sum $-1+16=15$ fits comfortably inside the signed range, so the stored pattern $\texttt{0x0000000F}=15$ is the CORRECT, exact signed result — no overflow, because signed overflow can only occur when both operands share a sign and the result's sign differs, which cannot happen when adding a negative and a positive number.
2. Part (b) — can $A+B$ always be represented exactly? No, not in general. IEEE-754 addition must first ALIGN the two mantissas to a common exponent (the larger of $E_A,E_B$) by right-shifting the smaller-exponent operand's mantissa by $d=|E_A-E_B|$ bit positions before adding. Any of that shifted-out mantissa's low bits that don't fit back into the 23-bit fraction field are simply lost (rounded away) — e.g. $A=1.0$, $B=2^{-30}$ have $d=30$, so $B$'s entire contribution shifts 30 places past the 23 available fraction bits and $1.0+2^{-30}$ rounds straight back to $1.0$ in float32, exactly reproducing the register value and demonstrably NOT equal to the true sum.
   • Sign: $\boxed{0}$ extra bits are ever needed — the sum of two floats always has one well-defined sign, computed by the usual add/subtract sign rules.
   • Exponent: at most $\boxed{1}$ extra bit — adding two aligned mantissas can at most double the magnitude (e.g. $1.75+1.75=3.5$ moves the exponent from $2^0$ to $2^1$, a carry-out of exactly one bit), so a single extra exponent bit accommodates any growth caused by one addition.
   • Mantissa: up to $d=|E_A-E_B|$ extra bits are needed to preserve the smaller operand's shifted-out bits exactly — and since two normalized single-precision numbers have biased exponents anywhere in $1\le E\le254$, $d$ can be as large as $254-1=253$, no small, FIXED number of extra mantissa bits guarantees an exact sum for every possible $A,B$; the required extension grows without a small bound as the operands' exponents drift apart.
3. Part (c) — two-dimensional array addressing. With row-major storage, row 0's 64 elements are laid out first, contiguously, then row 1's 64 elements, and so on — element $A[R][C]$ therefore sits $R$ whole rows (each $64\times4=256$ bytes) plus $C$ more elements past the array's base: $$\text{addr}(R,C)=\boxed{\texttt{0x1000}+(R\times64+C)\times4}\qquad 0\le R\le127,\ 0\le C\le63.$$ For example, $A[0][0]=\texttt{0x1000}$, $A[1][0]=\texttt{0x1000}+256=\texttt{0x1100}$, and the very last element $A[127][63]=\texttt{0x1000}+8191\times4=\texttt{0x8FFC}$.