COMP2120-Assignment1
File description: Assignment 1 of COMP2120 (24/25 Spring) with solutions.
Document status: LTS
Last modified: 2026-09-11 21:12 HKT
COMP2120 Computer Organisation
24/25 Semester 2
Assignment 1
1. Write down the logical expression P = f (A, B,C) corresponding to the following truth table (simplification of logical expression
is not required):
A B C P
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Solution: Since there are less rows with P = 0 than rows with P = 1, it is easier to work by Product-of-Sums. First, identify
the rows with P = 0, which are (0, 0, 1), (0, 1, 0) and (1, 0, 0). For each of the rows, construct a product of all the variables,
such that the term equals 1, then apply NOT to the term to invert it to 0. This gives:
(0, 0, 1) =⇒ A · B ·C
(0, 1, 0) =⇒ A · B ·C
(1, 0, 0) =⇒ A · B ·C
Simplify each term by applying De Morgan’s Theorem, then combine them with AND, we have:
P =
A + B +C
·
A + B +C
·
A + B +C
2. Consider a 16-bit 2’s complement representation.
(a) What is the largest (most positive) number and the smallest (most negative) value in this representation scheme?
Solution: Recall that in 2’s complement representation, the most significant bit (MSB) is the sign bit. The largest number
is when the MSB is 0 and all other bits are 1’s, i.e., 0111 1111 11111111
2
= 32767
10
.
Similarly, the smallest number is when the MSB is 1 and all other bits are 0’s, i.e., 1000000000000000
2
= −32768
10
.
(b) Write down the bit pattern representing 18, -18, 25, and -25, respectively.
Solution: The bit patterns are:
Decimal Bit Pattern
18 0000 0000 0001 0010
2
-18 1111 1111 1110 1110
2
25 0000 0000 0001 1001
2
-25 1111 1111 1110 0111
2
(c) What are the values of the above bit patterns if they are treated as unsigned integers?
Solution: When treated as unsigned integers, the values are:
Bit Pattern uint Value
0000 0000 0001 0010
2
18
1111 1111 1110 1110
2
65 518
0000 0000 0001 1001
2
25
1111 1111 1110 0111
2
65 511
Page 1 of 7
Page 1 of 7
(d) Add the bit patterns together for the following:
(1) 18 + 25 (2) 18 + (−25) (3) (−18) + 25 (4) (−18) + (−25)
Solution: The bit patterns required are:
(1) 18 + 25 = 43
0000 0000 0001 0010 (+18)
+ 0000 0000 0001 1001 (+25)
0000 0000 0010 1011 (+43)
(2) 18 + (−25) = −7
0000 0000 0001 0010 (+18)
+ 1111 1111 1110 0111 (−25)
1111 1111 1111 1001 (−7)
(3) (−18) + 25 = 7
1111 1111 1110 1110 (−18)
+ 0000 0000 0001 1001 (+25)
1 0000 0000 0000 0111 (+7)
(4) (−18) + (−25) = −43
1111 1111 1110 1110 (−18)
+ 1111 1111 1110 0111 (−25)
1 1111 1111 1101 0101 (−43)
3. Prove that the multiplication of an n-bit binary number A and an m-bit binary number B gives a product A × B of no more than
(n + m) bits.
Solution: Note that A ∈ [0, 2
n
− 1] and B ∈ [0, 2
m
− 1], m, n ≥ 1, and m + n ≥ 2.
The maximum value of A × B is given by:
max(A × B) = max(A) × max(B)
= (2
n
− 1) × (2
m
− 1)
= 2
n
× 2
m
− 2
n
− 2
m
+ 1
= 2
n+m
− 2
n
− 2
m
+ 1
Note that to represent the term 2
n+m
, we need at least (n + m + 1) bits, and the maximum value representable by (n+ m) bits is
2
n+m
− 1. Therefore, we need to show that:
∀m, n ∈ [1, +∞) ∩ Z, 2
n+m
− 2
n
− 2
m
+ 1 < 2
n+m
(1)
Assume that m is constant, when n = 1, we have:
L.H.S. = 2
1+m
− 2
1
− 2
m
+ 1
= 2
m+1
− 2 − 2
m
+ 1
= 2
m+1
− 2
m
− 1
= 2
m
(2 − 1) − 1
= 2
m
− 1
and R.H.S. = 2
m+1
, so L.H.S. < R.H.S. clearly holds. Therefore, the proposition holds for n = 1.
Now, assume that the proposition holds for n = k where k ∈ [1, +∞) ∩ Z, i.e.,
∀k ∈ [1, +∞) ∩ Z, 2
k+m
− 2
k
− 2
m
+ 1 < 2
k+m
(2)
We need to show that the proposition holds for n = k + 1, i.e.,
L.H.S. = 2
k+1+m
− 2
k+1
− 2
m
+ 1
= 2
k+m
· 2 − 2
k
· 2 − 2
m
+ 1
= 2
k+m
− 2
m
− 2
k
+ 1 + 2
k+m
− 2
k
and
R.H.S. = 2
k+1+m
= 2
k+m
· 2
= 2
k+m
+ 2
k+m
Page 2 of 7
Page 2 of 7
Subtract 2
k+m
from both sides, we have:
L.H.S. = 2
k+m
− 2
m
− 2
k
+ 1
Induction Hypothesis (Eq. 2)
−2
k
and R.H.S. = 2
k+m
Observe that by the induction hypothesis, we have 2
k+m
− 2
m
− 2
k
+ 1 < 2
k+m
, and since 2
k
> 0, we have:
L.H.S. < 2
k+m
− 2
k
< 2
k+m
Therefore, the proposition holds for n = k + 1.
By the principle of mathematical induction, the proposition holds for all n ∈ [1, +∞) ∩ Z.
Now, proposition 2 is partially proven for all n and constant m. Observe that the proposition is symmetric in m and n, i.e., m
and n are dummy variables. Therefore, it is trivial to show that the proposition holds for all m ∈ [1, +∞) ∩ Z and constant n.
Hence, we have shown that the proposition holds for all m,n ∈ [1, +∞) ∩ Z.
Now, we can conclude that the A × B = 2
n+m
− 2
n
− 2
m
+ 1 < 2
n+m
, which means that the product A × B can be represented by
no more than (n + m) bits.
Q.E.D.
4. Verify the validity of the multiplication of integers (2’s complement) procedure in the lecture notes. (Give the prove)
Solution: It may be helpful to recall that for any n-bit 2’s complement number (a
n−1
a
n−2
. . . a
2
a
1
a
0
)
2
, where a ∈ [0, 1], the
value of the number is given by
A = −2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
Also, recall that the multiplication procedure in the lecture notes involves sign-extension and negation of the multiplicand and
multiplier, it would be helpful to first prove that these two operations are valid.
Proof of sign-extension:
Suppose A is sign-extended to A
′
of m bits, where m > n. Then, A
′
can be expressed as:
A
′
= (a
n−1
a
n−1
. . . a
n−1
a
n−2
. . . a
2
a
1
a
0
)
2
m bits
and its value is given by:
A
′
= −2
m−1
a
n−1
+
m−2
∑
i=0
2
i
a
j
, where j =
i if i ∈ [0, n − 2]
n − 1 if i ≥ n − 1
By splitting the summation, we have:
A
′
= −2
m−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+
m−2
∑
i=n−1
2
i
a
n−1
= −2
m−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+ a
n−1
·
m−2
∑
i=n−1
2
i
= −2
m−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+ a
n−1
·
2
n−1
2
m−2−(n−1)+1
− 1
2 − 1
= −2
m−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+ a
n−1
·
2
m−1
− 2
n−1
=
−2
m−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+
2
m−1
a
n−1
− 2
n−1
a
n−1
= −2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
= A
Page 3 of 7
Page 3 of 7
We can conclude that the value of A
′
is the same as the value of A, therefore, sign-extension is valid.
Q.E.D.
Proof of negation: Recall that the negation of a number A is given by taking its 2’s complement, i.e. apply bitwise NOT to the
number, then add 1 to the result.
Consider a number B of n bits, which is given by (a
n−1
a
n−2
. . . a
2
a
1
a
0
)
2
+ 1. Then, the value of B is given by:
B = −2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+ 1
Also recall that for any bit a
i
, we have a
i
= 1 − a
i
.
Now, consider A + B, we have:
A + B = −2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
− 2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
+ 1
= −2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
− 2
n−1
(1 − a
n−1
) +
n−2
∑
i=0
2
i
(1 − a
i
) + 1
= −2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
− 2
n−1
+ 2
n−1
a
n−1
+
n−2
∑
i=0
2
i
−
n−2
∑
i=0
2
i
a
i
+ 1
=
−2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
− 2
n−1
+
2
n−1
a
n−1
+
n−2
∑
i=0
2
i
−
n−2
∑
i=0
2
i
a
i
+ 1
= −2
n−1
+
2
0
·
2
n−2−0+1
− 1
2 − 1
+ 1
= −2
n−1
+ 2
n−1
− 1 + 1
A + B = 0
Therefore, B = −A
We can conclude that the negation of a number A is indeed valid, since it gives the negative of the number, i.e., −A.
Q.E.D.
Now, we can verify the multiplication procedure in the lecture notes.
Proof of multiplication procedure:
First, sign-extension is performed on the multiplicand and multiplier to ensure that they are both of the same bit length, which
is proven to be valid above.
Now consider the multiplication of two n-bit 2’s complement numbers A and B, where A is the multiplicand and B is the
multiplier. We have:
A × B =
−2
n−1
a
n−1
+
n−2
∑
i=0
2
i
a
i
×
−2
n−1
b
n−1
+
n−2
∑
j=0
2
j
b
j
Case 1: A, B ≥ 0 (i.e., a
n−1
= b
n−1
= 0), our desired expression of the product is:
A × B =
n−2
∑
i=0
2
i
a
i
×
n−2
∑
j=0
2
j
b
j
(3)
Consider the procedure given by the lecture notes, ∀b
j
∈ B = 1, A is shifted to the left by j bits, which is equivalent to A × 2
j
,
and then added to the product. Therefore,
A × B =
n−2
∑
i=0
2
i
a
i
× 2
0
× b
0
+
n−2
∑
i=0
2
i
a
i
× 2
1
× b
1
+ ··· +
n−2
∑
i=0
2
i
a
i
× 2
n−1
× b
n−1
=
n−2
∑
i=0
2
i
a
i
·
2
0
b
0
+ 2
1
b
1
+ ··· + 2
n−1
b
n−1
=
n−2
∑
i=0
2
i
a
i
·
n−2
∑
j=0
2
j
b
j
+ 2
n−1
b
n−1
= A × B (since b
n−1
= 0)
Page 4 of 7
Page 4 of 7
Therefore, the multiplication procedure holds for two non-negative numbers.
Case 2: A ≥ 0, B < 0 (i.e., a
n−1
= 0, b
n−1
= 1), our desired expression of the product is:
A × B =
n−2
∑
i=0
2
i
a
i
×
−2
n−1
+
n−2
∑
j=0
2
j
b
j
(4)
The procedure states:
1. For each j ∈ [0, n − 2] where b
j
= 1, shift A to the left by j bits, which is equivalent to A × 2
j
.
2. Sum all terms given by step 1, which gives
∑
n−2
j=0
A × 2
j
× b
j
.
3. For the MSB of B, if b
n−1
= 1, then negate A and shift it to the left by (n−1) bits, which is equivalent to −A×2
n−1
×b
n−1
.
4. Add the results of step 2 and step 3 together, which gives:
A × B =
n−2
∑
j=0
A × 2
j
× b
j
− A × 2
n−1
× b
n−1
= A ×
−2
n−1
b
n−1
+
n−2
∑
j=0
2
j
b
j
=
n−2
∑
i=0
2
i
a
i
×
−2
n−1
+
n−2
∑
j=0
2
j
b
j
This matches our desired expression of the product, therefore, the multiplication procedure holds for A ≥ 0, B < 0.
Case 3: A < 0, B ≥ 0 (i.e., a
n−1
= 1, b
n−1
= 0). By considering the commutativity of multiplication, and the fact that A and B
are dummy variables, it is trivial to show that the multiplication procedure holds for this case as well.
Case 4: A < 0, B < 0 (i.e., a
n−1
= 1, b
n−1
= 1), our desired expression of the product is:
A × B =
−2
n−1
+
n−2
∑
i=0
2
i
a
i
×
−2
n−1
+
n−2
∑
j=0
2
j
b
j
(5)
The multiplication procedure for this case is identical to that of Case 2. Notice how A was not expressed in its full form (i.e.
−2
n−1
a
n−1
+
∑
n−2
i=0
2
i
a
i
) in the proof of Case 2. This implies that the calculation procedure is independent of the sign of A, and
therefore, the multiplication procedure holds for this case as well.
By now, we have shown that the multiplication procedure in the lecture notes holds for all cases of A and B, therefore, the
multiplication procedure is valid.
Q.E.D.
5. Any floating-point representation used in a computer can represent only certain real numbers exactly; all others must be approx-
imated. If A
′
is the stored value approximating the real value A, then the relative error, r, is expressed as
r =
A − A
′
A
Represent the decimal quantity +0.4 in the following floating-point format: base = 2; exponent: biased, 4 bits; significand, 7
bits. What is the relative error?
Solution: First, convert 0.4 to binary and normalise it:
0.4
10
= 0.0110011001100. . .
2
= 1. 1001100
significand
1100. . .
2
× 2
−2
Then, find the biased exponent:
Biased exponent = −2 + (2
3
− 1) = 5
1
0 = 0101
2
Page 5 of 7
Page 5 of 7
Therefore, the floating-point representation of 0.4 is:
A
′
= 0
sign
0101
exponent
1001100
significand
Now, we find the stored value of A
′
:
A
′
= (1 + 2
−1
+ 2
−4
+ 2
−5
) × 2
−2
= 2
−2
+ 2
−3
+ 2
−6
+ 2
−7
= 0.3984375
10
Now, we can calculate the relative error:
r =
A − A
′
A
=
0.4 − 0.3984375
0.4
=
0.0015625
0.4
= 0.00391 (corr. to 3 sig. figs.)
6. Consider a 40-bit floating point representation with a sign bit S, an exponent E (biased, 11 bits), and a significand f (28 bits).
The value is
V = (−1)
S
· 1. f · 2
E−1023
Here, E = 11. . . 111
2
and f = 00 . . . 000
2
do not have special meanings.
(a) Write down the largest positive number that can be represented.
Solution:
Largest value =
1 +
−1
∑
i=−28
2
i
· 2
2
11
−1−1023
=
1 + 2
−28
· (2
28
− 1)
· 2
1024
= (1 + 1 − 2
−28
) · 2
1024
= 2
1025
− 2
996
(b) Write down the smallest positive number that can be represented.
Solution:
Smallest value = 1 · 2
−1023
= 2
−1023
(c) Write down the bit pattern representing the value 15.3125.
Solution: First, convert 15.3125 to binary:
15.3125
10
= 1111.0101
2
= 1.1110101
2
× 2
3
Now, find the biased exponent:
Biased exponent = 3 + (2
11−1
− 1)
= 3 + 1023 = 1026
10
= 1000 0000 010
2
Page 6 of 7
Page 6 of 7
Combining the sign bit, exponent, and significand, we have:
Bit pattern = 0
sign
10000000010
exponent
111010100000 0000 0000 0000 0000
significand
= 0x402EA00000
(d) Write down the value represented by the bit pattern 0xC06F800000.
Solution: Convert the hexadecimal to binary:
0xC06F800000 = 1100 0000 0110 1111 1000 0000 0000 0000 0000 0000
= 1
sign
1000000110
exponent
111110000000 0000 0000 0000 0000
significand
Now, calculate the value:
V = (−1)
1
· 1.1111000
2
· 2
1030−1023
= −1.11111000
2
· 2
7
= −11111100
2
= −252
10
(e) If we assign 16 bits and 23 bits for exponent E and significand f , respectively. What is the largest positive number that can
be represented ? Discuss what is the relation between range and precision in floating point number representation?
Solution: Omitted.
Page 7 of 7
Page 7 of 7
See also
-
COMP2120-Assignment2
Assignment 2 of COMP2120 (24/25 Spring) with solutions.
-
COMP2120-Assignment3
Assignment 3 of COMP2120 (24/25 Spring) with solutions.
-
COMP2120-Assignment4
Assignment 4 of COMP2120 (24/25 Spring) with solutions.
-
COMP2120-Assignment5
Assignment 5 of COMP2120 (24/25 Spring) with solutions.
-
COMP2120-Cheatsheet
An A4 double-sided cheatsheet for the COMP2120 final exam.
-
COMP2120-Notes
Revision notes for COMP2120.