Numbering Systems: a companion

COMP1310 Introduction to Computers and Computing Ethics · First Semester 2026/27

This page goes with the two lectures on numbering systems. Read it with a pen and paper next to you. The sections build on each other, so read them in order the first time. There are four small tools to play with, and the practice questions at the end have their answers hidden until you open them.

1Why two symbols

Inside your phone's processor there are billions of tiny electronic switches (transistors). Each one either lets current through or it doesn't. You could try to build a switch that holds ten different voltage levels, one for each decimal digit, but telling ten levels apart reliably, billions of times a second, with heat and electrical noise around, is hard. Telling "on" from "off" is easy. So computers store everything using two symbols: 1 for on, 0 for off.

That leaves a real problem. How do you write 22, or 297, or −75, or 26.75, using only 0 and 1? You already know the method: you use it every day, with ten symbols. Once you see what our ordinary decimal system is actually doing, binary turns out to be the same idea with fewer symbols.

2What 754 really means

The 7 in 754 does not mean seven. It means seven hundreds, because of where it sits. Every position has a place value (القيمة المكانية), and in decimal (النظام العشري) the place values are powers of 10:

Where do the place values come from? Think of the distance counter (odometer) in a car. The right-hand wheel shows 0, 1, 2, … 9. There is no symbol after 9, so the wheel rolls back to 0 and pushes the next wheel on by one: 09 becomes 10. That push is the carry. The second wheel moves once every 10 steps, so it counts tens. The third moves once every 10×10 = 100 steps, so it counts hundreds. Each place is worth 10 times the place to its right.

The number 10 is the base (الأساس) of the system, and it does three jobs at once:

• it is how many symbols you have (0 to 9);
• it is the point where a wheel rolls over and carries;
• it is what you multiply by to get from one place value to the next.

Change the base and everything else follows. When more than one base is around, write the base as a small number after the brackets: (754)₁₀, (10110)₂. The slides also use a programmer's shorthand: a letter after the number, 10110b for binary and 27h for hexadecimal.

3Counting in binary

Now give every wheel of the odometer only two symbols, 0 and 1. A wheel rolls over after every 2 steps instead of 10. Count from zero and watch the binary (النظام الثنائي) column. Ignore the Octal and Hex columns for now; they will make sense a few paragraphs down, when we meet bases 8 and 16.

The highlighted rows are where binary gets a new wheel: at 2, 4, 8, 16. Each wheel moves half as often as the one on its right, so the binary place values are powers of 2:

Each binary digit is called a bit (short for binary digit). Bits come in named groups: 4 bits make a nibble, 8 bits make a byte, and in this course 2 bytes (16 bits) make a word. (How big a "word" is really depends on the machine; we use the lecture's definition.) So 1010 0011 is 8 bits, 2 nibbles, 1 byte.

How many values fit in n bits?

One bit has 2 patterns: 0 and 1. Add a second bit and you can put a 0 or a 1 in front of each of those, so you get 4. Every extra bit doubles the count:

A byte can hold 2⁸ = 256 different patterns, so as a plain (unsigned) number it runs from 0 to 255. The largest is 2⁸ − 1 for the same reason the largest 3-digit decimal number is 999 = 10³ − 1.

Other bases work the same way

Nothing here is special to 2 or 10. Base 8, octal (النظام الثماني), uses the digits 0 to 7 and carries at 8 (look at the octal column above: 7, then 10). Base 5 uses 0 to 4, base 7 uses 0 to 6, base 3 uses 0, 1, 2. A base-b system always has exactly b digits, from 0 to b−1. So (35)₇ is a real number, but (37)₇ is not: there is no digit 7 in base 7.

Base 16, hexadecimal or "hex" (النظام السداسي عشر), needs sixteen digits, and we only have ten numerals. So after 9 it borrows letters: A=10, B=11, C=12, D=13, E=14, F=15. In hex, F + 1 rolls over to 10, which is sixteen.

4Any base to decimal

You already have everything you need. Each digit means digit × place value, so to find the value of a number in any base, write out those products and add them. The place values are powers of the base, counted from 0 at the right.

Look at the middle two. (47)₈ and (27)₁₆ are the same number, 39. The digits alone don't tell you the value; you also need the base. That is why we write the subscript.

For binary there is a quicker way: each digit is 0 or 1, so just add up the place values that sit under a 1. For 10110 that is 16 + 4 + 2 = 22.

5Decimal to any base

Going the other way, you have a value and need to find its digits. The method: divide by the base and write down the remainder (باقي القسمة). Divide the quotient by the base again, and keep going until the quotient is 0. Then read the remainders from the bottom up.

Reading up: (22)₁₀ = (10110)₂, which matches section 4.

Why bottom-up? Check it on a number you know

Do the same thing to 754 with base 10. 754 ÷ 10 gives quotient 75, remainder 4. The remainder is the last digit, and the quotient is the number with that digit chopped off. Next, 75 ÷ 10 gives 7 remainder 5. Then 7 ÷ 10 gives 0 remainder 7. The remainders came out 4, 5, 7: the digits of 754, last digit first.

That is all repeated division does, in any base. Dividing by the base splits off the rightmost digit as the remainder and shifts everything else one place to the right. Dividing 22 by 2 gives remainder 0, which is the last bit of 10110, and quotient 11, which is 1011. Because the digits come out right-to-left, you read the column upwards.

Two more worked out. Remainders can be anything from 0 to base−1, so in hex a remainder of 10 to 15 is written A to F.

Always check by converting back with section 4: 128 + 64 + 16 + 8 + 4 = 220.

6Octal and hex: binary in short

To convert binary to octal you could go through decimal, but there is a much shorter route, and it is the reason octal and hex are used in computing at all.

Here is why it works, on one number. Take 101110₂ = 32 + 8 + 4 + 2 = 46, and split it into 101 | 110. The left three bits are worth 32, 16, 8, which is 8 × (4, 2, 1), so they count eights: 101 = 5 eights. The right three bits count ones: 110 = 6. So 46 = 5×8 + 6 = (56)₈. Because 8 = 2³, each octal digit is exactly 3 bits. In the same way 16 = 2⁴, so each hex digit is exactly 4 bits.

The rule: starting from the right (or from the binary point, if there is one), cut the bits into groups of 3 for octal or 4 for hex. If the last group on the left is short, pad it with zeros. Then replace each group with its digit.

You only need the 16 patterns below, and the first 8 patterns, 0 to 7 (dropping the leading 0), are the octal table too.

This is why programmers like hex. A byte is exactly two hex digits, 00 to FF, so a long string of bits becomes short and readable without losing anything. 1101 0001 is hard to read aloud; D1 is not. You will see memory written this way in section 11.

Between two bases that are not decimal

If both bases are powers of 2 (2, 4, 8, 16), go through binary: expand each digit into bits, then regroup.

Base 4 = 2², so each base-4 digit is 2 bits. If one of the bases is not a power of 2, such as 7, go through decimal: (35)₇ = 3×7 + 5 = 26 = (32)₈.

7Fractions

Place values carry on past the point. In decimal, the places after the point are tenths, hundredths, and so on: 0.25 = 2×10⁻¹ + 5×10⁻². In binary they are halves, quarters, eighths:

Decimal fraction to binary: multiply by 2

Convert the whole part and the fraction part separately. The whole part uses division, as before (11 = 1011). For the fraction part: multiply it by 2. The whole-number part of the answer (0 or 1) is the next bit. Keep only the fraction and repeat until it becomes 0. Read the bits top-down.

So 0.375 = (0.011)₂ and 11.375 = (1011.011)₂.

Why it works. Multiplying by 10 moves a decimal point one place right: 0.375 × 10 = 3.75, and the first digit after the point has jumped across it. Multiplying by 2 does the same thing to a binary point. 0.375 is 0.011 in binary. Doubling it gives 0.75, which is 0.11: the first bit after the point, a 0, has crossed over and become the whole part. Doubling 0.75 gives 1.5, which is 1.1: the next bit, a 1, has crossed over. Each time you write down the bit that crossed, throw it away, and double again. The bits come out first-to-last, which is why this time you read downwards.

Same method for 26.75: 26 = 11010, and 0.75 × 2 = 1.5 (bit 1), 0.5 × 2 = 1.0 (bit 1). So 26.75 = (11010.11)₂. Keep this one; we store it in memory in section 12.

Some fractions never end

Try 0.2:

We are back at 0.2, so the same four bits repeat forever: 0.2 = (0.0011 0011 0011…)₂. Likewise 0.3 = (0.0 1001 1001 1001…)₂. The lecture's answers, 0.0011 and 0.01001, are these same expansions cut off after a few bits.

This is the binary version of 1/3 = 0.3333… in decimal. A fraction has a finite binary form only if, written in lowest terms, its denominator is a power of 2. 0.375 = 3/8 ends; 0.2 = 1/5 and 0.1 = 1/10 do not. A computer has a fixed number of bits, so it cannot store 0.1 or 0.2 exactly. It stores the nearest value it can. That is why, in many programming languages, 0.1 + 0.2 prints 0.30000000000000004.

8Binary addition

It is the column method you learned in primary school. The only change is that a column "fills up" at 2 instead of 10:

Carries are shown in teal on the top line.

 111      carries
 01111       15
+00110     +  6
------     ----
 10101       21

11 1 11      carries
 11010011     211
+01010110   +  86
---------   -----
100101001     297

The second answer has 9 bits even though both inputs had 8: 297 is bigger than 255, the most a byte can hold. Keep that in mind for section 10.

With fractions, line up the points first and pad with zeros so both numbers have the same number of places, then add as usual:

     1     carries
 110.010      6.25
+001.011    + 1.375
--------    -------
 111.101      7.625

9Negative numbers

On paper you just write a minus sign. A computer has no minus sign, only bits. And there is one more fact about hardware you need first: it stores numbers in a fixed number of bits, such as 8, 16 or 32. Before we can talk about negative numbers we have to agree on the width. That is why everything below says "4-bit" or "8-bit". The same pattern 1101 means different things under different agreements.

Idea 1: sign-magnitude

Use the leftmost bit as a sign bit (بت الإشارة): 0 for +, 1 for −. The other bits hold the size. In 4 bits, +5 = 0101 and −5 = 1101. But read 1101 as a plain unsigned number and it is 13. The bits don't carry their meaning with them; the program has to know which agreement is in use.

Sign-magnitude has two problems. It has two zeros (0000 = +0 and 1000 = −0). And ordinary addition gives wrong answers: 5 + (−5) = 0101 + 1101 = 1 0010, which in 4 bits is 0010 = 2, not 0.

Idea 2: one's complement

To make −x, flip every bit of x. In 4 bits, 5 = 0101 so −5 = 1010, and −1 = 1110. Better, but there are still two zeros: 0000 and 1111.

Idea 3: two's complement (what computers actually use)

Flip every bit, then add 1. For −5 in 4 bits: 0101 → 1010 → 1011.

Why this particular recipe? Go back to the odometer, a 4-bit one showing 0000, and turn it backwards one step. Every wheel rolls back from 0 to 1: you get 1111. One step below zero is −1, so 1111 should mean −1. One more step back gives 1110 = −2, then 1101 = −3, 1100 = −4, 1011 = −5. That is exactly what flip-and-add-1 produced.

And why does the recipe always land on the right pattern? Add x to its flipped version: every column is 1 + 0, so you get 1111. Add 1 more and the odometer rolls over to 0000. So flipped-x + 1 is the number that, added to x, gives zero, which is exactly what −x should do. (As a check: in 4 bits, −5 is stored as the pattern for 16 − 5 = 11 = 1011.)

A second way to see it, often quicker for reading a pattern: in two's complement the leftmost bit is worth minus its usual place value. In 4 bits it is worth −8 instead of 8:

Here are all sixteen 4-bit patterns under each agreement:

Three things to read off the table:

• In every signed scheme, a leftmost 1 means negative (apart from the extra −0 in the first two schemes). That is your quick sign check.
• Two's complement has one zero, so its 16 patterns cover −8 to 7: one more negative than positive.
• To find the size of a negative two's complement number, take its two's complement again: 1011 → 0100 → 0101 = 5, so 1011 is −5.

For n bits, two's complement covers −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1:

Go back to the bit board and watch the "signed" box. Set 11111111 (−1) and 10000000 (−128). Press "Flip and add 1" on any pattern to negate it, and press it twice to get back where you started.

10Subtraction and overflow

This is why computers use two's complement: subtraction needs no circuit of its own, a − b = a + (−b). Make −b with flip-and-add-1, then add normally, keeping only n bits.

Example 1: 01111111 − 76, in 8 bits

111111       carries
 01111111     127
+10110100   +(−76)
---------   ------
100110011      51

The sum has a ninth bit. It is a carry out of the 8-bit width, and you simply drop it: the answer is 00110011 = 51, which is 127 − 76. Dropping that carry is correct; it is the odometer rolling past zero.

The lecture slide labels this ninth bit "overflow". In two's complement it is called a carry out, and it is dropped, because the answer is right. Overflow means something else, below.

Example 2: 00110010 + (−125), in 8 bits

      1      carries
 00110010      50
+10000011   +(−125)
---------   -------
 10110101     −75

No carry out this time. The leftmost bit is 1, so the result is negative. Its size is the two's complement of 10110101: flip to 01001010, add 1, get 01001011 = 75. So the answer is −75, and 50 − 125 = −75.

Overflow: when the answer does not fit

In 4 bits the largest number is 7. Ask for 6 + 3:

 11      carries
 0110      6
+0011    + 3
-----    ---
 1001     −7 ?

The true answer, 9, does not fit in 4-bit two's complement, so the pattern wraps round into the negatives. This is overflow (الفيضان). The rule for spotting it: overflow happens when you add two numbers of the same sign and the result has the opposite sign. Two positives giving a negative, or two negatives giving a positive. Adding a positive and a negative can never overflow, because the answer lies between the two. You can see it on the bit board too: 01111111 + 1 jumps from 127 to −128.

11Integers and characters in memory

Memory is a long row of bytes, each 8 bits. The bits have no meaning on their own. 01000001 could be the number 65, the letter A, or part of a real number; it depends on what the program has decided that byte is.

Integers in 2 bytes

Store 92 in a 16-bit word. 92 = 64 + 16 + 8 + 4 = 1011100. Pad on the left to 16 bits and group into nibbles:

Store −94 in two's complement, 16 bits:

A check: FFA2 as unsigned is 65442, and 65536 − 94 = 65442. That is the 2ⁿ − x rule from section 9 with n = 16.

Characters: ASCII

Letters are stored as numbers. ASCII (American Standard Code for Information Interchange) is a table that gives each character a code: A = 65, B = 66, …, Z = 90; a = 97, b = 98, …; the digit "0" = 48; a space = 32. Compare a capital and small letter in binary:

Capital and small versions of every letter differ in exactly the bit worth 32. ASCII codes go from 0 to 127, so they need only 7 bits, which leaves the leftmost bit of a byte free.

The parity bit: a simple error check

When data is sent or stored, a bit can occasionally flip. A parity bit is one extra bit, chosen so that the total number of 1s is even (even parity) or odd (odd parity). Here it goes in that free leftmost bit.

Store Q (ASCII 81) with even parity:

With odd parity, Q already has an odd count, so the parity bit is 0 and the byte is 0101 0001 = (51)₁₆, still 81 in decimal.

The receiver counts the 1s. If one bit flipped on the way, the count is now wrong and the error is caught. If two bits flipped, the count is right again and the error slips through. Parity also cannot tell you which bit flipped, so it detects a single error but cannot fix it.

12Real numbers: floating point

Integers cannot hold 26.75, or a very small value like 0.000003. For those, computers use floating point (الفاصلة العائمة), which is scientific notation in base 2. In decimal, 26750 = 2.675 × 10⁴: one digit before the point, and the power of 10 says where the point really belongs. In binary:

Writing it with exactly one 1 before the point is called normalising. Every number except 0 can be normalised this way, because in binary the first nonzero digit is always 1.

The 32-bit layout (single precision, IEEE 754)

• Sign: 0 for positive, 1 for negative.
• Exponent, with a bias of 127: the exponent can be negative (0.375 = 1.1 × 2⁻²), but there is no separate sign bit for it. Instead we store exponent + 127. So the exponent 4 is stored as 131, and the exponent −2 as 125. Why 127? It is roughly the middle of 0 to 255, so about half the stored values mean negative exponents and half mean positive ones. Stored values 0 and 255 are kept for special cases (zero, infinity and a few others), so ordinary numbers use exponents from −126 to 127.
• Mantissa: the bits after the point in 1.xxxx. The leading 1 is not stored, because every normalised number has it; leaving it out buys one extra bit of precision. Pad with zeros on the right to fill 23 bits.

Worked: 26.75

Try 0.1 in the encoder. Its binary form repeats forever (section 7), and only 23 bits after the point are kept, so the stored value is a tiny bit off. With 24 bits of precision (23 stored plus the hidden 1), single precision keeps about 7 significant decimal digits.

13Practice

Do each one on paper before opening the answer. Several are the homework questions from the lectures.

1. Convert (21)₁₀ and (15)₁₀ to binary, and (200)₁₀ to hex.

2. Convert 1010b, 0010b and 101b to decimal.

3. Convert to octal: 101101011₂ and 100101001₂.

4. Convert to decimal: (72)₈, (72)₁₆, (DE1)₁₆.

5. (AB)₁₆ = ( ? )₂

6. (23)₄ = ( ? )₈

7. (35)₇ = ( ? )₈

8. (72E)₁₆ = ( ? )₈

9. Convert 37.375 to binary.

10. Convert 0.2 to binary. Why can't you finish?

11. Write −5 in 4-bit two's complement, and −76 in 8-bit two's complement.

12. In 4-bit two's complement, work out 0101 + 0100. Is the answer correct?

13. In 8-bit two's complement, work out 45 − 100.

14. Represent the integer −1 in 2 bytes, in hex.

15. Store your name in memory in ASCII with odd parity, in hex. Try it with the name "Sami".

16. Encode 11.375 as a 32-bit float.