CSC 100 – Numbering Systems Supplementary Notes

CSC 100 – Numbering Systems Supplementary Notes
In this document I hope to illustrate how different number systems are used, and how they differ from
the decimal system we use on a day-to-day basis.
Digits
What is a digit? You might answer the question with the answer “a digit is just a number”, but strictly
speaking it would be more accurate to say that a number is made up of a sequence of digits. A more
accurate answer to this question would be to say “a digit is a symbol that is used to represent numbers,
and numbers represent quantities of things”. When I say “I have 13 eggs”, the number 13 represents a
quantity of things (in this case eggs), and it is made up of the two digits 1 and 3.
For example, in the decimal system we use on a daily basis we have ten unique digits (or symbols) to
represent numbers. Those digits are of course 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. By combining these digits
in various ways we can express any quantity (or number) we wish. Since there are 10 digits in the
decimal system, it is said to be a base ten numbering system. However, there is absolutely no reason
why we couldn't restrict ourselves to only 2 digits to represent numbers. Or put another way, we could
represent any number in the base ten numbering system as base two numbers. As it turns out, this is
exactly the system a digital computer uses, thus it is of interest to us.
What you should know by this point:
● The base ten numbering system is a system which uses exactly ten digits to represent numbers.
● The base two (or binary) numbering system is a system which uses two digits to represent
numbers.
● Or more generally/formally: a base N system is a system which has exactly N unique digits or
symbols to represent numbers.
Number Systems
Think back to early grade school when you first started learning about numbers. At that time (you
might not remember this anymore) you learned that any number in the decimal (or base ten) system can
be expressed as a series of powers of ten. This is due to the fact that there are ten digits in the system.
So for example, the number 7623 (in decimal) can be written as:
7623=7000600203
=7×10006×1002×103×1
=7×1036×1022×1013×100
Of course we could go the opposite way, given a quantity written as a sequence of powers of ten, we
could write the number:
3×1024×1016×100
=3×1004×106×1
=300406
=346
Note the pattern: each digit in the number is a subsequent power of ten.
Again though, note that the choice of base 10 is completely arbitrary1, we could have just as easily
expressed the same quantity (three hundred and forty-six) in a base 2 system, as seen below.
346=256641682
=2826242321
=1×281×261×241×231×21
=1×280×271×260×251×241×230×221×210×20
=101011010base 2
The only difference here is that we have powers of 2 instead of powers of 10. And again, we could
have gone the opposite way, given a binary number get the decimal equivalent. Say you were given the
base 2 number 11010, how would you get the decimal (or base 10) equivalent? Again note the pattern:
each digit in a number represents a digit to multiply by a power of the base of the system, like so:
11010base 2=1×241×230×221×210×20
=1682
=26 base10
What you should know by this point:
● How any number in the base ten system can be expressed as a sequence of products where you
have a decimal digit multiplied by a power of 10
● How any number in the base two system can be expressed as a sequence of products where you
have a binary digit (0 or 1) multiplied by a power of 2
● How numbers in both systems are completely equivalent (that is, any decimal number can be
written as a binary one, and vice-versa), and how to convert from one system to the other.
Binary Arithmetic
How do we do arithmetic in binary then? Say for example I had 1010 eggs and you had 1100 eggs and
we wanted to know how many eggs we had between us, how would we do that? Well, just like the
decimal system, addition in binary works the same way. First lets look at an example in decimal:
9
+ 1
= 10
1 Nobody seems to know for sure, but it is widely assumed that the reason we use the base 10 system in our daily lives is
because we have exactly 10 fingers, and we first learn to count by counting fingers.
What happened here: when adding the 1 to 9, we exceeded the range of digits in the base ten system,
thus we had to carry a 1 to the second column. Binary addition works the same way, but this point of
“carrying” occurs much sooner as we only have two digits to work with (the following is in base two):
1
+ 0
= 1
1
+ 1
= 10
Note that in the second example we had to carry the 1 to the second column.
What you should know by this point:
● How to add two binary numbers together
The Hexadecimal Base 16 System (or “time to really bend your mind”)
What if we decided to do a base 16 system? That is, a numbering system which has sixteen unique
digits for representing numbers. This is completely possible, however a problem arises: in the English
language we typically only have ten symbols used as digits, but we need sixteen of them. The way this
problem is solved is by using the letters A, B, C, D, E, and F as digits. So for example, the following
table illustrates this:
Quantity Decimal (base ten) Binary (base two) Hex (base sixteen)
Zero 0 0 0
One 1 1 1
Two 2 10 2
Three 3 11 3
Four 4 100 4
Five 5 101 5
Six 6 110 6
Seven 7 111 7
Eight 8 1000 8
Nine 9 1001 9
Ten 10 1010 A
Eleven 11 1011 B
Twelve 12 1100 C
Thirteen 13 1101 D
Fourteen 14 1110 E
Fifteen 15 1111 F
Sixteen 16 10000 10
Note that the last row shows how “carrying” works the same way in hexadecimal: put a 0 in the
rightmost column, and carry the 1. So for example the hexadecimal number A3F is the same as:
A3F base16=A×1623×161F×160
=A×2563×16F×1
=10×2563×1615×1
=25604815=2623 base10
A Trick For Working With Hexadecimal Numbers
Lets say we had the hex number 3D4 and we wanted to see what it was as a binary number. One (long)
way of doing this would be to convert the hex number to decimal, then the decimal number to binary.
3D4=3×162D×1614×160
=3×25613×164
=7682084=980 base10
980base 10=51225612864164
=1×291×281×271×260×251×240×231×220×210×20
=1111010100base 2
However, there is an easier way. Note that if you take each hex digit, and convert it to binary using the
table shown earlier you get the following:
3base16=0011base 2
Dbase 16=1101base 2
4 base16=0100 base 2
Now take those 4 bit patterns and put them side by side and you get 001111010100 which is exactly
what we got doing the long method. The reason this works is because 16 is itself a power of two, you
can just convert each hex digit to binary and write out the pattern. The same works in reverse, say you
had the binary number 01011110 and you wanted to convert this to hexadecimal, you could just break
the binary number into groups of 4 bits, and then look up those 4-bit patterns in the table above like so:
01011110 breaks into the two patterns: 0101 and 1110 and:
0101base 2=5base 16
1110base 2=Ebase 16
So therefore:
01011110base 2=5 Ebase16
Hexadecimal numbers aren't used directly by computers (again everything inside a computer boils
down to bits or binary digits), but there are many computer applications that make use of hexadecimal
numbers (for example, colour codes in HTML web pages are often specified using hexadecimal
numbers – something you will be seeing in lab #3).
What you should know by this point:
● How base 16 numbers work, and how to convert them to binary and/or decimal
Exercises
1. Convert the following binary numbers to decimal:
a) 1001
b) 11101
c) 10100
d) 0
e) 1
f) 01001001110 (okay admittedly this one's artificially long)
2. Convert the following decimal numbers to binary:
a) 42
b) 176
3. What is the hexadecimal number “FF” expressed as a binary number? A decimal one?
4. Complete the table on the following page (this is the same table seen earlier in this document, but
with some entries removed). Note: a good practice exercise (read: exam prep) would be to create
this entire table from scratch, as if you can then it means that you can count in each of the three
number systems.
Quantity Decimal (base ten) Binary (base two) Hex (base sixteen)
Zero 0 0 0
One 1 1 1
Two 2
Three 3 11 3
Four 4
Five 5
6
Seven 7 111
Eight 1000 8
Nine 1001 9
1010
Eleven 1011 B
Twelve 12
Thirteen 13
Fourteen 14 1110 E
Fifteen 15 1111
Sixteen 16 10000