程序代写代做代考 scheme Java Computer Systems Week 1 – Numbers

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