Homework: Exercise 2

Theory: How to Approach These

Positional notation (2.1): digit $\times$ base $^{\text{position}}$ , positions counted from the right starting at 0.
Base conversion (2.1): hex to binary is 4 bits per digit; a fraction is converted by repeated multiplication by 2, taking the integer parts in order.
Complement arithmetic (2.2, 2.3): 4 bits cover $-7$ to $+7$ in one’s complement and $-8$ to $+7$ in two’s complement. Subtract by adding the negative; one’s complement needs the end-around carry.
Overflow (2.3): two numbers of the same sign give a result of the opposite sign.
Floating point (2.4, 2.5): normalize to $1.f \times 2^e$ , add the bias to $e$ , pad or truncate the fraction to the field size. To multiply: multiply significands, add exponents, renormalize.

Jump to: Q1 · Q2 · Q3 · Q4 · Q5

Homework Solutions

Exercise Q1

[Positional numbering system] Write each number in positional (expanded) form:

a. $526$

b. $10110$

Part	Detail
Asks	Show each digit times its place value, then add them up.
Needs	Value $= \sum d_i \cdot b^i$ . The base: 526 is decimal (base 10), 10110 is binary (base 2).
Look at	The digits 5 and 6 in 526 mean it cannot be binary; 10110 uses only 0 and 1, so it is read as binary.
If it changes	Another base: same recipe, only $b$ changes.

Show solution ↓

Solution

How to solve

Number the digits from the right, starting at position 0.
Write each digit times $b^{\text{position}}$ .
Add the terms.

Position	4	3	2	1	0
Digit
Place value

Sample answer

(a) Base 10:

526_{10} = 5 \times 10^2 + 2 \times 10^1 + 6 \times 10^0 = 500 + 20 + 6 = 526

(b) Base 2:

10110_2 = 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 16 + 0 + 4 + 2 + 0

So $10110_2 = 22_{10}$ ✓ (check: $22 = 16 + 4 + 2$ ).

Exercise Q2

[Converting numbers into different bases]

a. $2AD_{16}$ to base 2

b. $5.15$ to base 2 (limited to 8 fractional bits)

Part	Detail
Asks	(a) hex to binary. (b) a decimal fraction to binary, stopping at 8 places after the point.
Needs	(a) one hex digit = 4 bits. (b) integer part by its binary form; fraction by repeated $\times 2$ .
Look at	“8 fractional bits”: stop after 8 multiplications, the rest is dropped.
If it changes	More or fewer bits: do more or fewer multiplications.

Show solution ↓

Solution

How to solve

(a) Replace each hex digit by its 4-bit group, then drop leading zeros.
(b) Convert the integer part, then multiply the fraction by 2 eight times, writing down each integer part (0 or 1) and keeping the rest.

Step	Number $\times 2$	Bit	Fraction kept
1
2

Sample answer

(a) $2 = 0010$ , $A = 1010$ , $D = 1101$ :

2AD_{16} = 0010\ 1010\ 1101_2 = 1010101101_2

Check: $2 \cdot 256 + 10 \cdot 16 + 13 = 685$ and $512 + 128 + 32 + 8 + 4 + 1 = 685$ ✓.

(b) Integer part: $5 = 101_2$ . Fraction part $0.15$ :

Step	Number $\times 2$	Bit	Fraction kept
1	$0.15 \times 2 = 0.30$	0	0.30
2	$0.30 \times 2 = 0.60$	0	0.60
3	$0.60 \times 2 = 1.20$	1	0.20
4	$0.20 \times 2 = 0.40$	0	0.40
5	$0.40 \times 2 = 0.80$	0	0.80
6	$0.80 \times 2 = 1.60$	1	0.60
7	$0.60 \times 2 = 1.20$	1	0.20
8	$0.20 \times 2 = 0.40$	0	0.40

Reading the bits top to bottom: $0.15 \approx 0.00100110_2$ . So $5.15 \approx 101.00100110_2$ .

Check: $0.00100110_2 = \tfrac18 + \tfrac1{64} + \tfrac1{128} = 0.1484375$ , close to $0.15$ . The fraction never ends (it repeats $0011$ ), which is why the result is only approximate.

Exercise Q3

[Integer number representation and arithmetic] For $-3 - 5$ , show the operation using four-bit binary of:

a. One’s complement

b. Two’s complement

Note: indicate if the result is overflow or not.

Part	Detail
Asks	Compute $-3 - 5$ in 4 bits in two systems and say whether each result fits.
Needs	$-3 - 5 = (-3) + (-5)$ . One’s complement: flip bits, end-around carry. Two’s complement: flip and add 1, discard the carry out.
Look at	Same-sign operands (both negative): overflow if the result sign is positive. The true answer is $-8$ .
If it changes	Other numbers: same steps. Check the true answer against the range of the system.

Show solution ↓

Solution

How to solve

Write $+3 = 0011$ and $+5 = 0101$ .
Form $-3$ and $-5$ in the required system.
Add the two patterns.
One’s complement only: add any carry out back into the right end (end-around carry).
Two’s complement only: discard the carry out.
Compare the signs of the operands and the result, and check the range.

	$-3$	$-5$	Sum	Result	Overflow?
One’s complement
Two’s complement

Sample answer

(a) One’s complement (range $-7$ to $+7$ ): $-3 = 1100$ , $-5 = 1010$ .

1100 + 1010 = 1\,0110 \quad\Rightarrow\quad 0110 + 1 = 0111

The carry out of the MSB is added back (end-around carry), giving $0111 = +7$ . Two negative numbers produced a positive result, and the true answer $-8$ is outside $-7$ to $+7$ , so overflow.

(b) Two’s complement (range $-8$ to $+7$ ): $-3 = 1101$ , $-5 = 1011$ .

1101 + 1011 = 1\,1000 \quad\Rightarrow\quad \text{discard the carry: } 1000

$1000 = -8$ , which is the correct answer. Both operands are negative and the result is negative, and the carry into the MSB (1) equals the carry out (1), so no overflow ✓.

Watch out: the carry out of the MSB is not the overflow test in two’s complement. Compare the signs, or compare carry-in with carry-out of the MSB.

Exercise Q4

[Floating point and operation]

a. Convert $64.125$ into binary floating point of the format 14-bit simple model with bias 16. Is there a truncation?

b. Multiply $10.101 \times 2^{-3}$ and $1.01 \times 2^{7}$ and represent the result using IEEE 754 single precision format.

Part	Detail
Asks	(a) Encode 64.125 in the 14-bit model and say if bits are lost. (b) Multiply two binary floating-point numbers and encode the product in IEEE 754 single.
Needs	14-bit model: sign 1, exponent 5 (bias 16), significand 8 bits after the implicit 1. IEEE single: sign 1, exponent 8 (bias 127), fraction 23 bits after the implicit 1.
Look at	(a) count the fraction bits after normalizing: more than 8 means truncation. (b) the product may need renormalizing.
If it changes	Another number or format: change the bias and the field widths, keep the steps.

Show solution ↓

Solution

How to solve

Convert to binary and normalize to $1.f \times 2^e$ .
Stored exponent $= e + \text{bias}$ .
Fit the fraction into the field: pad with zeros, or truncate if too long.
(b) Multiply the significands, add the exponents, then renormalize.

Sign	Exponent	Fraction

Sample answer

(a) $64 = 1000000_2$ and $0.125 = 0.001_2$ , so

64.125 = 1000000.001_2 = 1.000000001_2 \times 2^6

Sign: $0$ .
Exponent: $6 + 16 = 22 = 10110$ .
Fraction: $000000001$ has 9 bits, but the field holds 8, so the last bit is cut: $00000000$ .

130sign (1 bit)

12–810110exponent (5 bits)

7–000000000significand (8 bits)

The code is 0 10110 00000000. Yes, there is a truncation: the final 1 (worth $2^{-9}$ of the significand) is lost, so the stored value is $64$ , not $64.125$ .

(b) Multiply the significands and add the exponents:

10.101_2 \times 1.01_2 = 11.01001_2, \qquad 2^{-3} \times 2^{7} = 2^{4}

Check in decimal: $2.625 \times 1.25 = 3.28125 = 11.01001_2$ ✓.

Renormalize: $11.01001 \times 2^4 = 1.101001 \times 2^5$ (this equals $52.5$ ).

Sign: $0$ .
Exponent: $5 + 127 = 132 = 10000100$ .
Fraction: $101001$ padded with zeros to 23 bits: $10100100000000000000000$ .

310sign (1 bit)

30–2310000100exponent (8 bits)

22–010100100000000000000000fraction (23 bits)

The result is 0 10000100 10100100000000000000000 $= 42520000_{16}$ . No truncation is needed because the fraction has only 6 significant bits.

Exercise Q5

[Challenge case] Suppose a computer uses 4-bit one’s complement representation. Ignoring overflows, what value will be stored in the variable $j$ after the following pseudocode routine terminates?

-2 → j    // Store -2 in j.
 6 → k    // Store 6 in k.

while k ≠ -6
    j = j - 1    // Don't forget to operate in one's complement representation
    k = k + 1
end while

Hint: $j$ starts with $-2 = 1101$ in one’s complement and $k = 6 = 0110$ . Use one’s complement arithmetic and ignore any overflow effect. The test $k \ne -6$ means $k \ne 1001$ .

Part	Detail
Asks	Run the loop by hand with 4-bit one’s complement numbers and give the final $j$ .
Needs	$-6 = 1001$ , $-1 = 1110$ , $+1 = 0001$ . Add with end-around carry. $0111 + 1 = 1000 = -7$ (the count wraps).
Look at	$k$ counts up from 6, so it passes through 7, wraps to $-7$ , then reaches $-6$ . Stop when $k = 1001$ .
If it changes	Another start or stop value: trace again row by row.

Show solution ↓

Solution

How to solve

Write the start values: $j = 1101$ , $k = 0110$ .
Check the test $k \ne 1001$ . If true, run the body.
$j - 1 = j + 1110$ with end-around carry. $k + 1 = k + 0001$ .
Repeat until $k = 1001$ .

Pass	$k$ before	Test $k \ne 1001$	$j$ after	$k$ after
1
2

Sample answer

Pass	$k$ before	Test $k \ne 1001$	$j$ after	$k$ after
1	$0110$ ( $+6$ )	true	$1101 + 1110 = 1\,1011 \to 1100$ ( $-3$ )	$0111$ ( $+7$ )
2	$0111$ ( $+7$ )	true	$1100 + 1110 = 1\,1010 \to 1011$ ( $-4$ )	$1000$ ( $-7$ )
3	$1000$ ( $-7$ )	true	$1011 + 1110 = 1\,1001 \to 1010$ ( $-5$ )	$1001$ ( $-6$ )
4	$1001$ ( $-6$ )	false: loop ends

The loop body runs 3 times, so $j$ goes down by 3 from $-2$ : $j = 1010_2 = -5$ ✓.

Watch out: $0111 + 0001 = 1000$ is $-7$ in one’s complement, not $+8$ . The wrap-around is what lets $k$ reach $-6$ by counting up.