Question 1 of 6: Two's-Complement Addition, IEEE-754 Multiply Precision, and Byte-Addressable Array Layout

Question 1: Two's-Complement Addition, IEEE-754 Multiply Precision, and Byte-Addressable Array Layout (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 = 0xFFFFFFFE, B = 0x00000003. (b) IEEE-754 single precision: 1 sign bit S, 8-bit biased exponent E (bias 128), 23-bit mantissa M, value $(-1)^S2^{E-128}(1.M)$. (c) A 4GB address space. (d) A 128-element array A of 16-bit values, byte-addressable memory, base address 0x1000.

Find. (a) A + B under both the unsigned and the 2's-complement signed interpretations, with explanation. (b) Whether $A\times B$ is always exactly representable, and if not, how many extra mantissa/exponent/sign bits would be needed. (c) The address width in bits for a byte-addressable and for a 32-bit-word-addressable 4GB space. (d) The storage layout and the address formula for element A[i].

Approach. (a) add the two 32-bit patterns once as raw bits, then re-interpret the identical result twice, checking each interpretation's own overflow rule. (b) expand the product of two normalized 1.M significands algebraically to see how many fraction bits the exact product needs, and separately bound the range needed for the sum of two biased exponents. (c)–(d) address width $=\lceil\log_2(\text{number of addressable units})\rceil$; array element address $=$ base $+$ index $\times$ element size.

1. Part (a) — adding the bit patterns once, interpreting twice. Adding the raw 32-bit patterns: $0\text{xFFFFFFFE} + 0\text{x00000003} = 0\text{x100000001}$, which does not fit in 32 bits — the register keeps only the low 32 bits, $0\text{x00000001}$, and produces a carry-out of 1 from the top bit.

   Interpretation	A	B	True sum	Stored (32-bit) result	Overflow?
   Unsigned	4,294,967,294	3	4,294,967,297	1	Yes — carry-out = 1, true sum exceeds $2^{32}-1$
   Signed (2's complement)	−2	3	1	1	No — operands have opposite signs, so a signed add of them can never overflow

   Unsigned: $A=4294967294$, $B=3$; the arithmetic sum $4294967297$ needs 33 bits, so it does not fit in the 32-bit register — the hardware reports this as unsigned overflow (a carry out of the MSB), and the register is left holding $0\text{x00000001}=1$, which is the mathematically WRONG unsigned result. Signed 2's complement: the same bit pattern $0\text{xFFFFFFFE}$ is $-2$ and $0\text{x00000003}$ is $+3$; $-2+3=1$ fits comfortably in the signed range, and the rule for detecting signed overflow (result sign differs from both operands' sign, when the operands share a sign) does not apply here since A and B have opposite signs — a sum of opposite-signed operands can never overflow. So the identical addition circuit produces the identical bit pattern $0\text{x00000001}$ both times, but the two interpretations disagree on whether an error occurred: $\boxed{\text{unsigned: overflow, stored value }1\text{ is wrong}}$; $\boxed{\text{signed: no overflow, }1\text{ is the correct answer}}$.
2. Part (b) — can a floating-point product always be represented exactly? Write each normalized operand as $A=1.a$, $B=1.b$ where $a,b$ are the 23-bit fractions (so $a,b\in\{0,\dots,2^{23}-1\}$, each contributing a value $a/2^{23}$). Multiplying the significands: $$A\times B = \left(1+\frac{a}{2^{23}}\right)\left(1+\frac{b}{2^{23}}\right) = 1+\frac{a+b}{2^{23}}+\frac{ab}{2^{46}} = 1+\frac{(a+b)2^{23}+ab}{2^{46}}$$ The last term's numerator, $(a+b)2^{23}+ab$, can be as large as $2\times(2^{23}-1)2^{23}+(2^{23}-1)^2$ — a 48-bit quantity — over a denominator of $2^{46}$. Representing that fraction exactly therefore needs up to $46$ fraction bits, not the $23$ the format provides, so in general $\boxed{A\times B\text{ cannot be represented exactly}}$ — it must be rounded. Mantissa: $46-23=\boxed{23\text{ additional mantissa bits}}$ are needed (46 total) to capture the exact product in the worst case. Exponent: the product's unbiased exponent is the sum of the two operands' unbiased exponents (plus possibly 1 from renormalizing a significand product that lands in $[2,4)$); in biased form the two 8-bit biased exponents can each reach 255, so their sum can reach $510$, which needs $\lceil\log_2(511)\rceil=9$ bits to represent — $\boxed{1\text{ additional exponent bit}}$ (9 total). Sign: the product's sign is simply $S_A\oplus S_B$, still a single bit, so $\boxed{0\text{ additional sign bits}}$ are needed.
3. Part (c) — address width for byte- vs. word-addressable 4GB. A 4GB space has $4\times2^{30}=2^{32}$ addressable units. Byte-addressable: the unit is 1 byte, so there are $2^{32}$ distinct addresses, needing $\log_2(2^{32})=\boxed{32\text{ bits}}$. Word-addressable with a 32-bit (4-byte) word: the number of words is $2^{32}/4=2^{30}$, needing $\log_2(2^{30})=\boxed{30\text{ bits}}$ — two fewer bits, exactly $\log_2(4)=2$ fewer, because each word-address step skips 4 byte-addresses.
4. Part (d) — layout and address formula for array A. Using the byte-addressable space of part (c), each 16-bit (2-byte) element of A occupies 2 consecutive bytes, and the 128 elements are packed contiguously with no gaps (the standard layout for a unidimensional array), so the array occupies $128\times2=256$ bytes in total. If element A[0] starts at 0x1000, element A[i] starts $i$ elements later, i.e. $2i$ bytes later: $$\text{address}(A[i]) = 0\text{x1000} + 2i,\qquad i=0,1,\dots,127$$

   Element	Address
   A[0]	0x1000
   A[1]	0x1002
   A[2]	0x1004
   …	…
   A[127]	0x10FE

   Checking the last element: $A[127]=0\text{x1000}+2(127)=0\text{x1000}+254=\boxed{0\text{x10FE}}$, and it occupies bytes 0x10FE–0x10FF, so the whole array spans 0x1000–0x10FF (256 bytes), consistent with the computed size.