Computer Systems Week 1 – Numbers
Lecture Objectives
To introduce the fundamentals of number representations, their conversion and how overflow can create problems in computer programs.
Slide #2 of 46
Numbers – Lecture Outline
Why do we use binary?
Representing Text
Decimal, Binary, Octal and Hexadecimal Notations How to convert from Decimal to Binary & vice versa? Conversion between other notations?
Overflow – and avoiding it
Signed Integers – 2’s complement
Illustration of Overflow using Factorial
Slide #3 of 46
What are Computers made of?
A collection of “switches” called transistors.
Can either be “on” or “off”, corresponding to a particular electrical state (conducting or not).
Forces “binary” representation “Off” → 0
“On” → 1
All data must be represented as sequences of ones and zeros – binary digits – bits
As must the computer’s “instructions”
Slide #4 of 46
Implications?
For practical engineering reasons it is better (cheaper, more reliable, faster …) to stick with basic components that only have two states – binary
But, in principle, we could build other types of computer – and they have been built
This applies within the processor, memory and all other components As an aside, all the data is just a pattern of bits. The interpretation put
on it is down to the program:
You can add two character strings or instructions
But, there are safeguards in most operating systems and programming languages that restrict this.
Historically, memory and processing was very limited. It still is, but not to the same extent.
Slide #5 of 46
Representing Text
Every text character is represented as a “binary string” A: 1000001
B: 1000010
C: 1000011
Text Encoding Schemes like ASCII, Unicode
These usually use 8, 16 or 32 bits to encode characters
Support internationalisation
https://en.wikipedia.org/wiki/Character_encoding
Strings (words, names, addresses etc) are usually represented by a block of characters. See how Java does it.
Numbers are more subtle
Need to worry about arithmetic
Slide #6 of 46
Decimal Notation (Base = 10)
The key thing is that we need to do arithmetic
Slide #7 of 46
Different Notations
System
Base
Symbols
Used by humans?
Used in computers?
Decimal
10
0, 1, … 9
Yes
No
Binary
2
0, 1
No
Yes
Octal
8
0, 1, … 7
No
No
Hexa- decimal
16
0, 1, … 9, A, B, … F
No
No
Slide #8 of 46
Counting in Different Number Systems (1 of 3)
Decimal
Binary
Octal
Hexa- decimal
0
0
0
0
1
1
1
1
2
10
2
2
3
11
3
3
4
100
4
4
5
101
5
5
6
110
6
6
7
111
7
7
Slide #9 of 46
Counting in Different Number Systems (2 of 3)
Decimal
Binary
Octal
Hexa- decimal
8
1000
10
8
9
1001
11
9
10
1010
12
A
11
1011
13
B
12
1100
14
C
13
1101
15
D
14
1110
16
E
15
1111
17
F
Slide #10 of 46
Counting in Different Number Systems (3 of 3)
Decimal
Binary
Octal
Hexa- decimal
16
10000
20
10
17
10001
21
11
18
10010
22
12
19
10011
23
13
20
10100
24
14
21
10101
25
15
22
10110
26
16
23
10111
27
17
Etc.
Slide #11 of 46
Conversion among Different Notations
Decimal Octal
Binary
Hexadecimal
2510 = 110012 = 318 = 1916 Base
Slide #12 of 46
Conversion – Decimal to Binary
Technique
Divide by two, keep track of the remainder
First remainder is bit 0 (LSB, Least- Significant Bit)
Second remainder is bit 1
Etc.
Binary
12510 = ?2 2 125
2 62 1 2 31 0 2 15 1 271
231 211 01
12510 = 11111012
Hex
Decimal
Octal
Example
Slide #13 of 46
Conversion – Binary to Decimal
Decimal
Octal
Technique
Multiply each bit by
2n, where n is the “weight” (“positional value”) of the bit.
The weight is the position of the bit, starting from 0 on the right
Add the results
Example
1010112 =>
Bit “0”
Binary
1 x 20 = 1 1×21= 2 0x22= 0 1 x 23 = 8 0x24= 0 1 x 25 = 32
Hex
4310
Slide #14 of 46
Decimal
Octal
Conversion – Decimal to Octal
Technique
Divide by 8
Keep track of the remainder
Binary
Hex
Example
123410 = ?8 8 1234
8 154 2
19 2
23 8
02
123410 = 23228
8
Slide #15 of 46
Decimal
Octal
Conversion – Octal to Decimal
Technique
Multiply each digit by 8n, where n is the “weight” of the digit
The weight is the position of the digit, starting from 0 on the right
Add the results
Binary
Hex
Example
7248=> 4×80= 4 2 x 81 = 16 7 x 82 = 448
46810
Slide #16 of 46
Technique
Divide by 16
Keep track of the remainder
Example
123410 = ?16 16 1234
77 2
Decimal
Octal
Conversion – Decimal to Hexadecimal
Binary
Hex
16
16
4 13=D 04
123410 = 4D216
Slide #17 of 46
Conversion – Hexadecimal to Decimal
Decimal
Octal
Technique
Multiply each digit by 16n, where n is the “weight” of the digit
The weight is the position of the digit, starting from 0 on the right
Add the results
Example
ABC16 =>
Binary
Hex
C x 160
B x 161
Ax162 =10×256=2560
274810
= 12 x = 11 x
1 = 12 16 = 176
Slide #18 of 46
Conversion – Binary to Octal
Technique
Group bits in threes,
starting on right
Convert to octal digits
Binary
Hex
Decimal
Octal
Example
10110101112 = ?8 1 011 010 111
1327
10110101112 = 13278
Slide #19 of 46
Conversion – Octal to Binary
Technique
Convert each octal digit to a 3-bit equivalent binary representation
Note: Every digit will be converted to 3 bits, even if all bits are zeros
Binary
Hex
Decimal
Octal
Example
7058 = ?2 705
111 000 101 7058 = 1110001012
Slide #20 of 46
Conversion – Binary to Hexadecimal
Technique
Group bits in fours,
starting on right
Convert to hexadecimal digits
Example
10101110112 = ?16 10 1011 1011
2BB 10101110112 = 2BB16
Decimal
Octal
Binary
Hex
Slide #21 of 46
Conversion – Hexadecimal to Binary
Decimal
Octal
Binary
Hex
Technique
Convert each hexadecimal digit to a 4-bit equivalent binary representation
Note: Every digit will be converted to 4 bits, even if all bits are zeros
Example
10AF16 = ?2 10AF
0001 0000 1010 1111
10AF16 = 00010000101011112
Slide #22 of 46
Conversion – Octal to Hexadecimal
Technique
Use binary notation as an intermediate representation.
Example
10768 = ?16 1076
001 000 111 110
23E
10768 = 23E16
Decimal
Octal
Binary
Hex
Slide #23 of 46
Conversion – Hexadecimal to Octal
Decimal
Octal
Technique
Use binary notation as an intermediate representation.
Example
1F0C16 = ?8 1F0C
Binary
Hex
0001 1111 0000 1100
17414
1F0C16 = 174148
Slide #24 of 46
Exercise – Conversions (Home Work)
Decimal
Binary
Octal
Hexa- decimal
33
1110101
703
1AF
Don’t use a calculator!
Slide #25 of 46