Exercise 1: Positional weights: reading a number in its base

In a base $b$ , the digit in position $k$ (counted from the right, starting at 0) has weight $b^{k}$ . Converting to decimal means weighing: multiply each digit by the weight of its position and add. The grid below recalls the eight weights of a byte.

a) Convert $10110110_2$ to decimal.
b) Convert $357_8$ to decimal.
c) Convert $2\text{F}5_{16}$ to decimal.
d) Convert $1101.101_2$ to decimal.
e) What is the largest unsigned integer that can be represented on $n$ bits? On 8 bits? On 16 bits?

Type your answers, the page tells you right or wrong 0/12

a)

10110110_2

in decimal

The least significant bit is 0, so the number is

b)

357_8

in decimal

The digit 7 is allowed in base 8 because the digits there run from

c)

Value of the digit

\text{F}

2\text{F}5_{16}

in decimal

d)

Value of the integer part

Value of the fractional part

1101.101_2

in decimal

e)

On

n

bits, the largest unsigned integer is

On 8 bits

On 16 bits

Show the solution

Answers

a) $182$
b) $239$
c) $757$
d) $13.625$
e) $2^{n}-1$ , that is $255$ on 8 bits and $65\,535$ on 16 bits

a)

Write the weights above the bits: $128, 64, 32, 16, 8, 4, 2, 1$ . The bits equal to 1 are those of weight $128$ , $32$ , $16$ , $4$ and $2$ . Sum: $128+32+16+4+2 = 182$ . Quick check: the most significant bit is 1, so the number is at least 128; the least significant bit is 0, so the number is even. 182 satisfies both.

b)

In base 8, the weights are $64, 8, 1$ . So $357_8 = 3(64) + 5(8) + 7(1) = 192 + 40 + 7 = 239$ . Check: the largest digit used is 7, which is allowed in base 8; an 8 or a 9 in an octal numeral would be a mistake in the question.

c)

In base 16, the weights are $256, 16, 1$ , and $\text{F}$ stands for 15. So $2\text{F}5_{16} = 2(256) + 15(16) + 5(1) = 512 + 240 + 5 = 757$ . The letters $\text{A}$ to $\text{F}$ stand for 10 to 15: that is the only thing to memorize in hexadecimal.

d)

The integer part $1101_2$ is $8+4+1 = 13$ . After the binary point, the weights become negative powers: $2^{-1} = 0.5$ , then $2^{-2} = 0.25$ , then $2^{-3} = 0.125$ . The bits are $1, 0, 1$ , so the fractional part is $0.5 + 0.125 = 0.625$ . Total: $13.625$ . The rule is the same on both sides of the point; only the sign of the exponent changes.

e)

On $n$ bits there are $2^{n}$ combinations, numbered from 0 to $2^{n}-1$ : the largest unsigned integer is therefore $2^{n}-1$ . On 8 bits, $255$ ; on 16 bits, $65\,535$ . Classic pitfall: answering $2^{n}$ and forgetting that zero uses up one combination.

Tick the exercises you have done or want to review: a free account, no password, keeps your ticks and your right answers from one visit to the next, tells you which chapter to tackle next and lets you ask for the exercise you are missing. Create your space, an email is enough.

Exercise 2: From decimal to other bases: repeated division

To convert a decimal integer to base $b$ , divide repeatedly by $b$ and read the remainders from BOTTOM TO TOP. For a fractional part, multiply repeatedly by $b$ and read the integer parts from TOP TO BOTTOM. The two algorithms look alike, but the reading direction is reversed: that is where half the marks are lost.

a) Convert 156 to binary by repeated division and check with the weights.
b) Convert 156 to octal, then to hexadecimal.
c) Convert $0.6875$ to binary.
d) Try to convert $0.1$ to binary. What happens?
e) Convert 1000 to hexadecimal.
f) What consequence does question d) have for a program that tests $0.1 + 0.2 = 0.3$ ?

Type your answers, the page tells you right or wrong 0/14

a)

156 in binary

Check with the weights

b)

156 in octal

156 in hexadecimal

Going from binary to hexadecimal is done in groups of

c)

The digits after the point

Check in decimal

d)

The binary expansion of

0.1

Length of the period, in bits

The reason is that the denominator 10 contains

e)

1000 in hexadecimal

Value of the digit

\text{E}

f)

Comparing two floats with strict equality

For money, work

Show the solution

Answers

a) $156 = 10011100_2$
b) $156 = 234_8 = 9\text{C}_{16}$
c) $0.6875 = 0.1011_2$
d) Repeating expansion: $0.1 = 0.0\overline{0011}_2$ , never terminating
e) $1000 = 3\text{E}8_{16}$
f) Never compare two floats with strict equality: test $|x-y| < \varepsilon$ , and count money in cents, with integers

a)

$156 = 2(78) + 0$ ; $78 = 2(39)+0$ ; $39 = 2(19)+1$ ; $19 = 2(9)+1$ ; $9 = 2(4)+1$ ; $4 = 2(2)+0$ ; $2 = 2(1)+0$ ; $1 = 2(0)+1$ . The remainders read from bottom to top give $10011100_2$ . Check with the weights: $128 + 16 + 8 + 4 = 156$ . The weight check is compulsory, because it catches the reading-direction error, which would give $00111001$ .

b)

Dividing by 8: $156 = 8(19)+4$ ; $19 = 8(2)+3$ ; $2 = 8(0)+2$ , hence $234_8$ . Check: $2(64)+3(8)+4 = 128+24+4 = 156$ . Dividing by 16: $156 = 16(9)+12$ ; $9 = 16(0)+9$ , and $12 = \text{C}$ , hence $9\text{C}_{16}$ . Check: $9(16)+12 = 156$ . Shortcut: $10011100_2$ splits into $1001\ 1100 = 9\text{C}$ , in groups of 4 bits starting from the right.

c)

$0.6875 \times 2 = 1.375$ , keep 1; $0.375 \times 2 = 0.75$ , keep 0; $0.75 \times 2 = 1.5$ , keep 1; $0.5 \times 2 = 1.0$ , keep 1, and nothing is left. Reading from top to bottom: $0.1011_2$ . Check: $0.5 + 0.125 + 0.0625 = 0.6875$ . The conversion stops here because $0.6875 = \dfrac{11}{16}$ has a denominator that is a power of 2.

d)

$0.1 \times 2 = 0.2$ ; $0.2 \times 2 = 0.4$ ; $0.4 \times 2 = 0.8$ ; $0.8 \times 2 = 1.6$ ; $0.6 \times 2 = 1.2$ ; $0.2 \times 2 = 0.4$ , and we are back to a state already seen. The expansion is repeating: $0.1 = 0.0\overline{0011}_2$ , with no end. The reason is arithmetic: $0.1 = \dfrac{1}{10}$ and 10 contains the factor 5, which is not a power of 2. A terminating decimal has a terminating binary expansion only if its reduced denominator is a power of 2.

e)

$1000 = 16(62)+8$ ; $62 = 16(3)+14$ , and $14 = \text{E}$ ; $3 = 16(0)+3$ . Hence $3\text{E}8_{16}$ . Check: $3(256) + 14(16) + 8 = 768 + 224 + 8 = 1000$ .

f)

The computer does not store $0.1$ but its infinite binary expansion rounded to the number of bits available. Three separate roundings occur, for $0.1$ , for $0.2$ and for $0.3$ , and nothing guarantees that the sum of the first two lands exactly on the third: in practice it does not. The conclusion fits in one rule: never compare two floating-point numbers with strict equality; test $|x-y| < \varepsilon$ instead. For money, work in cents with integers.

Exercise 3: Binary arithmetic: adding, subtracting, multiplying

The four operations are worked in binary exactly as in decimal, with a tiny addition table: $0+0=0$ , $0+1=1$ , $1+1=10$ , $1+1+1=11$ . The carry propagates the same way. Every result must be checked in decimal, without exception.

a) Set up and compute $10110_2 + 1101_2$ .
b) Set up and compute $110101_2 - 10110_2$ .
c) Set up and compute $1011_2 \times 101_2$ .
d) Carry out the division $1101_2 \div 10_2$ and give the quotient and the remainder.
e) What happens to a binary number when a 0 is appended on the right? Three zeros?

Show the solution

Answers

a) $100011_2 = 35$
b) $11111_2 = 31$
c) $110111_2 = 55$
d) Quotient $110_2 = 6$ , remainder $1$
e) One zero multiplies by 2, three zeros by $2^{3}=8$

a)

Align on the right: $10110$ is 22 and $1101$ is 13. Column by column from the right: $0+1 = 1$ ; $1+0 = 1$ ; $1+1 = 10$ , write 0 and carry 1; $0+1+1 = 10$ , write 0 and carry 1; $1+0+1 = 10$ , write 0 and carry 1; the carry remains, write 1. Result: $100011_2$ . Check: $32+2+1 = 35$ and $22+13 = 35$ .

b)

$110101$ is 53 and $10110$ is 22. Borrow as in decimal, a borrow being worth 2 in the column that receives it. From the right: $1-0 = 1$ ; $0-1$ forces a borrow, $10-1 = 1$ ; then $1-1$ minus the borrow forces another borrow, $11-1-1 = 1$ ; then $0-0$ minus the borrow borrows again, $10-0-1 = 1$ ; then $11-1-1 = 1$ once more; finally $1-0-1 = 0$ . Result: $11111_2$ . Check: $16+8+4+2+1 = 31$ and $53-22 = 31$ . A result of $11111$ is not suspicious: it is $2^{5}-1$ .

c)

$1011$ is 11 and $101$ is 5. Binary multiplication needs no table: each bit of the multiplier gives either a shifted copy of the multiplicand or a row of zeros. Here: $1011$ (bit of weight 1), $000000$ (bit of weight 2, zero), $101100$ (bit of weight 4, so shifted two positions). Sum: $1011 + 101100 = 110111_2$ . Check: $32+16+4+2+1 = 55$ and $11 \times 5 = 55$ .

d)

$1101$ is 13 and $10$ is 2. Dividing by $10_2$ means shifting one position to the right: the quotient is $110_2 = 6$ and the bit pushed out, here 1, is the remainder. Check: $2(6)+1 = 13$ . Dividing by a power of 2 is a shift, which explains why compilers replace $n/2$ with a shift when $n$ is an unsigned integer.

e)

Appending a 0 on the right shifts every bit one position to the left: each bit sees its weight doubled, so the number is multiplied by 2, not by 10. Three zeros multiply by $2^{3} = 8$ . It is the same mechanism as in decimal, where appending a zero multiplies by 10, that is, by the base. Remember: the factor is always the base, never ten.

Exercise 4: Two's complement: representing negative numbers

On $n$ bits, two's complement represents negative numbers without a separate sign: $-x$ is written as the pattern of $2^{n}-x$ . The most significant bit then acts as a sign indicator, and ordinary addition keeps working without any change to the circuit. The wheel below shows the 16 patterns of 4 bits: moving one step forward adds 1, and you go past the top with no break.

a) Write $-37$ in two's complement on 8 bits, showing both steps.
b) The pattern $10110100$ is read as a signed integer on 8 bits. What is its value?
c) What is the range of signed integers on 8 bits? Why is it not symmetric?
d) Compute $45 - 37$ using only an addition on 8 bits.
e) On 4 bits, what is the opposite of $-8$ ? What does this case reveal?

Type your answers, the page tells you right or wrong 0/13

a)

37 on 8 bits

Pattern of

-37

Its unsigned reading

The pattern in hexadecimal

b)

Unsigned reading of the pattern

Signed value

c)

Lower bound

Upper bound

The asymmetry comes from the fact that

d)

Result obtained

The carry out of position 8

e)

Opposite obtained

The case reveals that negation in two's complement

Show the solution

Answers

a) $-37 = 11011011_2 = \text{DB}_{16}$ , whose unsigned reading is $219 = 256-37$
b) $-76$
c) From $-128$ to $+127$ : zero takes up a pattern on the positive side
d) $45 + 11011011_2 = 8$ , the carry out being discarded
e) The opposite of $-8$ is $-8$ : negation is not total

a)

Step 1: write $37$ on 8 bits. $37 = 32+4+1$ , so $00100101$ . Step 2: invert all the bits, which gives $11011010$ , then add 1: $11011011$ . Numerical check: $11011011$ is $128+64+16+8+2+1 = 219$ , and $219 = 256 - 37$ , which is exactly the definition. In hexadecimal, $\text{DB}$ .

b)

The most significant bit is 1, so the number is negative. Two methods. Direct method: read the pattern as unsigned, $10110100 = 128+32+16+4 = 180$ , then subtract $256$ : $180 - 256 = -76$ . Complement method: invert, $01001011$ , add 1, $01001100 = 64+8+4 = 76$ , so the pattern stood for $-76$ . Both give the same result, and that is the check to do.

c)

From $-128$ to $+127$ . There are $256$ patterns; half of them, those whose most significant bit is 0, encode $0$ to $127$ ; the other half encode $-128$ to $-1$ . The asymmetry comes from zero taking up a slot on the positive side: $127$ patterns remain for the positive numbers and $128$ for the negative ones. That is precisely the advantage of two's complement over representations with a separate sign bit, which have two zeros and waste a pattern.

d)

$45 = 00101101$ . Add to it the representation of $-37$ , namely $11011011$ . Binary addition gives $1\,00001000$ over nine columns: the carry out of position 8 is simply discarded, and what remains is $00001000 = 8$ . Check: $45-37 = 8$ . That is the whole point of two's complement: the adder circuit also serves as the subtractor, give or take an inverter.

e)

On 4 bits, the range is $-8$ to $+7$ . The opposite of $-8$ should be $+8$ , which does not exist in the range. Applying the recipe: $-8$ is written $1000$ ; invert, $0111$ ; add 1, $1000$ : we land back on $-8$ . The case reveals that negation in two's complement is not total, and it is a real programming trap, where $\lvert x \rvert$ can return a negative number for the lower bound of the range.

Exercise 5: Base 8 lab: from expanded notation to long multiplication

Octal has only eight digits, from 0 to 7, and each position has a power of 8 as its weight. Everything you can do in base 10 can be redone in base 8 with a single change: you carry as soon as you reach 8, and you borrow 8, not 10. This exercise goes through the complete route of the binary arithmetic lab, in octal: writing a number in expanded notation, converting it both ways, adding, subtracting, multiplying, then closing the loop with a round trip checked in decimal. Every result is checked by going back through decimal, and that check is what makes the difference between a correct calculation and one that only looks correct.

Tables to know or to rebuild on scrap paper: $8^{1} = 8$ , $8^{2} = 64$ , $8^{3} = 512$ , $8^{4} = 4096$ , and the reciprocals $8^{-1} = 0.125$ , $8^{-2} = 0.015625$ .

a) Write $2471.35_8$ in expanded notation, as a sum of products of its digits by decreasing powers of 8, then give its decimal value.
b) Convert to decimal: $735_8$ , $1204_8$ , $61.4_8$ and $0.52_8$ .
c) Convert to octal: $200$ , $1000$ , $93.75$ and $0.1$ . What happens for the last one?
d) Set up and compute the octal additions $357_8 + 246_8$ , $1745_8 + 633_8 + 27_8$ and $12.56_8 + 7.37_8$ .
e) We work with 4 octal digits. Define the 7's complement and the 8's complement of a number, compute the 8's complement of $0325_8$ , then use it to carry out $2461_8 - 0325_8$ by an addition. What is the range of signed integers on 4 octal digits, and how do you recognize a negative number?
f) Set up and compute the octal subtractions $7042_8 - 3567_8$ and $10.2_8 - 3.75_8$ , showing the borrows.
g) Set up and compute the octal multiplications $53_8 \times 7_8$ , $124_8 \times 35_8$ and $6.4_8 \times 2.2_8$ .
h) Convert both numbers to octal, carry out the operation in octal, then go back to decimal to check: $345 + 219$ and $6.5 \times 3.25$ .
i) On Linux, the command chmod 755 sets the permissions of a file. Write $755_8$ in binary and explain what each octal digit represents. Why is octal the natural base for this encoding?

Type your answers, the page tells you right or wrong 0/32

a)

Weight of the leading digit 2

2471.35_8

in decimal

b)

735_8

1204_8

61.4_8

0.52_8

c)

200 in octal

1000 in octal

93.75

in octal

For

0.1

, the octal expansion

d)

357_8 + 246_8

1745_8 + 633_8 + 27_8

12.56_8 + 7.37_8

You write the remainder and carry 1 as soon as a column reaches

e)

7's complement of

0325_8

8's complement

2461_8 - 0325_8

Lower bound of the signed range

A number is negative when its leading digit is

f)

7042_8 - 3567_8

10.2_8 - 3.75_8

A borrow is worth

g)

53_8 \times 7_8

124_8 \times 35_8

6.4_8 \times 2.2_8

h)

345 in octal

219 in octal

The sum, in octal

6.5 \times 3.25

, in octal

i)

755_8

in binary

Each octal digit encodes

The three bits of a digit are, in order

Show the solution

Answers

a) $2\cdot 8^{3}+4\cdot 8^{2}+7\cdot 8+1+3\cdot 8^{-1}+5\cdot 8^{-2} = 1337.453125$
b) $477$ , $644$ , $49.5$ and $0.65625$
c) $310_8$ , $1750_8$ , $135.6_8$ ; $0.1 = 0.0\overline{6314}_8$ , repeating
d) $625_8$ , $2627_8$ and $22.15_8$
e) 8's complement of $0325_8$ : $7453_8$ ; $2461_8-0325_8 = 2134_8$ ; range $-2048$ to $2047$ , negative as soon as the leading digit reaches 4
f) $3253_8$ and $4.23_8$
g) $455_8$ , $4604_8$ and $16.5_8$
h) $531_8+333_8 = 1064_8 = 564$ ; $6.4_8 \times 3.2_8 = 25.1_8 = 21.125$
i) $755_8 = 111\ 101\ 101_2$ : three parties, three bits each, read, write, execute

a)

The radix point separates the positive positions from the negative ones. On the left, moving left from the point, the weights are $8^{0}, 8^{1}, 8^{2}, 8^{3}$ ; on the right, $8^{-1}$ then $8^{-2}$ . Hence $2471.35_8 = 2 \cdot 8^{3} + 4 \cdot 8^{2} + 7 \cdot 8^{1} + 1 \cdot 8^{0} + 3 \cdot 8^{-1} + 5 \cdot 8^{-2}$ . Value: $2(512) + 4(64) + 7(8) + 1 + \dfrac{3}{8} + \dfrac{5}{64} = 1024 + 256 + 56 + 1 + 0.375 + 0.078125 = 1337.453125$ . Expanded notation is not an exercise in style: it is the very definition of the base, and every conversion to decimal is just this calculation written faster.

b)

$735_8 = 7(64) + 3(8) + 5 = 448 + 24 + 5 = 477$ . $1204_8 = 1(512) + 2(64) + 0(8) + 4 = 512 + 128 + 4 = 644$ : the zero is weighed too; it holds a position even though it adds nothing. $61.4_8 = 6(8) + 1 + \dfrac{4}{8} = 49.5$ . $0.52_8 = \dfrac{5}{8} + \dfrac{2}{64} = 0.625 + 0.03125 = 0.65625$ . Classic pitfall: reading $0.52_8$ as fifty-two hundredths. In base 8, the second digit after the point is worth one sixty-fourth, not one hundredth.

c)

Integer part by repeated division by 8, remainders read from bottom to top. $200 = 8(25) + 0$ ; $25 = 8(3) + 1$ ; $3 = 8(0) + 3$ , hence $200 = 310_8$ ; check $3(64) + 1(8) = 200$ . $1000 = 8(125) + 0$ ; $125 = 8(15) + 5$ ; $15 = 8(1) + 7$ ; $1 = 8(0) + 1$ , hence $1000 = 1750_8$ ; check $512 + 7(64) + 5(8) = 512 + 448 + 40 = 1000$ . For $93.75$ , split it: $93 = 8(11) + 5$ ; $11 = 8(1) + 3$ ; $1 = 8(0) + 1$ , so $93 = 135_8$ ; then $0.75 \times 8 = 6.0$ , keep 6 and nothing is left, so $93.75 = 135.6_8$ . Check: $64 + 24 + 5 + 0.75 = 93.75$ . For $0.1$ : $0.1 \times 8 = 0.8$ , digit 0; $0.8 \times 8 = 6.4$ , digit 6; $0.4 \times 8 = 3.2$ , digit 3; $0.2 \times 8 = 1.6$ , digit 1; $0.6 \times 8 = 4.8$ , digit 4; $0.8 \times 8 = 6.4$ , and we are back to a state already seen. The expansion is repeating: $0.1 = 0.0\overline{6314}_8$ . No surprise: $0.1 = \dfrac{1}{10}$ and 10 contains the factor 5, which divides no power of 8. A terminating decimal has a terminating expansion in base 8 exactly when its reduced denominator is a power of 2, the same condition as in binary, because $8 = 2^{3}$ .

d)

Add column by column, and as soon as a column reaches 8, write the remainder and carry 1. First addition: ones $7 + 6 = 13 = 8 + 5$ , write 5 and carry 1; eights $5 + 4 + 1 = 10 = 8 + 2$ , write 2 and carry 1; $3 + 2 + 1 = 6$ . Result $625_8$ . Decimal check: $357_8 = 239$ , $246_8 = 166$ , sum 405, and $625_8 = 6(64) + 2(8) + 5 = 405$ . Second addition, with three terms aligned on the right: ones $5 + 3 + 7 = 15 = 8 + 7$ , write 7 and carry 1; $4 + 3 + 2 + 1 = 10$ , write 2, carry 1; $7 + 6 + 0 + 1 = 14$ , write 6, carry 1; $1 + 0 + 0 + 1 = 2$ . Result $2627_8$ . Check: $997 + 411 + 23 = 1431$ and $2627_8 = 2(512) + 6(64) + 2(8) + 7 = 1431$ . Third addition, with radix points, lining up the points: $6 + 7 = 13$ , write 5, carry 1; $5 + 3 + 1 = 9$ , write 1, carry 1; $2 + 7 + 1 = 10$ , write 2, carry 1; $1 + 0 + 1 = 2$ . Result $22.15_8$ . Check: $10.71875 + 7.484375 = 18.203125$ and $22.15_8 = 18 + \dfrac{1}{8} + \dfrac{5}{64} = 18.203125$ . The most frequent error is carrying at 10 out of habit: $7 + 6$ is then written down as 13, and the result is off by 8 in that column.

e)

The 7's complement of a 4-digit octal number is obtained by replacing each digit $d$ with $7 - d$ , with no carry at all; it is the analogue of inverting the bits. The 8's complement is the 7's complement plus 1, and it equals $8^{4} - x = 4096 - x$ : it is the analogue of two's complement. For $0325_8$ : 7's complement, digit by digit, $7-0, 7-3, 7-2, 7-5$ , that is $7452_8$ ; plus 1, $7453_8$ . Check: $0325_8 = 3(64) + 2(8) + 5 = 213$ , $4096 - 213 = 3883$ , and $7453_8 = 7(512) + 4(64) + 5(8) + 3 = 3584 + 256 + 40 + 3 = 3883$ . Subtraction by addition: $2461_8 + 7453_8$ . Ones $1 + 3 = 4$ ; $6 + 5 = 11 = 8 + 3$ , write 3, carry 1; $4 + 4 + 1 = 9$ , write 1, carry 1; $2 + 7 + 1 = 10$ , write 2, carry 1. We get $12134_8$ on five digits; the carry that comes out on the left is discarded, since we work with 4 digits, and what remains is $2134_8$ . Check: $2461_8 = 1329$ , $1329 - 213 = 1116$ , and $2134_8 = 1024 + 64 + 24 + 4 = 1116$ . Why it works: adding $4096 - x$ and then discarding $4096$ is exactly the same as subtracting $x$ . Signed range on 4 octal digits, that is, 12 bits: from $-2^{11} = -2048$ to $2^{11} - 1 = 2047$ , that is, from $4000_8$ (read as $-2048$ ) to $3777_8$ . A number is negative when its leading digit is 4 or more: the upper half of the patterns represents the negative numbers, exactly like the most significant bit in binary, since the first octal digit contains that bit. So $7453_8$ , read as a signed integer, is $3883 - 4096 = -213$ .

f)

First subtraction, $7042_8 - 3567_8$ . Ones: $2 < 7$ , borrow one eight, $2 + 8 - 7 = 3$ , and the eights digit goes from 4 to 3. Eights: $3 < 6$ , borrow, $3 + 8 - 6 = 5$ , and the 64s digit must go down by 1; it is 0, so first borrow from the 512s, which go from 7 to 6, and the 64s become $8 - 1 = 7$ . 64s column: $7 - 5 = 2$ . 512s column: $6 - 3 = 3$ . Result $3253_8$ . Check: $7042_8 = 3618$ , $3567_8 = 1911$ , difference 1707, and $3253_8 = 3(512) + 2(64) + 5(8) + 3 = 1707$ . Second subtraction, $10.20_8 - 3.75_8$ , padding $10.2$ with a zero to line up: sixty-fourths $0 < 5$ , borrow, $0 + 8 - 5 = 3$ , and the eighths go from 2 to 1; eighths $1 < 7$ , borrow, $1 + 8 - 7 = 2$ , and the ones, which are 0, borrow from the eights, $1 \to 0$ , to become $8 - 1 = 7$ ; ones $7 - 3 = 4$ ; eights $0 - 0 = 0$ . Result $4.23_8$ . Check: $8.25 - 3.953125 = 4.296875$ and $4.23_8 = 4 + \dfrac{2}{8} + \dfrac{3}{64} = 4.296875$ . The trap of a cascading borrow through a zero is the same as in decimal; the only novelty is that a borrow is worth 8.

g)

Long multiplication, with the 8 times table in mind: each partial product is reduced modulo 8 and the carry can exceed 1. $53_8 \times 7_8$ : $3 \times 7 = 21 = 2(8) + 5$ , write 5 and carry 2; $5 \times 7 + 2 = 37 = 4(8) + 5$ , write 5 then 4. Result $455_8$ ; check $43 \times 7 = 301 = 4(64) + 5(8) + 5$ . $124_8 \times 35_8$ : by 5, $4 \times 5 = 20 = 2(8) + 4$ , write 4, carry 2; $2 \times 5 + 2 = 12 = 8 + 4$ , write 4, carry 1; $1 \times 5 + 1 = 6$ , row $644_8$ . By 3, shifted one position: $4 \times 3 = 12$ , write 4, carry 1; $2 \times 3 + 1 = 7$ ; $1 \times 3 = 3$ , row $3740_8$ . Sum $644_8 + 3740_8$ : $4 + 0 = 4$ ; $4 + 4 = 8$ , write 0, carry 1; $6 + 7 + 1 = 14$ , write 6, carry 1; $3 + 1 = 4$ . Result $4604_8$ ; check $84 \times 29 = 2436 = 4(512) + 6(64) + 4$ . $6.4_8 \times 2.2_8$ : multiply without the points, $64_8 \times 22_8$ , and then put back as many digits after the point as there were in total in the factors, here $1 + 1 = 2$ . $64_8 \times 2 = 150_8$ (since $4 \times 2 = 8$ , write 0, carry 1; $6 \times 2 + 1 = 13$ , write 5, carry 1); the row for the other 2, shifted, gives $1500_8$ ; sum $1650_8$ ; with two fractional digits, $16.50_8 = 16.5_8$ . Check: $6.5 \times 2.25 = 14.625$ and $16.5_8 = 14 + \dfrac{5}{8} = 14.625$ . The rule for placing the point is the same as in decimal, because it depends only on the number of positions, not on the base.

h)

$345 = 8(43) + 1$ , $43 = 8(5) + 3$ , $5 = 8(0) + 5$ , so $345 = 531_8$ ; $219 = 8(27) + 3$ , $27 = 8(3) + 3$ , so $219 = 333_8$ . Addition: $1 + 3 = 4$ ; $3 + 3 = 6$ ; $5 + 3 = 8$ , write 0, carry 1, and write 1 in front. Result $1064_8$ , and back: $512 + 6(8) + 4 = 564 = 345 + 219$ . The check closes the loop. Then $6.5 = 6.4_8$ since $0.5 = \dfrac{4}{8}$ , and $3.25 = 3.2_8$ since $0.25 = \dfrac{2}{8}$ . Compute $64_8 \times 32_8$ : by 2, $150_8$ ; by 3, shifted: $4 \times 3 = 12 = 8 + 4$ , write 4 and carry 1; $6 \times 3 + 1 = 19 = 2(8) + 3$ , write 3 then 2, which gives $234_8$ , then $2340_8$ ; sum $150_8 + 2340_8 = 2510_8$ ; two fractional digits: $25.10_8 = 25.1_8$ . Back: $2(8) + 5 + \dfrac{1}{8} = 21.125$ , and $6.5 \times 3.25 = 21.125$ . Both numbers have terminating octal expansions because their fractional parts, $\dfrac{1}{2}$ and $\dfrac{1}{4}$ , have a power of 2 as denominator.

i)

Each octal digit is exactly 3 bits: $7 = 111_2$ , $5 = 101_2$ , so $755_8 = 111\ 101\ 101_2$ . The three digits encode the permissions of three parties, the owner, the group and others, and the three bits of each digit are, in order, read, write, execute. $7 = 111$ : the owner can do everything; $5 = 101$ : the group and others can read and execute, not write. Base 8 is natural here because permissions come in groups of 3 bits and an octal digit is precisely a group of 3 bits: the split needs no calculation, it is simply read off. A 644, for comparison, gives $110\ 100\ 100$ : the owner reads and writes, the others only read. That is why the binary to octal conversion works in groups of 3, and why octal survives wherever bits are handled in triples.

Exercise 6: Base 16 lab: from expanded notation to long multiplication

Hexadecimal has sixteen digits: 0 to 9, then A, B, C, D, E, F for 10 to 15. Each position has a power of 16 as its weight; you carry as soon as you reach 16, and you borrow 16. It is the base of everything displayed in computing, memory addresses, colours, the bytes of a file, because one hexadecimal digit is exactly 4 bits and a byte fits in two digits. This exercise goes through the complete route of the lab again in base 16: expanded notation, conversions both ways, addition, complement, subtraction, multiplication, and a checked round trip.

Tables to keep at hand: $16^{2} = 256$ , $16^{3} = 4096$ , $16^{4} = 65536$ , $16^{-1} = 0.0625$ , $16^{-2} = 0.00390625$ ; the product of two hexadecimal digits is rebuilt in decimal and then reduced modulo 16.

a) Write $3\text{AF}.\text{C}8_{16}$ in expanded notation, then give its decimal value.
b) Convert to decimal: $2\text{B}_{16}$ , $7\text{D}0_{16}$ , $\text{FFFF}_{16}$ , $\text{A}.4_{16}$ and $0.18_{16}$ .
c) Convert to hexadecimal: $255$ , $4096$ , $3000$ , $0.8125$ and $0.1$ . What do you notice for the last one?
d) Set up and compute the hexadecimal additions $3\text{C}_{16} + 2\text{F}_{16}$ , $\text{A}9\text{F}_{16} + 7\text{E}5_{16}$ and $1\text{F}.8_{16} + \text{C}.\text{A}_{16}$ .
e) We work with 4 hexadecimal digits. Define the 15's complement and the 16's complement, compute the 16's complement of $02\text{D}4_{16}$ , then use it to carry out $1\text{A}7\text{B}_{16} - 02\text{D}4_{16}$ by an addition. How is this related to two's complement on 16 bits, and how do you recognize a negative number?
f) Set up and compute the hexadecimal subtractions $\text{B}05_{16} - 4\text{C}9_{16}$ and $10.4_{16} - 7.\text{C}_{16}$ , showing the borrows.
g) Set up and compute the hexadecimal multiplications $2\text{A}_{16} \times \text{B}_{16}$ , $1\text{F}_{16} \times 3\text{C}_{16}$ and $4.8_{16} \times 2.4_{16}$ .
h) Convert both numbers to hexadecimal, carry out the operation in hexadecimal, then go back to decimal to check: $1000 - 255$ and $12.75 \times 2.5$ .

Type your answers, the page tells you right or wrong 0/33

a)

Value of the digit

\text{A}

3\text{AF}.\text{C}8_{16}

in decimal

b)

2\text{B}_{16}

7\text{D}0_{16}

\text{FFFF}_{16}

\text{A}.4_{16}

0.18_{16}

c)

255 in hexadecimal

4096 in hexadecimal

3000 in hexadecimal

0.8125

in hexadecimal

For

0.1

, the hexadecimal expansion

d)

3\text{C}_{16} + 2\text{F}_{16}

\text{A}9\text{F}_{16} + 7\text{E}5_{16}

Its check in decimal

1\text{F}.8_{16} + \text{C}.\text{A}_{16}

e)

15's complement of

02\text{D}4_{16}

16's complement

Its check in decimal

1\text{A}7\text{B}_{16} - 02\text{D}4_{16}

, in decimal

A number is negative when its leading digit is

f)

\text{B}05_{16} - 4\text{C}9_{16}

Its check in decimal

10.4_{16} - 7.\text{C}_{16}

A cascading borrow through a zero leaves behind it

g)

2\text{A}_{16} \times \text{B}_{16}

1\text{F}_{16} \times 3\text{C}_{16}

, in decimal

4.8_{16} \times 2.4_{16}

In base 16, a multiplication carry can go up to

h)

3\text{E}8_{16} - 0\text{FF}_{16}

Decimal check of the subtraction

12.75 \times 2.5

, in hexadecimal

Decimal check of the product

Show the solution

Answers

a) $3\cdot 16^{2}+10\cdot 16+15+12\cdot 16^{-1}+8\cdot 16^{-2} = 943.78125$
b) $43$ , $2000$ , $65\,535$ , $10.25$ and $0.09375$
c) $\text{FF}_{16}$ , $1000_{16}$ , $\text{BB}8_{16}$ , $0.\text{D}_{16}$ ; $0.1 = 0.1\overline{9}_{16}$ , repeating
d) $6\text{B}_{16}$ , $1284_{16}$ and $2\text{C}.2_{16}$
e) 16's complement of $02\text{D}4_{16}$ : $\text{FD}2\text{C}_{16}$ ; the difference is $17\text{A}7_{16} = 6055$ ; range $-32\,768$ to $32\,767$ , negative as soon as the leading digit reaches 8
f) $63\text{C}_{16}$ and $8.8_{16}$
g) $1\text{CE}_{16}$ , $744_{16}$ and $\text{A}.2_{16}$
h) $2\text{E}9_{16} = 745$ and $1\text{F}.\text{E}_{16} = 31.875$

a)

The weights, moving left from the radix point, are $16^{0}, 16^{1}, 16^{2}$ ; moving right, $16^{-1}, 16^{-2}$ . Hence $3\text{AF}.\text{C}8_{16} = 3 \cdot 16^{2} + 10 \cdot 16^{1} + 15 \cdot 16^{0} + 12 \cdot 16^{-1} + 8 \cdot 16^{-2}$ , replacing A, F and C by their values 10, 15 and 12. Value: $3(256) + 10(16) + 15 + \dfrac{12}{16} + \dfrac{8}{256} = 768 + 160 + 15 + 0.75 + 0.03125 = 943.78125$ . The only new difficulty compared with octal is remembering that A is 10, not 1, and that F is 15, not 6.

b)

$2\text{B}_{16} = 2(16) + 11 = 43$ . $7\text{D}0_{16} = 7(256) + 13(16) + 0 = 1792 + 208 = 2000$ . $\text{FFFF}_{16} = 15(4096) + 15(256) + 15(16) + 15 = 61440 + 3840 + 240 + 15 = 65535$ , and faster: four digits all at their maximum are worth $16^{4} - 1 = 65535$ , the largest integer on 16 bits. $\text{A}.4_{16} = 10 + \dfrac{4}{16} = 10.25$ . $0.18_{16} = \dfrac{1}{16} + \dfrac{8}{256} = 0.0625 + 0.03125 = 0.09375$ . Same pitfall as in octal: $0.18_{16}$ has nothing to do with eighteen hundredths; the second digit is worth one two-hundred-fifty-sixth.

c)

$255 = 16(15) + 15$ , $15 = 16(0) + 15$ , two remainders of 15, that is $\text{FF}_{16}$ ; check $15(16) + 15 = 255$ , the full byte. $4096 = 16^{3}$ , so $1000_{16}$ : a 1 followed by three zeros, like $1000 = 10^{3}$ in decimal. $3000 = 16(187) + 8$ ; $187 = 16(11) + 11$ ; $11 = 16(0) + 11$ ; remainders read from bottom to top, $11, 11, 8$ , that is $\text{BB}8_{16}$ ; check $11(256) + 11(16) + 8 = 2816 + 176 + 8 = 3000$ . $0.8125 \times 16 = 13.0$ , digit D, and nothing is left: $0.8125 = 0.\text{D}_{16}$ , which is consistent with $0.8125 = \dfrac{13}{16}$ . For $0.1$ : $0.1 \times 16 = 1.6$ , digit 1; $0.6 \times 16 = 9.6$ , digit 9; $0.6 \times 16 = 9.6$ , digit 9, and so on. So $0.1 = 0.1\overline{9}_{16}$ , repeating. It is the same impossibility as in binary and in octal, for the same reason: $16 = 2^{4}$ , so a decimal has a terminating expansion in base 16 if and only if it has one in base 2, that is, if its reduced denominator is a power of 2. One tenth, with its factor 5, will never qualify. You can in fact read the binary $0.0\overline{0011}_2$ through the hexadecimal: $1 = 0001$ , $9 = 1001$ , and the concatenation $0001\ 1001\ 1001\dots$ does give back the pattern $0011$ repeated, shifted by one position.

d)

$3\text{C}_{16} + 2\text{F}_{16}$ : ones $\text{C} + \text{F} = 12 + 15 = 27 = 16 + 11$ , write B and carry 1; $3 + 2 + 1 = 6$ . Result $6\text{B}_{16}$ ; check $60 + 47 = 107 = 6(16) + 11$ . $\text{A}9\text{F}_{16} + 7\text{E}5_{16}$ : $\text{F} + 5 = 20 = 16 + 4$ , write 4, carry 1; $9 + \text{E} + 1 = 9 + 14 + 1 = 24 = 16 + 8$ , write 8, carry 1; $\text{A} + 7 + 1 = 18 = 16 + 2$ , write 2, carry 1, written in front. Result $1284_{16}$ ; check $2719 + 2021 = 4740 = 4096 + 2(256) + 8(16) + 4$ . $1\text{F}.8_{16} + \text{C}.\text{A}_{16}$ , radix points lined up: $8 + \text{A} = 18 = 16 + 2$ , write 2, carry 1; $\text{F} + \text{C} + 1 = 15 + 12 + 1 = 28 = 16 + 12$ , write C, carry 1; $1 + 0 + 1 = 2$ . Result $2\text{C}.2_{16}$ ; check $31.5 + 12.625 = 44.125 = 2(16) + 12 + \dfrac{2}{16}$ . The safe method for each column: add in decimal, subtract 16 if you go past 15, then translate the remainder into a hexadecimal digit. The pitfall is writing 27 or 11 instead of B.

e)

The 15's complement of a 4-digit hexadecimal number replaces each digit $d$ with $15 - d$ : it is bit inversion, since $15 - d$ inverts the 4 bits of $d$ . The 16's complement adds 1 to the result and equals $16^{4} - x = 65536 - x$ . For $02\text{D}4_{16}$ : 15's complement, $\text{F}-0, \text{F}-2, \text{F}-\text{D}, \text{F}-4$ , that is $\text{FD}2\text{B}_{16}$ ; plus 1, $\text{FD}2\text{C}_{16}$ . Check: $02\text{D}4_{16} = 2(256) + 13(16) + 4 = 724$ , $65536 - 724 = 64812$ , and $\text{FD}2\text{C}_{16} = 15(4096) + 13(256) + 2(16) + 12 = 61440 + 3328 + 32 + 12 = 64812$ . Subtraction by addition: $1\text{A}7\text{B}_{16} + \text{FD}2\text{C}_{16}$ . $\text{B} + \text{C} = 23 = 16 + 7$ , write 7, carry 1; $7 + 2 + 1 = 10$ , write A; $\text{A} + \text{D} = 23$ , write 7, carry 1; $1 + \text{F} + 1 = 17 = 16 + 1$ , write 1, carry 1. We get $117\text{A}7_{16}$ ; discard the carry out, and $17\text{A}7_{16}$ remains. Check: $1\text{A}7\text{B}_{16} = 6779$ , $6779 - 724 = 6055$ , and $17\text{A}7_{16} = 4096 + 7(256) + 10(16) + 7 = 6055$ . Link with two's complement: 4 hexadecimal digits are 16 bits, and $\text{FD}2\text{C}_{16}$ is exactly the pattern of $-724$ in two's complement on 16 bits; the 16's complement is not another operation, it is two's complement written in base 16, four bits at a time. Signed range: from $8000_{16} = -32768$ to $7\text{FFF}_{16} = 32767$ . A number is negative when its leading digit is 8 or more, because that digit contains the most significant bit; so $\text{FD}2\text{C}_{16}$ read as signed is $64812 - 65536 = -724$ .

f)

$\text{B}05_{16} - 4\text{C}9_{16}$ . Ones: $5 < 9$ , borrow 16, $5 + 16 - 9 = 12$ , write C, and the sixteens digit must go down by 1; it is 0, so borrow from the 256s, B becomes A, and the sixteens become $16 - 1 = 15 = \text{F}$ . Sixteens: $\text{F} - \text{C} = 15 - 12 = 3$ . 256s column: $\text{A} - 4 = 6$ . Result $63\text{C}_{16}$ . Check: $\text{B}05_{16} = 2821$ , $4\text{C}9_{16} = 1225$ , difference 1596, and $63\text{C}_{16} = 6(256) + 3(16) + 12 = 1596$ . $10.4_{16} - 7.\text{C}_{16}$ : sixteenths $4 < \text{C}$ , borrow, $4 + 16 - 12 = 8$ , and the ones, which are 0, borrow from the 1 on the left to become F; ones $\text{F} - 7 = 8$ ; the leading 1 has become 0. Result $8.8_{16}$ . Check: $16.25 - 7.75 = 8.5 = 8 + \dfrac{8}{16}$ . A borrow is worth 16, and a cascading borrow through a zero leaves an F behind it, as it leaves a 9 in decimal and a 7 in octal.

g)

$2\text{A}_{16} \times \text{B}_{16}$ : $\text{A} \times \text{B} = 10 \times 11 = 110 = 6(16) + 14$ , write E and carry 6; $2 \times \text{B} + 6 = 28 = 16 + 12$ , write C, carry 1, written in front. Result $1\text{CE}_{16}$ ; check $42 \times 11 = 462 = 256 + 12(16) + 14$ . Note the carry of 6: in base 16, a multiplication carry can go up to 14, which throws off anyone who only ever carries 1 out of habit. $1\text{F}_{16} \times 3\text{C}_{16}$ : by C, $\text{F} \times \text{C} = 180 = 11(16) + 4$ , write 4, carry 11; $1 \times \text{C} + 11 = 23 = 16 + 7$ , write 7, carry 1, row $174_{16}$ . By 3, shifted: $\text{F} \times 3 = 45 = 2(16) + 13$ , write D, carry 2; $1 \times 3 + 2 = 5$ , row $5\text{D}0_{16}$ . Sum $174_{16} + 5\text{D}0_{16}$ : $4 + 0 = 4$ ; $7 + \text{D} = 20 = 16 + 4$ , write 4, carry 1; $1 + 5 + 1 = 7$ . Result $744_{16}$ ; check $31 \times 60 = 1860 = 7(256) + 4(16) + 4$ . $4.8_{16} \times 2.4_{16}$ : compute $48_{16} \times 24_{16}$ , then put back two fractional digits. By 4: $8 \times 4 = 32 = 2(16) + 0$ , write 0, carry 2; $4 \times 4 + 2 = 18 = 16 + 2$ , write 2, carry 1, row $120_{16}$ . By 2, shifted: $8 \times 2 = 16$ , write 0, carry 1; $4 \times 2 + 1 = 9$ , row $900_{16}$ . Sum $\text{A}20_{16}$ , so $\text{A}.20_{16} = \text{A}.2_{16}$ . Check: $4.5 \times 2.25 = 10.125 = 10 + \dfrac{2}{16}$ .

h)

$1000 = 16(62) + 8$ , $62 = 16(3) + 14$ , $3 = 16(0) + 3$ , so $1000 = 3\text{E}8_{16}$ ; and $255 = \text{FF}_{16}$ , written $0\text{FF}_{16}$ to line up. Subtraction $3\text{E}8_{16} - 0\text{FF}_{16}$ : ones $8 < \text{F}$ , borrow, $8 + 16 - 15 = 9$ , and E becomes D; sixteens $\text{D} < \text{F}$ , borrow, $13 + 16 - 15 = 14 = \text{E}$ , and 3 becomes 2; $2 - 0 = 2$ . Result $2\text{E}9_{16}$ ; back: $2(256) + 14(16) + 9 = 512 + 224 + 9 = 745 = 1000 - 255$ . Then $12.75 = \text{C}.\text{C}_{16}$ , since $12 = \text{C}$ and $0.75 = \dfrac{12}{16}$ , and $2.5 = 2.8_{16}$ since $0.5 = \dfrac{8}{16}$ . Compute $\text{CC}_{16} \times 28_{16}$ . By 8: $\text{C} \times 8 = 96 = 6(16) + 0$ , write 0, carry 6; $\text{C} \times 8 + 6 = 102 = 6(16) + 6$ , write 6, carry 6, row $660_{16}$ . By 2, shifted: $\text{C} \times 2 = 24 = 16 + 8$ , write 8, carry 1; $\text{C} \times 2 + 1 = 25 = 16 + 9$ , write 9, carry 1, row $1980_{16}$ . Sum $660_{16} + 1980_{16}$ : $0 + 0 = 0$ ; $6 + 8 = 14 = \text{E}$ ; $6 + 9 = 15 = \text{F}$ ; $0 + 1 = 1$ . Result $1\text{FE}0_{16}$ , and with two fractional digits $1\text{F}.\text{E}0_{16} = 1\text{F}.\text{E}_{16}$ . Back: $16 + 15 + \dfrac{14}{16} = 31.875$ , and $12.75 \times 2.5 = 31.875$ . The loop is closed: when the round trip comes out right, the conversion and the long calculation are validated in one go; when it does not, the error is in one of the two, and it is quickly located by rechecking the two conversions first.

Exercise 7: Overflow: when the result no longer fits

An overflow occurs when the exact result of an operation falls outside the representable range. The machine does not stop: it returns the truncated pattern, which is wrong. You therefore have to be able to DETECT the situation, and not confuse the carry out, which concerns unsigned arithmetic, with overflow, which concerns signed arithmetic.

a) With 8-bit signed integers, compute $100 + 50$ . What does the machine return?
b) State the rule that detects a signed overflow from the signs of the operands and of the result.
c) With 8-bit unsigned integers, compute $200 + 100$ . What does the machine return?
d) Does $(-100) + (-50)$ overflow with 8-bit signed integers?
e) Can $100 + (-50)$ overflow with 8-bit signed integers? Justify without computing.

Type your answers, the page tells you right or wrong 0/8

a)

Value returned by the machine

Two positives give a negative: there is therefore

b)

A signed overflow occurs exactly when

c)

Value kept

What happens here is

d)

Is there an overflow?

Value returned

e)

Can it overflow?

Show the solution

Answers

a) The machine returns $-106$ : overflow, since $150 > 127$
b) Signed overflow if and only if both operands have the same sign and the result the opposite sign
c) The machine keeps $44$ and raises the carry out: unsigned carry, not signed overflow
d) Yes: $-150 < -128$ , the pattern obtained is $106$
e) No: opposite signs, the sum lies between $-50$ and $100$

a)

$100 = 01100100$ and $50 = 00110010$ . The addition gives $10010110$ . The most significant bit is 1: read as signed, the result is $150 - 256 = -106$ . Adding two positive numbers gives a negative one: that is an overflow. The exact value, $150$ , exceeds the ceiling $127$ , and the two's complement wheel shows why: moving 50 steps forward from 100, you cross the boundary between $127$ and $-128$ .

b)

Rule: a signed overflow occurs exactly when both operands have the SAME sign and the result has the opposite sign. Two numbers of opposite signs can never overflow, since their sum lies between the two. The processor implements this rule with an XOR between the carry into and the carry out of the most significant bit, which gives the same verdict.

c)

$200 + 100 = 300$ , but the unsigned ceiling on 8 bits is $255$ . The machine keeps $300 - 256 = 44$ and raises the carry out. The pattern kept is $00101100$ . Here there is no signed overflow in the sense of rule b): there is an unsigned carry. The two flags, carry and overflow, are computed at the same time by the processor, and it is the program that chooses which one to look at, according to the declared type of the variables.

d)

$-100$ and $-50$ have the same sign, and their exact sum $-150$ is below the floor $-128$ : there is an overflow. The pattern obtained corresponds to $-150 + 256 = 106$ , a positive number. The rule is confirmed: two negatives giving a positive.

e)

No. The operands have opposite signs, so their sum lies between $-50$ and $100$ , that is, strictly inside the range $[-128, 127]$ . This is a bounding argument, not a calculation: the sum of a positive and a negative number always lies between the two, so inside the range as soon as both operands are. A signed addition overflow can therefore always be detected by looking at the signs alone.

Exercise 8: Hexadecimal, masks and bitwise operations

Hexadecimal is not a base for computing: it is a compact way of writing binary. One hexadecimal digit is exactly 4 bits, one octal digit exactly 3 bits, which makes the conversions immediate by grouping, starting from the RIGHT. Bitwise operations, for their part, act on each position independently, with no carry at all.

a) Convert $1011111011101111_2$ to hexadecimal, then to octal.
b) $\text{AND}$ denotes the bitwise conjunction. What is $\text{B6}_{16}$ AND $\text{0F}_{16}$ ? And $\text{B6}_{16}$ AND $\text{F0}_{16}$ ?
c) Which operation forces bit 2 to 1 without touching the others? Which operation inverts it?
d) What is $1011_2$ shifted 3 positions to the left, then 2 positions to the right?
e) How can you test whether an integer is even with a single bitwise operation?
f) Why is the binary to octal conversion done in groups of 3 and not 4?

Type your answers, the page tells you right or wrong 0/16

a)

In hexadecimal

In octal

Decimal value

b)

\text{B6}_{16}

AND

0\text{F}_{16}

, in decimal

\text{B6}_{16}

AND

\text{F}0_{16}

, in decimal

An AND is always used to

c)

Forcing a bit to 1 without touching the others takes

Inverting that single bit takes

The mask, in decimal

d)

After a shift of 3 positions to the left

Then 2 positions to the right

The right shift is

e)

The evenness test reads

f)

Bits encoded by one octal digit

Bits encoded by one hexadecimal digit

Grouping works only if

Show the solution

Answers

a) $\text{BEEF}_{16} = 137357_8 = 48\,879$
b) $6$ and $\text{B}0_{16} = 176$ , whose sum gives back $182$
c) OR with $00000100$ to set, XOR with the same mask to toggle
d) $88$ then $22$
e) $n$ AND $1$ equals 0
f) Because $8 = 2^{3}$ : one octal digit is 3 bits, one hexadecimal digit 4

a)

Groups of 4 from the right: $1011\ 1110\ 1110\ 1111$ , that is $\text{B}, \text{E}, \text{E}, \text{F}$ : the number is written $\text{BEEF}_{16}$ . Check with the weights: $11(4096) + 14(256) + 14(16) + 15 = 45056 + 3584 + 224 + 15 = 48\,879$ . For octal, split the SAME binary again into groups of 3 from the right, padding on the left with a zero: $1\ 011\ 111\ 011\ 101\ 111$ , that is $137357_8$ . Check: $1(32768)+3(4096)+7(512)+3(64)+5(8)+7 = 48\,879$ . The grouping must start from the right; starting from the left is the most frequent error, and it shifts everything.

b)

$\text{B6}_{16} = 10110110_2 = 182$ . The mask $\text{0F} = 00001111$ keeps the 4 low-order bits and clears the others: the result is $00000110 = 6$ . The mask $\text{F0} = 11110000$ keeps the 4 high-order bits: the result is $10110000 = \text{B0}_{16} = 176$ . Check: $176 + 6 = 182$ ; the two halves rebuild the byte. An AND is always used to CLEAR bits.

c)

To force a bit to 1 without touching the others, OR it with a mask that has a 1 only in that position: here $\text{OR}\ 00000100$ . To invert that single bit, XOR it with the same mask, since $x \oplus 1 = \overline{x}$ and $x \oplus 0 = x$ . Three roles to remember: AND to clear, OR to set, XOR to toggle.

d)

$1011_2 = 11$ . Shifted 3 positions to the left: $1011000_2 = 88$ , that is $11 \times 2^{3}$ . That result shifted 2 positions to the right gives $10110_2 = 22$ , that is $88 \div 4$ . Careful: the right shift is an INTEGER division; the bits pushed out are lost, and $11$ shifted right by 1 position gives 5, not $5.5$ .

e)

An integer is even if and only if its bit 0 is 0, so the test reads: $n$ AND $1$ equals 0. One operation, against a division and a remainder for the test $n \bmod 2 = 0$ . It is the classic optimization, and it remains correct for negative integers in two's complement, since bit 0 keeps the same meaning there.

f)

Because a base- $b$ digit encodes exactly $\log_{2}b$ bits: $16 = 2^{4}$ gives 4 bits per hexadecimal digit, and $8 = 2^{3}$ gives 3 bits per octal digit. The grouping works only because the base is a power of 2; there is no similar grouping toward base 10, and that is why the binary to decimal conversion requires divisions or weights.

Exercise 9: Computer codes: ASCII, BCD, Gray and parity

A code is not a base: it is a convention that associates a bit pattern with a symbol or a digit. The same pattern $01000001$ means 65, or the letter A, or anything else, depending on the code applied. A bit pattern never carries its interpretation with it.

a) The letter A is 65 in ASCII. Write its pattern on 8 bits. The letter a is 97: what is the difference, and where does it show in the pattern?
b) Write 47 in BCD, then in pure binary. Compare the number of bits used.
c) The 3-bit Gray code is $000, 001, 011, 010, 110, 111, 101, 100$ . What property does it satisfy? Give the conversion rule from binary.
d) The 7-bit word $1011011$ is protected by an even parity bit. Which bit is added?
e) Does this code detect two simultaneous errors? Does it correct an error?

Type your answers, the page tells you right or wrong 0/15

a)

Difference between a and A

Position of the bit that changes

Going from an uppercase letter to its lowercase amounts to

b)

47 in BCD, number of bits

47 in pure binary

Number of bits in pure binary

Per nibble, BCD uses only

c)

Two consecutive Gray codes differ in

Bit

k

of the Gray code is

Gray code of 5, on 3 bits

d)

Number of 1s in the word

Parity bit added

Number of 1s in the transmitted word

e)

Two simultaneous errors

This code

Show the solution

Answers

a) A is $01000001$ , a is $01100001$ : only bit 5 changes, hence the gap of $32$
b) $0100\ 0111$ on 8 bits in BCD, $101111_2$ on 6 bits in pure binary
c) Only one bit changes between two consecutive codes; Gray bit $k$ is the XOR of binary bits $k$ and $k+1$
d) The parity bit is 1, the transmitted word is $10110111$
e) It detects a single error, not two errors, and corrects nothing

a)

$65 = 64 + 1$ , so A is written $01000001$ . And $97 = 64+32+1$ , so a is written $01100001$ . The difference is $32 = 2^{5}$ : the only bit that changes is bit 5. Going from an uppercase letter to its lowercase therefore amounts to forcing that bit to 1, and the reverse to clearing it. That is why converting to lowercase was historically coded as a simple OR with $00100000$ , with no table at all.

b)

In BCD, each decimal digit is encoded separately on 4 bits: the 4 becomes $0100$ , the 7 becomes $0111$ , so $47$ is written $0100\ 0111$ , that is, 8 bits. In pure binary, $47 = 32+8+4+2+1 = 101111_2$ , that is, 6 bits. BCD wastes space, since it uses only 10 of the 16 patterns of each nibble, but it makes display immediate, digit by digit. It is still found in displays, clocks and some financial formats, where exact conversion to decimal matters more than compactness.

c)

Two consecutive codes differ in only one bit, including between the last and the first. The conversion rule: bit $k$ of the Gray code is the XOR of bit $k$ and bit $k+1$ of the binary numeral. For example $5 = 101_2$ gives a first bit $1 \oplus 0 = 1$ , a second $0 \oplus 1 = 1$ , a third $1 \oplus 0 = 1$ , that is $111$ , which is indeed the sixth word of the list. The benefit is physical: on a position sensor, if two bits changed at the same time, a slight timing offset between them would produce an absurd intermediate value. With Gray code, only one bit is ever in transition.

d)

The word $1011011$ contains five 1s, an odd number. For the total to be even, the parity bit is 1, and the transmitted word becomes $10110111$ , which contains six 1s. Check on reception: count the 1s again; if there is an odd number of them, an error has occurred.

e)

It detects any error affecting an ODD number of bits, so a single error, but not two simultaneous errors: two flipped bits leave the parity unchanged and the error goes unnoticed. And it corrects nothing, since it only signals that an error exists, without saying where. Correcting requires more redundancy, for example a Hamming code, which adds several check bits placed so as to point to the position of the faulty bit.

Exercise 10: Five statements to correct

Each of the following five statements is FALSE. Say why and give the correct statement.

1) “In binary, appending a 0 on the right multiplies the number by 10.”
2) “On 8 bits, two's complement represents the integers from $-127$ to $+127$ .”
3) “The pattern $11111111$ is $-1$ .”
4) “A byte is written with four hexadecimal digits.”
5) “With enough bits, $0.1$ can eventually be written exactly in binary.”

Type your answers, the page tells you right or wrong 0/11

1)

Appending a zero on the right multiplies by

101_2 = 5

becomes, in decimal

2)

Lower bound

Upper bound

3)

Read as unsigned on 8 bits

Read as signed on 8 bits

The value of a pattern depends on

4)

Hexadecimal digits in a byte

Bits described by 4 hexadecimal digits

5)

0.1

in binary

A number has a terminating binary expansion if

Show the solution

Answers

1) FALSE: the base is 2, so the factor is 2. $101_2 = 5$ becomes $1010_2 = 10$
2) FALSE: the range is $[-128, 127]$ , that is $[-2^{n-1}, 2^{n-1}-1]$
3) FALSE: $-1$ as signed, $255$ as unsigned. The type is set by the program, not by the memory
4) FALSE: a byte is written with TWO hexadecimal digits, from $00$ to $\text{FF}$
5) FALSE: $0.1$ has no terminating binary expansion; the factor 5 in the denominator rules it out

1)

FALSE. Appending a zero on the right multiplies by the BASE, and the base is 2. Counterexample: $101_2 = 5$ becomes $1010_2 = 10$ , twice as much, not ten times as much. Correct statement: in base $b$ , appending a zero on the right multiplies by $b$ ; in binary, by 2, and $k$ zeros multiply by $2^{k}$ .

2)

FALSE. The range is $-128$ to $+127$ : it is asymmetric, because zero uses up a pattern on the positive side. Counting the patterns is enough to see it: $128$ patterns for the negative numbers, $128$ for zero and the positive numbers. Correct statement: on $n$ bits, two's complement covers $[-2^{n-1},\ 2^{n-1}-1]$ .

3)

FALSE. The pattern does not carry its interpretation: $11111111$ is $-1$ if it is read as a signed integer on 8 bits, but $255$ if it is read as an unsigned integer. It means something else again if it is read as a character or as part of a floating-point number. Correct statement: the value of a pattern depends on the declared type, and it is the program, not the memory, that sets that type.

4)

FALSE. One hexadecimal digit is 4 bits, so an 8-bit byte is written with exactly TWO hexadecimal digits, from $00$ to $\text{FF}$ . Four hexadecimal digits describe 16 bits, that is, two bytes. Correct statement: $n$ bits require $n/4$ hexadecimal digits, rounded up.

5)

FALSE. $0.1 = \dfrac{1}{10}$ and $10 = 2 \times 5$ contains the factor 5. A number has a terminating binary expansion only if its reduced denominator is a power of 2: the expansion of $0.1$ is repeating, and adding bits only pushes the rounding further back. Correct statement: $0.1$ has no terminating binary expansion, whatever the number of bits; that is why $0.1+0.2$ is not exactly $0.3$ on a computer.

Exercise 11: Problem: colours, memory and the size of an image

A screen colour is written in hexadecimal in the form #RRGGBB: two hexadecimal digits per component, red, green and blue, each component taking up one byte. A raster image stores one such colour per pixel.

a) Break down the colour $\#3\text{C}78\text{D}8$ into its three decimal components.
b) How many distinct colours does this encoding allow?
c) An address bus has 16 lines. How many bytes can be addressed?
d) How much space does an image of 800 by 600 pixels in 24-bit colour take, in bytes and then in mebibytes?
e) Is the same 16-line bus enough to address this image? How many lines would be needed?
f) Is the colour $\#\text{FFFFFF}$ white or black? And $\#000000$ ?

Type your answers, the page tells you right or wrong 0/15

a)

Red

Green

Blue

b)

Number of colours

The safest calculation is to

c)

Number of addresses

In kibibytes

Each extra line

d)

Number of pixels

Size in bytes

Size in mebibytes

e)

The 16-line bus

Number of lines needed

f)

The colour

\#\text{FFFFFF}

is

The synthesis of a screen is

Show the solution

Answers

a) $(60, 120, 216)$
b) $256^{3} = 2^{24} = 16\,777\,216$ colours
c) $2^{16} = 65\,536$ bytes, that is 64 KiB
d) $480\,000$ pixels, $1\,440\,000$ bytes, about $1.37$ MiB
e) No: 21 lines are needed, since $2^{20} < 1\,440\,000 \le 2^{21}$
f) $\#\text{FFFFFF}$ is white, $\#000000$ black: the synthesis of a screen is additive

a)

Split into three pairs: $3\text{C}$ , $78$ , $\text{D}8$ . Red: $3(16)+12 = 60$ . Green: $7(16)+8 = 120$ . Blue: $13(16)+8 = 216$ . The colour is therefore $(60, 120, 216)$ , a strong blue, as the dominant blue component confirms.

b)

Each component takes $256$ values, and the three are independent: $256^{3} = 2^{24} = 16\,777\,216$ colours. That is the famous 16 million colours, and the calculation is done by adding the bits, $8+8+8 = 24$ , rather than multiplying 256 three times.

c)

With 16 address lines, you form $2^{16} = 65\,536$ distinct addresses, that is, 64 kibibytes if each address designates one byte. Each extra line doubles the addressable capacity: it is a doubling, not an addition, and that is why moving from 32-bit to 64-bit addressing did not double the limit but put it out of reach.

d)

The image has $800 \times 600 = 480\,000$ pixels, at 3 bytes each: $1\,440\,000$ bytes. Since a mebibyte is $2^{20} = 1\,048\,576$ bytes, that makes $1\,440\,000 / 1\,048\,576 \approx 1.37$ MiB. Order-of-magnitude check: half a million pixels at 3 bytes is about one and a half million bytes, so a little more than one mebibyte.

e)

No: $65\,536$ addresses are not enough for $1\,440\,000$ bytes. You need $n$ such that $2^{n} \ge 1\,440\,000$ . Since $2^{20} = 1\,048\,576$ is too small and $2^{21} = 2\,097\,152$ is enough, 21 address lines are needed. The reasoning brackets the value between two powers of 2, never by division.

f)

$\#\text{FFFFFF}$ sets all three components to their maximum, $255$ : it is white, the sum of the three lights. $\#000000$ sets them to zero: no light emitted, it is black. The synthesis is additive because a screen emits light; on paper, ink absorbs and the logic is reversed, which explains why white there is the absence of ink.

Exercise 12: Problem: the IEEE 754 standard in single precision

A single-precision floating-point number takes up 32 bits: 1 sign bit, 8 exponent bits with a bias of $127$ , and 23 mantissa bits. The number is written $(-1)^{s} \times 1.m \times 2^{e-127}$ : the leading 1 is not stored, since it is always there after normalization.

a) Write $6.25$ in binary.
b) Normalize this numeral in the form $1.m \times 2^{k}$ .
c) Compute the biased exponent, then give the 32 bits of $-6.25$ .
d) Write these 32 bits in hexadecimal.
e) Up to which integer are all the integers represented exactly in single precision?
f) Are two neighbouring floating-point numbers separated by a constant gap?

Type your answers, the page tells you right or wrong 0/14

a)

6.25

in binary

Check in decimal

b)

Exponent

k

The normalized mantissa is written

Decimal value of

1.1001_2

c)

Stored exponent

Sign bit

Pattern read as an unsigned integer

d)

The 32 bits in hexadecimal

Grouping by 4 bits is legitimate here because

e)

Significant bits

All integers exact up to

f)

The gap between two consecutive floats

Adding a small number to a very large one

Show the solution

Answers

a) $6.25 = 110.01_2$
b) $1.1001_2 \times 2^{2}$
c) Stored exponent $129$ , sign 1: $1\ 10000001\ 10010000000000000000000$
d) $\text{C0C80000}_{16}$
e) $2^{24} = 16\,777\,216$
f) No: the gap is $2^{-23}\times 2^{k}$ , it grows with the order of magnitude

a)

Integer part: $6 = 110_2$ . Fractional part: $0.25 = 2^{-2}$ , so $01$ after the binary point. Hence $6.25 = 110.01_2$ . Check: $4 + 2 + 0.25 = 6.25$ .

b)

Move the binary point two positions to the left, which is compensated by a factor $2^{2}$ : $110.01_2 = 1.1001_2 \times 2^{2}$ . Check: $1.1001_2 = 1 + 0.5 + 0.0625 = 1.5625$ , and $1.5625 \times 4 = 6.25$ . Normalization requires exactly one 1 before the point, which makes the representation unique and makes it possible not to store that 1.

c)

The actual exponent is $2$ , so the stored exponent is $2 + 127 = 129 = 10000001_2$ . The sign is negative, so $s = 1$ . The mantissa is the part after the point, $1001$ , padded with zeros to 23 bits. The 32 bits are: $1\ 10000001\ 10010000000000000000000$ . Numerical check: read as an unsigned integer, this pattern is $2^{31} + 129 \times 2^{23} + 2^{22} + 2^{19} = 3\,234\,332\,672$ .

d)

Group the 32 bits in fours from the left, which is legitimate since 32 is a multiple of 4: $1100\ 0000\ 1100\ 1000\ 0000\ 0000\ 0000\ 0000$ , that is $\text{C0C80000}_{16}$ . Check: $\text{C0C80000}$ is indeed $3\,234\,332\,672$ , the same value as in the previous question.

e)

The mantissa has 23 stored bits plus the implicit 1, that is, 24 significant bits. All the integers up to $2^{24} = 16\,777\,216$ are therefore written exactly. Beyond that, only every other integer can be represented, then one in four, and so on. That is why a seconds counter or an identifier stored in single precision goes wrong from about 17 million on, without the slightest error message.

f)

No. The gap between two consecutive floats is $2^{-23} \times 2^{k}$ : it depends on the exponent, and so on the order of magnitude of the number. Near 1, the gap is about $10^{-7}$ ; near $10^{6}$ , it is about $0.06$ . Floats are tightly packed near zero and more and more spread out as you move away from it, exactly like the marks on a logarithmic scale. Practical consequence: adding a small number to a large one may change nothing at all, which makes a sum depend on the order of its terms.

Corrected exercises: number systems in computing (201-N11)

Course recap

Part A: the basics (/70)

Exercise 1: Positional weights: reading a number in its base

Exercise 2: From decimal to other bases: repeated division

Exercise 3: Binary arithmetic: adding, subtracting, multiplying

Exercise 4: Two's complement: representing negative numbers

Exercise 5: Base 8 lab: from expanded notation to long multiplication

Exercise 6: Base 16 lab: from expanded notation to long multiplication

Exercise 7: Overflow: when the result no longer fits

Part B: problems and reasoning (/50)

Exercise 8: Hexadecimal, masks and bitwise operations

Exercise 9: Computer codes: ASCII, BCD, Gray and parity

Exercise 10: Five statements to correct

Exercise 11: Problem: colours, memory and the size of an image

Exercise 12: Problem: the IEEE 754 standard in single precision

See also

Looking for a computer science math tutor in Montreal?