程序代写代做代考 Java algorithm computer architecture SEC204

SEC204
Computer Architecture and Low Level Programming
Dr. Vasilios Kelefouras
Email: v.kelefouras@plymouth.ac.uk
Website:
https://www.plymouth.ac.uk/staff/vasilios -kelefouras
School of Computing (University of Plymouth)
Date
24/09/2019

2
Outline
 Positional Numbering Systems
 Converting Positional Numbering Systems  Basic Binary Arithmetic Operations
 Signed Integer Representation
 Floating Point Representation
 Character Codes

3
What to do…
 In this file you will find the Lecture slides together with some extra slides  These extra slides are examples you need to understand and solve on
your own
 Study all the examples that follow and try to solve them on your own…
 Pay attention to the following slides  15-21
 24-27  35-42  48-49

4
Basics (1)
 The bit is the most basic unit of information in a computer  Switching activity 0 or 1
 A Byte is a group of 8 bits
 A byte is the smallest possible addressable unit of computer storage
 The term, “addressable,” means that a particular byte can be retrieved according to its location in memory
 A word is a contiguous group of bytes, e.g., an integer uses 4 bytes  Word sizes of 4 or 8 bytes are most common

5
Kilo- (K) = 1 thousand = 103 and 210 Mega- (M) = 1 million = 106 and 220 Giga- (G) = 1 billion = 109 and 230 Tera- (T) = 1 trillion = 1012 and 240 Peta- (P) = 1 quadrillion = 1015 and 250 Exa- (E) = 1 quintillion = 1018 and 260 Zetta- (Z) = 1 sextillion = 1021 and 270 Yotta- (Y) = 1 septillion = 1024 and 280
Normally, powers of 2 are used for measuring capacity
Basics (2)
Milli- (m) = 1 thousandth = 10-3 Micro- (μ) = 1 millionth = 10-6 Nano- (n) = 1 billionth = 10-9 Pico- (p) = 1 trillionth = 10-12

6
Basics (3)
 Hertz = clock cycles per second (frequency)
 1MHz = 1,000,000Hz
 Processor speeds are measured in MHz or GHz
 Byte = a unit of storage
 1KB = 210 = 1024 Bytes
 1MB = 220 = 1,048,576 Bytes
 1GB = 230 = 1,099,511,627,776 Bytes
 Main memory (RAM) is measured in GB
 Disk storage is measured in GB for small systems, TB (240) for large systems

7
Think Pair Share activity
 How many milliseconds (ms) are in 1 second?
 How many nanoseconds (ns) are in 1 millisecond?  How many kilobytes (KB) are in 1 gigabyte (GB)?  How many bytes are in 20 megabytes?

8
POSITIONAL NUMBERING SYSTEMS
 Positional numbering systems are systems in which the placement of a digit in connection to its intrinsic value determines its actual meaning in a numeral string
 The organization of any computer depends considerably on how it represents numbers, characters, and control information
 There are several positional numbering systems such as Decimal, Binary, Octal, Hexadecimal etc
 The positioning system is provided as a subscript, e.g., 1410, 101012, 8216
 Our decimal system is the base-10 system. It uses powers of 10 for each position
in a number
 The binary system is also called the base-2 system
 The hexadecimal system is the base-16 system
 The Mayan and other Mesoamerican cultures used a number system based in a base-20 system

9
Decimal System
 Decimal system: Our well known and used system.

 It uses 10 different digits: 0,1,2,3,4,5,6,7,8,9
 Our decimal system is the base-10 system. It uses powers of 10 for each position in a number
 For example, the decimal number 947 in powers of 10 is 947 =
=9×100 + 4×10 + 7×1 = =9×102 + 4×101 + 7×100
 70216=7×10000+0x1000+2×100+1×10+6×1= =7×104+0x103+2×102+1×101+6×100
The decimal number 3812.46 in powers of 10 is (3×103 + 8×102 +1×101+2×100+ 4×10-1+ 6×10-2)

10
Binary System (1)
 A binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically 0 (zero) and 1 (one)
 The base is 2
 2 different digits are used: 0,1
 For example, 1012= 1×22 +0x21 +1×20
= 1×4+0x2+1×1
= 510
 The binary number 11001 in powers of 2 is: 1×24 + 1×23 + 0x22 +
0x21 + 1×20 = 16 + 8 + 0 + 0 + 1 = 2510
 1011.1012 =
= 1×23 +0x22 +1×21+1×20 +1×2-1 +0x2-2 +1×2-3 =
= 1×8+0x4+1×2+1×1+1×0.5+0x0.25+1×0.125 =11.62510

11
2n representation
210
24
23
22
21
20
2-1
2-2
2-3
number
1024
16
8
4
2
1
0.5
0.25
0.125
Binary System (2)
Convert the following binary number 1101.101 to decimal
1101.101 2=1×23 + 1×22 + 0x21 + 1×20 + 1×2-1 + 0x2-2 + 1×2-3 = 8 + 4 + 0 + 1 + 0.5 + 0 + 0.125 = 13.62510

12
Octal system
 The base is 8
 8 different digits are used only: 0,1,2,3,4,5,6,7
 For example: 4368 = 4×82 +3×81 +6×80
= 4×64+3×8+6×1 = 28610
Convert the following octal number 205.248,to decimal:
205.248=2×82 +0x81 +5×80 + 2×8-1 + 4×8-2
= 2×64 + 0 + 5 + 2×0.125 + 4×0.015625 = 133.312510

13
Hexadecimal system
 The base is 16
 16 different digits are used: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F (we do not use numbers with 2 digits like 10,11,12,…), but
Α instead of 10, B instead of 11, C instead of 12, etc)
 Example: 3Β116 = 3×162 +11×161 +1×160
= 3×256+11×16+1 = = 768 + 176 + 1=
= 94510
Convert the following hexadecimal number 20C.216 to decimal
20C.216= 2×162 + 0x161 + 12×160 + 2×16-1= =2×256 + 0 + 12×1 + 2×0.0625= =512 + 12 + 0.125=
=524.12510

14
Positional Numbering Systems – General case
 Base: r
 Uses r different digits: 0,1,2,3,..r-1
 Νr =An-1 An-2…A1 A0 A-1 A-2…A-(m-1)A-m
Νr =An-1 xrn-1 +An-2 xrn-2 +….+A1 xr1 +A0 xr0 +A-1 xr-1 +A-2 x
r -2 +…+A-(m-1) x r -(m-1) +A-m x r -m
For example if 234.035=?10 then n=3, m=2 and r=5
 The left most digit (An-1) is called Most Significant Bit-(MSB) while the right most (A-m ) Least Significant Bit-(LSB)

15
Converting Positional Numbering Systems
From Decimal to Binary
The easiest method of converting integers from decimal to some other base uses division 37 / 2 = 18 remainder 1
Procedure:
a. Divide the decimal with 2
b. Write down the quotient and the remainder
c. Divide quotient with 2
d. Write down the quotient and the remainder
e. Repeat the process (c)-(d) until the quotient becomes zero
f. Write down the binary number from bottom (MSB) to top (LSB)
Base Quotient
Remainder

16
From Decimal to Binary, an example
8310 = ?2
83  2 =41 remainder 1 41  2 =20 remainder 1 20  2 =10 remainder 0 10  2 =5 remainder 0
5  2 =2 remainder 1 2  2 =1 remainder 0
(LSB)
1  2 =0 remainder 8310 = 10100112
1
(MSB)
Our result, is the remainders in reverse order (reading from bottom to top)
If the decimal number is lower than 1, e.g., 0.25, or contains a fractional part the procedure applied is different

17
Convert From Decimal To Another Base
 We follow the same procedure as in the previous slide (from decimal to binary) but instead of using 2-base we use the r-base.
 Convert the decimal 52410 to hexadecimal
524:16= 32 remainder 12 32:16=2 remainder 0
2:16=0 remainder 2 Thus, 52410= 20C16
6610 = ?2 12810= ?16
(1210=C16)

18
Binary
Octal
0
0
0
0
0
0
1
1
0
1
0
2
0
1
1
3
1
0
0
4
1
0
1
5
1
1
0
6
1
1
1
7
Convert from binary to octal
Procedure:
1. To convert a binary number of octal, we group all the 1’s and 0’s in the
binary number in sets of three, starting from the far right
2. Start from the right to make your groups
3. Add zeros to the left of the last digit if you don’t have enough digits to make a set of three
4. Write down the decimal representation of every group
1010112 = ;8
=101 011
100110112 = ;8
10 011 011 010 011 011
233
= 5 3 100110112 = 2338
1010112 = 538

19
Binary
Octal
0
0
0
0
0
0
1
1
0
1
0
2
0
1
1
3
1
0
0
4
1
0
1
5
1
1
0
6
1
1
1
7
Convert from Octal to binary
 Converting from octal to binary is as easy as converting from binary to octal. Simply look up each octal digit to obtain the equivalent group of three binary digits
317.28 =;2
= 011 001 111. 010
= 11001111.012

20
Convert Binary to Hexadecimal
Procedure:
1. Cut your string of binary numbers into groups of four, starting from the right
2. Add extra zeros to the front of the first number if it is not four digits
3. Convert one 4-digit group at a time. To convert between Binary and Hexadecimal, you simply replace each Hex digit with its 4-bit binary equivalent and vice versa
100011010112 = ;16
= 100 0110 1011
= 0100 0110 1011 =46Β
01002=0+4+0+0=416
01102=0+4+2+0=616
10112=8+0+2+1=11=B16
100011010112 = 46Β16

21
Convert Hexadecimal to Binary
 Likewise from Octal to Binary
 Simply look up each hexadecimal digit to obtain the equivalent group of four binary digits
8Β.216 = 1000 1011.00102
 That’s why we use hexadecimal in computer systems! Humans can still understand it, and computers can calculate Hex faster than decimal values!

22
Basic arithmetic operations
 The basic arithmetic operations are applied to all the previous numerical systems. There are:
 Addition
 Subtraction  Multiplication  Division
 For the reminder of this lecture we will focus on the binary system

23
Binary Addition (1)
Binary addition is like decimal addition:
1. 2.
Put the numbers in a vertical column, aligning the decimal points
Add each column of digits, starting on the right and working left. If the sum of a column is more than ten, “carry” digits to the next column on the left.
457 + 148 605
(011 Carry)
In the example above we add 8+7 and write 5 instead of 15. We
propagate 10 (which is the base) to the left and we write the remainder For every propagation, we add 1 carry to the next addition (left)
The same holds when adding different numerical system numbers too

 

24
Binary addition:
1 011 0 1 1 1+ 11 10 1 1 0
1 0 010 1 1 0 1
( 0 1 1 1 1 0 1 1 0 carry)
1 1 1 1 1 0 1 1 +
11101011 111100110
( 11111011 carry)
Binary Addition (2)
Note that: 0+0=
1+0=0+1= 1 and carry 0
1+1= 0 and carry 1, as 1 + 1 = 102 = 210 1+1+1= 1 and carry 1, as 1 + 1 + 1 = 112 = 310
0 and carry 0

25
Binary Subtraction (1)
Binary subtraction is like decimal subtraction:
1. Put the numbers in a vertical column, aligning the decimal points.
2. Subtract each column, starting on the right and working left. If the digit being subtracted in a column is larger than the digit above it, “borrow” a digit from the next column to the left. When we borrow a carry, we add 1 to the subtrahend of the next subtraction
435 6
-2 1 8 9 216 7
( 0 0 1 1 borrow carry from the left)

26
For binary subtraction: 0– 0= 0
“bottom” digit is 1
02 0202 02
1 0 1 0 1. 1 0 1 -1011.11
01001.111
Binary Subtraction (2)
1– 0 = 1
1–1=0
10 – 1 = 1, as 102 = 210
The first three are the same as in decimal. The fourth fact is the only new one; it is the borrow case. It applies when the “top” digit in a column is 0 and the
000
1 1 0 1 0 11 -110110 0 11 0 1 0 1 ( 1 1 0 1 0 0
carry)

27
Binary Subtraction (3)
 The procedure explained in the previous slides holds only when we subtract X-Y where Χ>Υ
 If X Υ=2C(Χ)= 10111 = – 910 Check: Χ+Υ=
01001 +10111
100000=00000
The carry is discarded as the result must be 5 bits
 We can always check whether the two’s complement result is correct by adding the two numbers. The result has to be zero. Note that the result of the addition must be of the n bits, where n is the number of bits of the inputs
 Find the negative binary number (two’s complement) of the following positive number with 7bits 0101101 (4510)
Answer 1010011

36
Signed Integer Representation Two’s Complement – Example2
Find the negative binary number (-1210)
  
Write down the positive 1210 =011002
Decide the number of the bits. We can use 5 or more. Let say 8 bits Find the two’s complement as follows
1210 = 000011002 ,-1210 = 11110011+1=11110100 -1210 =11110100 (negative number)

37
Wrap up
Given a positive binary number, we find its negative binary number by following the procedure:
1.
2. 3.
We decide the number of bits of the positive number. At least one ‘0’ has to appear on its left.
We find its two’s complement
If the MSB (the left most) is not ‘1’ then we made a mistake…

38
 
Subtraction with two’s complement
We know that A-B=A+(-B)
So, instead of applying a subtraction we can make an addition with the
opposite number, i.e., the two’s complement. The procedure follows:
1. Find –B, i.e., its two’s complement
2. Add A with B’s two complement
3. The result has as many bits as the inputs
Make the subtraction Z=12-5 (use 5 digits)
1210=011002, 510=001012, -510=110112
Ζ=01100 + 11011=100111, but we need 5 bits thus Z=001112=710
Z=00111
Make the subtraction 9-12 (use 5 digits) 910=010012, 1210=011002, -1210=101002
Ζ=01001 + 10100=11101 and thus Z=11101 (-310) Z=11101
38

39
Unsigned and Signed Integer Representation
 Both signed and unsigned numbers are useful
 For example, memory addresses are always unsigned
 Using the same number of bits, unsigned integers can express twice as many “positive” values as signed numbers.
 For example, the range of values that can be represented in 4-bits is:
• 00002 to 11112 (or 0 to 15) as unsigned
• 01112 to 11112 (or +7 to -7) as signed magnitude
• 01112 to 10002 (or +7 to -8) as two’s complement

40
Example #1
What decimal value does the 8-bit binary number 10011110 have if
a) it is interpreted as an unsigned number?
b) it is on a computer using signed-magnitude representation?
c) it is on a computer using one’s complement representation?
d) it is on a computer using two’s complement representation?
Answer:
a. 100111102 = 1×27 + 1×24 + 1×23 + 1×22 + 1×21 = 128+16+8+4+2=15810
b. 100111102 = 1 (negative) 00111102 =- 1×24 + 1×23 + 1×22 + 1×21 = -3010
c. Find the positive of 100111102 ;invert the bits of 100111102 and therefore 011000012 . 011000012 =1×26 + 1×25 + 1×20=64+32+1=9710. Since the original number was negative, the number is -9710
d. Find the positive of 100111102 ;invert the bits of 100111102 and add 1; therefore 011000102 . 011000102 =1×26 + 1×25 + 1×21=64+32+2=9810. Since the original number was negative, the number is -9810

41
Example #2
What decimal value does the 8-bit binary number 00010001 have if
a) it is interpreted as an unsigned number?
b) it is on a computer using signed-magnitude representation?
c) it is on a computer using one’s complement representation?
d) it is on a computer using two’s complement representation?
Answer:
a. 000100012 = 1×24 + 1×20 = 16+1=1710
b. 000100012 = 0 (positive) 00100012 = 1×24 + 1×20 = 16+1=1710
c. 000100012 = 1×24 + 1×20 = 16+1=1710
d. 000100012 = 1×24 + 1×20 = 16+1=1710

42
Example #3
Perform the following binary subtraction using two’s complement representation: Z=8 – 6
Answer:
1. Instead of subtraction we do addition: 8 – 6 =8 + (-6)
2. Choose the number of bits to represent 8 and 6 decimal numbers to binary. At least one zero has to appear on the left. Thus, we need 5 bits or more
810=010002
610=001102
3. Find – 610 (two’s complement) – 610 = 110102
3. Make the addition (The result has 5 bits ) 0 1 00 0
1 101 0
1 0 0 0 1 0 -> 000102=210

43
Signed Integer Representation Multiplication and Division by 2 (1)
 Binary multiplication and division by 2 is very easy. (as easy as it is to multiply and divide by 10 in the decimal system)
 Simply use an arithmetic shift operation 12= 110
102= 210 1002= 410 10002= 810 100002= 1610
 A left arithmetic shift inserts a 0 in for the rightmost bit and shifts everything else left one bit; in effect, it multiplies by 2
 A right arithmetic shift shifts everything one bit to the right, but copies the sign bit; it divides by 2

44
Signed Integer Representation Multiplication and Division by 2 (2)
 Multiplication by 2
 Shift left by one place  E.g. to calculate 2 * 7
 Division by 2
 Shift right by one place  E.g., to calculate 14/2
Binary
0000 0111 +7 0000 1110 +14
 To multiply by 4, we perform a left shift twice  To divide by 4, we perform a right shift twice
 Using arithmetic shifting, perform the following:
a) double the value 000101012
b) quadruple the value 001101112
c) divide the value 110010102 in half
Decimal

45
Floating-Point Representation (1)
 To represent real numbers with fractional values, floating-point representation is used
 Floating-point numbers are often expressed in scientific notation  For example: 0.125 = 1.25 × 10-1
 Remember that when a number is multiplied by its base, e.g., 10, then we add a zero or we move the ‘,’ by one position to the right
 235×10 = 2350  1.345×10=13.45
 1102×2 = 11002 (6×2=1210)
 101.112×2=1011.1 (5.75×2=11.510)

46
Floating-Point Representation (2)
 Computers use a form of scientific notation for floating-point representation
 Single Precision floating point format 32-bit
 Double Precision floating point format 64-bit
 Numbers written in scientific notation have three components:

47
Sign-S 1-bit
Exponent-E 8 – bits
Mantissa (Fraction) – F 23 – bits
Single precision Floating-Point format (1)
A binary number is represented in FP format as follows:
1. We write the number using only a single non-zero digit before the radix point : e.g., 1011010010001=1.011010010001 x 212
1101.10111 = 1.10110111 x 23
2. Then we transform the number to the following format using 32 bits Ν = (-1)S (1+F)(2E-127)
S: Sign, 0/1 for positives/negatives, respectively
Ε: Exponent. E-127=exp, where exp is the corresponding exponent F: Significant or Mantissa. We write the fractional part in 23 bits
E=127+exp in order to avoid using negative numbers. exp=[-127,128] and therefore E=[0,255] – 255 needs 8 bits

48
0
10001011
01101001000100000000000
Single precision Floating-Point format (2)
Convert the positive number Ν=1011010010001 in Floating point format
Step1: 1011010010001= 1.011010010001 x 212 Step2: Ν = (-1)S (1+F)(2E-127)
S = 0 (positive number)
Ε – 127 = 12, and thus Ε = 13910 and Ε = 100010112 F = 01101001000100000000000
Therefore Ν in FP format is:

49
1
10010001
10001110001000000000000
Single precision Floating-Point format (3)
Suppose that the 32-bit floating-point representation pattern is the following. Find the binary number
S is 1 and thus the number is negative
Ε is 10010001 = 14510, and thus the exponent is exp=Ε-127=145-
127=18
F= 10001110001000000000000
Ν = (-1)S (1+F)(2E-127)
Ν is (-1)1 x 1.10001110001000000000000×218 or Ν = – 1100011100010000000

50
Floating-Point Representation (1)
 No matter how many bits we use in a FP representation, the model is finite
 The real number system is, of course, infinite, so our models can give nothing
more than an approximation of a real value
 e.g., how to represent 33.33333333333333333333?
 At some point, every model breaks down, introducing errors into our calculations
 By using a greater number of bits in our model, we can reduce these errors, but we can never totally eliminate them

51
Why is 0.1+0.2 not equal to 0.3 in most programming languages?
 computers use a binary floating point format that cannot accurately represent a number like 0.110
 0.110 is already rounded to the nearest number in that format
 0.110 doesn’t exist in the FP representation
 0.110 is already rounded to the nearest number in that format, which results in a small rounding error
 This means that 0.110 is converted to a binary number that’s just very close to 0.110
 The error is tiny since 0.110 is 0.1000000000000000055511151231257827
 The constants 0.210 and 0.310 are also approximations to their true values
 So, 0.110 + 0.210 == 0.30000000000000004440892098500610

52
Character Codes
 So far, we have learnt how to represent numbers. How about text?
 To represent text characters, we use character codes
 Essentially, we assign a number for each character we want to represent
 As computers have evolved, character codes have evolved. Larger computer
memories and storage devices permit richer character codes
 Some of the character codes are
1. BCD
2. ASCII (American Standard Code for Information Interchange) (7 bits)
3. Extended ASCII (8-bits)
4. Unicode
5. and others
 A binary number of n bits gives 2n different codes
 For n=2 there are 22 =4 different codes, i.e., bit combinations {00, 01, 10, 11}

53
Binary Coded Decimal (BCD) code
 when numbers, letters or words are represented by a specific group of symbols, it is said that the number, letter or word is being encoded. The group of symbols is called as a code
 Binary Coded Decimal (BCD) code
 In this code each decimal digit is represented by a 4-bit binary
number
 BCD is a way to express each of the decimal digits with a binary code
 In the BCD, with four bits we can represent sixteen numbers (0000 to 1111)
25610 = 0010 0101 0110BCD And vise versa
0011 1000 1001BCD =38910

54
ASCII Code
 The most widely accepted code is called the American Standard Code for Information Interchange ( ASCII).
 The ASCII code associates an integer value for each symbol in the character set, such as letters, digits, punctuation marks, special characters, and control characters
 The ASCII table has 128 characters, with values from 0 through 127. Thus, 7 bits are sufficient to represent a character in ASCII

ASCII Code
55

56
Extended ASCII Characters
 ASCII was designed in the 1960s for teleprinters and telegraphy, and some computing
 The number of printable characters was deliberately kept small, to keep teleprinters and line printers inexpensive
 When computers and peripherals standardized on eight-bit bytes, it became obvious that computers and software could handle text that uses 256-character sets at almost no additional cost in programming, and no additional cost for storage
 An eight-bit character set (using one byte per character) encodes 256 characters, so it can include ASCII plus 128 more characters
 The extra characters represent characters from foreign languages and special symbols for drawing pictures

A set of codes that extends the basic ASCII set. The extended ASCII character set uses 8 bits, which gives it an additional 128 characters
57

58
UNICODE
 Many of today’s systems embrace Unicode that can encode the characters of every language in the world
 The Java programming language, and some operating systems now use Unicode as their default character code
 UTF-8 (8-bits: essentially the extended ASCII Table)
 UTF-16 (16 bits: Most spoken languages in the world, widely
used)
 UTF-32 (32 bits: includes past languages, space inefficient)

59
Any questions?