Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: number systems in computing (201-N11)

Number systems are the most mechanical chapter of the course, and yet the one where tests lose the most marks: the algorithms are simple, but each one has a reading DIRECTION, and reversing it gives a clean, wrong result.

This sheet gathers those reading directions and the edge cases: remainders from bottom to top, groups from the right, the $1$ added after the inversion, and the one sign that reveals an overflow. It is written for CEGEP students in computer science programs taking 201-N11; once it is read, the corrected exercise set on the same chapter puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

A bit pattern means nothing on its own: it is the INTERPRETATION chosen, unsigned, two's complement or IEEE 754, that decides the value it represents.

This chapter is part of 201-N11, Mathematics for Computer Science

The essentials

Positional weights, in every base

• In base $b$ , the digit in position $k$ has weight $b^{k}$ ; after the radix point, the weights are $b^{-1}$ , $b^{-2}$ , and so on.
• A byte carries the weights $128$ , $64$ , $32$ , $16$ , $8$ , $4$ , $2$ , $1$ , from the most significant bit to the least significant one.
• One hexadecimal digit is exactly $4$ bits, one octal digit $3$ bits: the bits are ALWAYS grouped starting from the right.
• Unsigned, on $n$ bits: from $0$ to $2^{n}-1$ . In two's complement: from $-2^{n-1}$ to $2^{n-1}-1$ .

The pattern

01100100

adds up the weights of the positions holding a

1

64+32+4=100

, and the leftmost position is the one that weighs the most.

Knowing the eight weights of a byte spares you any conversion calculation below $256$ : reading them directly is faster and safer than repeated division.

Converting, one way and the other

• Decimal to base $b$ , integer part: repeated division by $b$ , remainders read from BOTTOM TO TOP.
• Fractional part: repeated multiplication by $b$ , integer parts read from TOP TO BOTTOM.
• Base $b$ to decimal: sum of the digits multiplied by their weights, with no division at all.
• A terminating decimal has a terminating binary expansion only if its reduced denominator is a power of $2$ .

0.375

: multiply by

2

and keep the integer part, read from TOP to BOTTOM:

0.011_{2}

. Stop when the fractional part drops to

0

The two reading directions are opposite, and that is the only thing to memorize: integers from bottom to top, fractions from top to bottom.

Two's complement

• Two's complement of $x$ : invert all the bits, THEN add $1$ . The resulting pattern equals $2^{n}-x$ .
• The most significant bit acts as the sign bit: $1$ means negative.
• The range is not symmetric: on $8$ bits, from $-128$ to $127$ , because zero takes up a slot on the positive side.
• Signed overflow: both operands have the SAME sign and the result has the opposite sign. Two operands of opposite signs never overflow.

The same four-bit pattern reads

12

as unsigned and

-4

in two's complement: it is the convention chosen, not the pattern, that gives the value.

Two's complement exists so that a single addition serves for positive and negative numbers alike. That is why subtraction is just the addition of the complement.

Bitwise operations, shifts and IEEE 754

• AND to CLEAR bits, OR to SET them, EXCLUSIVE OR to TOGGLE them.
• Shifting left by $k$ positions: multiplication by $2^{k}$ . Shifting right: integer division by $2^{k}$ .
• IEEE 754 single precision: $1$ sign bit, $8$ exponent bits with a bias of $127$ , $23$ mantissa bits with an implicit $1$ .
• Integers are exact up to $2^{24}$ , that is $16\,777\,216$ ; beyond that, two neighbouring integers share the same representation.

The

32

bits of a single-precision float: one for the sign, eight for the biased exponent, twenty-three for the mantissa, whose leading

1

is not stored.

An equality test between two floats is almost always a programming error: compare $|a-b|$ with a tolerance, exactly as in the checks of this sheet.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Reading the remainders of repeated division in the wrong order

1.5 marks, and the weight check is immediate

What not to write

“ $13$ divided by $2$ gives the remainders $1$ , $0$ , $1$ , $1$ , so $1011_{2}$ .”

What to write

“The remainders are read from BOTTOM TO TOP: $1101_{2}$ , which is indeed $8+4+1=13$ .”

The first remainder is the LEAST significant bit: read the remainders from bottom to top,

1101_{2}=13

(green); read from top to bottom, they give

1011_{2}=11

(red).

Why: The first remainder obtained is the one of LOWEST weight, since the division starts from the ones. Rebuilding the number from its weights catches the error in ten seconds.

2. Grouping four bits at a time starting from the left

2 marks, and a value multiplied by a power of two

What not to write

“ $110101_{2}$ splits into $1101$ and $01$ , so $\text{D}1_{16}$ .”

What to write

“Group from the RIGHT: $11$ and $0101$ , padded on the left with zeros, so $0011\ 0101$ , that is $35_{16}$ .”

Groups of four bits are formed from the RIGHT:

11\,|\,0101

, that is

35_{16}

(green); cutting from the left gives

\text{D}1_{16}

, a different number (red).

Why: The grouping follows the weights, which are counted from the ones. Padding on the left with zeros does not change the value; padding on the right multiplies it.

3. Inverting the bits without adding one

2 marks, and every addition that follows

What not to write

“ $5$ is $0000\,0101$ , so $-5$ is $1111\,1010$ .”

What to write

“Invert THEN add $1$ : $1111\,1011$ . Check that $5+251=256$ .”

Why: One's complement, without the $+1$ , leaves two representations of zero and breaks addition. The check is arithmetic: the pattern of a negative $-x$ equals $2^{n}-x$ read as unsigned.

4. Diagnosing an overflow from the carry out

2 marks, and the diagnostic question is worth double on the exam

What not to write

“A carry comes out of the most significant bit, so there is an overflow.”

What to write

“In two's complement, overflow is read from the SIGN: two positive operands giving a negative result, or the reverse.”

Two positive operands,

100

and

50

, give a pattern whose leading bit is

1

: the result reads

-106

, and the overflow is there, with no carry out at all.

Why: The carry out signals an UNSIGNED overflow. In two's complement, it is often perfectly normal, for example when adding two negative numbers whose sum still fits.

5. Confusing the two representable ranges

1 mark, and a wrong conclusion about an overflow

What not to write

“On $8$ bits the range is $-255$ to $255$ .”

What to write

“Unsigned: from $0$ to $255$ . Two's complement: from $-128$ to $127$ , the range not being symmetric.”

8

bits,

256

patterns: from

0

255

as unsigned, from

-128

127

in two's complement, one step more on the negative side.

Why: Eight bits encode only $256$ values, whatever the convention. Since zero counts on the positive side, one more value remains on the negative side.

6. Believing that a simple decimal is written exactly in binary

2 marks on the analysis question, and bugs in programming

What not to write

“ $0.1+0.2=0.3$ , the computer will confirm it.”

What to write

“ $0.1$ has no terminating binary expansion: the computer returns $0.30000000000000004$ , and you always compare with a tolerance.”

Why: A terminating decimal has a terminating binary expansion only if its reduced denominator is a power of $2$ . One tenth is $\dfrac{1}{10}$ , whose denominator contains a $5$ .

7. Clearing a bit with an OR

1.5 marks, and the program does the opposite of what it claims

What not to write

“To set bit $3$ to zero, I use an OR with $0000\,1000$ .”

What to write

“OR SETS bits. To clear, you need an AND with the INVERTED mask: $1111\,0111$ .”

Why: Each operator has a single role: AND clears, OR sets, EXCLUSIVE OR toggles. An OR with a $1$ can never produce a $0$ .

8. Confusing a hexadecimal digit with a byte

1 mark, and an image size calculation divided by two

What not to write

“The colour $\text{FF}$ fits in one hexadecimal digit, so in $8$ bits each: three digits for an RGB colour.”

What to write

“One hexadecimal digit is $4$ bits; a byte needs TWO. An RGB colour is therefore written with six hexadecimal digits.”

Why: $16=2^{4}$ : each hexadecimal digit encodes exactly four bits. That is the whole reason for this base, which makes binary readable without distorting it.

9. Forgetting the bias or the implicit 1 in IEEE 754

2 marks, and an absurd order of magnitude

What not to write

“The stored exponent is $10000011$ , that is $131$ , so the number is of the order of $2^{131}$ .”

What to write

“The exponent is BIASED by $127$ : $131-127=4$ , so the number is of the order of $2^{4}=16$ .”

Why: The bias makes it possible to encode negative exponents without an extra sign bit. And the mantissa is always written with a $1$ before the point, which is not stored since it is certain.

Which method to choose

Which bitwise operation for which effect

Read what the program must do to the targeted bits.

If set some bits to zero without touching the others → AND with a mask where the bits to clear are $0$

Example: $x\ \text{AND}\ 1111\,0111$ clears bit $3$
If set some bits to one → OR with a mask where the bits to set are $1$

Example: $x\ \text{OR}\ 0000\,1000$ sets bit $3$
If invert some bits → EXCLUSIVE OR with a mask where the bits to toggle are $1$

Example: applied twice, it gives back the starting value
If test whether a bit is $1$ → AND with the mask, then compare the result with zero

Example: $x\ \text{AND}\ 0000\,1000$ nonzero means bit $3$ is set
If multiply or divide by a power of two → shift left or right by $k$ positions

Example: shifting left by $3$ multiplies by $8$

to the right, it is an INTEGER division: the bits pushed out are lost

Write a mask in binary first, then convert it to hexadecimal for the code. Writing it directly in hexadecimal is the source of half of all mask errors.

Which interpretation to give a bit pattern

Read what the question says about the CONTEXT, never the pattern alone.

If the question talks about an unsigned integer, a size or a counter → sum of the weights, from $0$ to $2^{n}-1$

Example: $1001\,0110$ is $150$
If the question talks about a signed integer or two's complement → a leading bit of $1$ means negative: the value is $\text{pattern}-2^{n}$

Example: $1001\,0110$ is $-106$
If the question talks about a floating-point number → split $1+8+23$ , remove the bias $127$ , restore the implicit $1$

Example: stored exponent $131$ for an actual exponent of $4$
If the question talks about text, a character or a key → ASCII code, one byte per character for the first $128$

Example: $0100\,0001$ is the letter A, that is $65$

The same $8$ -bit pattern can be $150$ , $-106$ , a character or a colour. Naming the interpretation chosen before computing is worth one mark on every reading question.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Converting by repeated division

When to use it: The question asks you to go from decimal to another base, with or without a fractional part.

1 Write the divisions one under the other, with the quotient and the remainder on each line.
2 Stop when the quotient is $0$ , never before.
3 Read the remainders from BOTTOM TO TOP for the integer part, and write the result with the base as a subscript.
4 For the fractional part, multiply repeatedly and read the integer parts from TOP TO BOTTOM.
5 Check by rebuilding the number from the weights.

Concluding sentence

“ $13=1101_{2}$ , since $8+4+1=13$ .”

The trap: Stopping the divisions when the quotient is $1$ : the last remainder, the most significant one, is then lost.

Marking: 1 mark for the divisions set out, 1 mark for the reading direction, 0.5 mark for the weight check.

Adding in two's complement and concluding about overflow

When to use it: The question asks for an addition of $n$ -bit signed integers, or asks whether the result is correct.

1 Write both operands on the SAME number of bits, padding on the left with the sign bit.
2 Add bit by bit with the carries, and ignore the carry that comes out of the leftmost position.
3 Read the sign bit of the result and compare it with those of the operands.
4 Conclude: overflow only if both operands have the same sign and the result the opposite sign.

Concluding sentence

“ $100+50$ gives $1001\,0110$ , that is $-106$ : two positives giving a negative, there is an overflow, and the result is unusable.”

The trap: Concluding that there is an overflow because a carry comes out: that is the unsigned criterion, not the two's complement one.

Marking: 1 mark for the alignment, 1 mark for the addition, 1 mark for the sign criterion, 1 mark for the conclusion.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Rebuild from the weights

After any conversion to binary, add up the weights of the positions holding a $1$ : you must get back the starting number.

$1101_{2}$ gives $8+4+1=13$ : the remainders were read in the right order.
Two's complement is checked by a sum

The pattern of $-x$ on $n$ bits, read as UNSIGNED, must equal exactly $2^{n}-x$ .

$-5$ on $8$ bits gives $251$ , and $5+251=256$ .
The expected number of digits

A byte is two hexadecimal digits; a number below $256$ fits in $8$ bits. A longer result gives away an error.

An RGB colour written with three hexadecimal digits instead of six.
The sign of the result

Before concluding a signed addition, compare the leading bit of the result with those of the operands.

Two positives giving a leading bit of $1$ : the result is unusable, whatever its pattern.

The typical problem, taken apart

An 8-bit signed addition that overflows

A sensor adds two readings, $100$ and $50$ , in a variable encoded on $8$ bits in two's complement.

Write the addition in binary, give the value read by the program, and say whether there is an overflow.

Step 1

$100=0110\,0100$ and $50=0011\,0010$ , both on $8$ bits.

Why

Write both operands on the same number of bits before anything else: an addition on different widths makes no sense and loses the alignment mark.

Step 2

Bitwise sum: $0110\,0100+0011\,0010=1001\,0110$ .

Why

Binary addition is set out exactly as in decimal, with carries. Here no carry comes out of the leading position, which changes nothing.

Step 3

Unsigned reading: $128+16+4+2=150$ , which is the expected sum.

Why

The pattern is right: the computer made no calculation error. The problem comes from the interpretation, not from the addition.

Step 4

Signed reading: the leading bit is $1$ , so the value is $150-256=-106$ .

Why

In two's complement, a pattern with a leading $1$ is read by subtracting $2^{8}$ . That is the value the program will actually use.

Step 5

Criterion: two positive operands, negative result, so OVERFLOW.

Why

The criterion is about the signs, never about the carry out. Here the signed range stops at $127$ , and $150$ exceeds it.

Step 6

Check: $-106+256=150$ , and $150>127$ .

Why

The first relation confirms the pattern, the second the diagnosis. On $16$ bits, the same addition would not overflow, since the limit would be $32\,767$ .

The conclusion, written out

“The pattern obtained is $1001\,0110$ ; read in two's complement on $8$ bits, it is $-106$ . Two positive operands giving a negative result, there is an overflow: the variable must be encoded on $16$ bits.”

The classic mistake on this problem: Answering $150$ because the pattern is indeed $150$ : the question is about the value READ by a program that interprets it in two's complement.

Learn by heart

• Repeated division: remainders from BOTTOM TO TOP. Fractional part: integer parts from TOP TO BOTTOM.
• One hexadecimal digit is $4$ bits, one octal digit $3$ bits; always group from the RIGHT.
• Two's complement: invert THEN add $1$ ; the pattern of $-x$ equals $2^{n}-x$ as unsigned.
• On $n$ bits: unsigned from $0$ to $2^{n}-1$ , signed from $-2^{n-1}$ to $2^{n-1}-1$ .
• Signed overflow: both operands of the SAME sign and a result of the opposite sign. The carry out proves nothing.
• AND clears, OR sets, EXCLUSIVE OR toggles. A left shift multiplies, a right shift divides as integers.
• IEEE 754: $1+8+23$ bits, exponent biased by $127$ , implicit $1$ , integers exact up to $2^{24}$ .

Frequently asked questions

In which direction do you read the remainders of repeated division?

From bottom to top, that is, from the last remainder obtained back to the first. The first remainder corresponds to the least significant digit, since the first division deals with the ones. Only stop when the quotient becomes zero, otherwise the most significant digit is lost.

How do you write a negative number in two's complement?

First write its absolute value in binary on the required number of bits, then invert all the bits, and finally add one. The resulting pattern, read as an unsigned integer, equals two to the power n minus the starting number, which gives an immediate check.

How can you tell whether there is an overflow?

By comparing the signs. A signed overflow occurs when both operands have the same sign and the result has the opposite sign. A carry coming out of the leading position proves nothing in two's complement: it signals an overflow only in the unsigned interpretation.

Why is 0.1 plus 0.2 not exactly 0.3 on a computer?

Because a decimal has a terminating binary expansion only if its reduced denominator is a power of two. One tenth has a five in its denominator, so its binary expansion is infinite and the computer rounds it. The rounding error survives the addition, hence the rule of always comparing two floats within a tolerance.

How many bits is one hexadecimal digit?

Exactly four, since sixteen is two to the power four. A byte therefore needs two hexadecimal digits, and a red green blue colour, which takes three bytes, is written with six digits. Grouping in fours always starts from the right, padding on the left with zeros.

Practise it

Corrected exercises: Number systems in computing, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

12 corrected exercises
120 points
180 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Proof techniques Next sheet Modular arithmetic

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-number-systems. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. With a B.Sc. in computer science from McGill and an M.Sc. in applied computer science from Concordia, I work through number systems on what actually breaks in real programs: silent overflows and floating-point comparisons.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: number systems in computing (201-N11)

The essentials

Positional weights, in every base

Converting, one way and the other

Two's complement

Bitwise operations, shifts and IEEE 754

The mistakes that cost marks

1. Reading the remainders of repeated division in the wrong order

2. Grouping four bits at a time starting from the left

3. Inverting the bits without adding one

4. Diagnosing an overflow from the carry out

5. Confusing the two representable ranges

6. Believing that a simple decimal is written exactly in binary

7. Clearing a bit with an OR

8. Confusing a hexadecimal digit with a byte

9. Forgetting the bias or the implicit 1 in IEEE 754

Which method to choose

Which bitwise operation for which effect

Which interpretation to give a bit pattern

How the answer is expected to be written

Converting by repeated division

Adding in two's complement and concluding about overflow

Check before you hand in

The typical problem, taken apart

An 8-bit signed addition that overflows

Learn by heart

Frequently asked questions

In which direction do you read the remainders of repeated division?

How do you write a negative number in two's complement?

How can you tell whether there is an overflow?

Why is 0.1 plus 0.2 not exactly 0.3 on a computer?

How many bits is one hexadecimal digit?

Corrected exercises: Number systems in computing, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?