# 程序代写代做代考 algorithm PowerPoint 演示文稿

PowerPoint 演示文稿

CO101

Principle of Computer

Organization

Lecture 03: Arithmetic

Liang Yanyan

澳門科技大學

Macau of University of Science and

Technology

Analog vs. Digital

• Analog Signal

• Vary in a smooth way

over time.

• Analog data are

continuous valued.

• Example: audio, video

2

• Digital Signal

• Maintains a constant

level then changes to

another constant level

(generally operate in one

of the two states).

• Digital data are discrete

value.

• Example: computer data.

Number Systems

• An ordered set of symbols, called digits, with relations defined for

addition, subtraction, multiplication, and division.

• Radix or base of the number system is the total number of the

number system is the total number of digits allowed in the number

system.

• Commonly used numeral systems.

3

Conversion from Decimal Integer

• Step 1: Divide the decimal number by the radix (number

base).

• Step 2: Save the remainder (first remainder is the least

significant digit).

• Repeat step 1 and step 2 until the quotient is zero.

• Result is in reverse order of remainders.

• Exercises:

• Convert 1510 to binary value.

• Convert 1010 to octal value.

4

0010010001001000

Most significant bit (MSB) Least significant bit (LSB)

Machine number representations

• Machine number representations

• Fixed point representation

• Floating point representation

• Fixed point representation

• Numbers can be represented in any base.

• 18910, 6EF16

• Numbers in computer are represented in binary.

• A sequence of 0 and 1, each digit is called a bit.

• 0000 -> 0001 -> 0010 -> 0011 -> 0100 -> 0101 -> …

• In decimal from 0 to 2N-1 for N bits.

• A byte → 8 bits

• A word → 16 bits, 32 bits? (machine dependent)

5

Sign and magnitude

• Unsigned number

• an-1an-2…a0 = an-1x2n-1 + an-2x2n-2+…+ a0x20

• 101 = 1×22 + 0x21 + 1×20 = 5

• For a N-bit number, the range it can represent is

[0, 2N-1]

• Sign and magnitude

• Use the MSB to represent positive or negative

number, e.g. 1 → negative, 0 → positive

• 101 = -1 (since 0x21 + 1×20 = 1, MSB = 1, so it is a

negative number)

• For a N bit number, the range it can represent is

[-(2N-1-1), +(2N-1-1)]

6

Problems of sign and magnitude

• There are two zeros

• 0000 = +0

• 1000 = -0

• Waste resource

• Computer needs an extra step to check the sign

before performing computations.

• E.g. (1001 + 0010) we cannot add them directly.

Two’s complement

• The sign is still indicated by MSB.

• 1 → negative , 0 → positive.

• Negative number is obtained by two steps.

• inverse all bits of the positive number

• add 1

For example, to represent -5 using a 4-bit

representation

We know : 5 = 0101

After inverse all bits: 1010

Plus 1 : +0001

After plus 1 : 1011 → answer!

8

Two’s complement

• Given a number in two’s complement format, what is the

actual value?

Example 1: given 1100, this is a negative number.

We have : 1100

After inverse all bits: 0011

Plus 1 : +0001

We have : 0100 → 4

As a result, 1100 is -4, since the MSB is 1.

Example 2: given 0110, since this is a positive number,

we just calculate the value as unsigned format.

We have : 0110 → 6

9

Two’s complement

• The range for an N-bit representation

• [-2N-1, +2N-1-1]

• E.g. for N=8, the range is [-128, +127]

• Remember to extend the sign when we extend a

number. Consider the case that extends a 4-bit

number to 8 bits (e.g. a computer uses 4 bits,

another one uses 8 bits).

• 0011 → 0000 0011

• 1011 → 1111 1011 (the negative sign is extended)

• If the sign is not extended, 1011 → 0000 1011. After

extension, a negative number becomes positive.

10

32-bit Binary Representations

• 32-bit signed numbers (2’s complement):

11

Addition and subtraction

• Addition of X and Y

• X + Y

• Subtraction

• X – Y = X + (-Y) = X + (inverse of Y) + 1

• Overflow means a number is out of the representation range.

• E.g. unable to represent 1023 using 4 bits

• What situations may cause overflow?

• Addition of two positive numbers, or two negative numbers.

• 0100 + 0100 or 1000 + 1000

• Subtraction of a positive and a negative number.

• 0111 – 1000

• What situations don’t cause overflow?

• Addition of a positive and a negative number

• 0100 + 1111

• Subtraction of two negative numbers, or two positive numbers

• 1000 – 1111 or 0100 – 0111

12

Digital Signal Representation

• Active HIGH

• High voltage means On

• Active LOW

• Low voltage means OFF

13

Logic Gates

14

Truth Table

• A means for describing how a logic circuit’s output

depends on the logic levels present at the circuit’s inputs.

• The number of input combinations will equal 2N for an N-

input truth table.

15

Building a 1-bit Binary Half Adder

• A: input

• B: input

• S: output

• C: output

• Using two half adders

to build a full adder.

16

XOR gate

AND gate

Inputs Outputs

A B C S

0 0 0 0

1 0 0 1

0 1 0 1

1 1 1 0

Building a 1-bit Binary Full Adder

17

How can we use it to build a 32-bit adder?

How can we modify it easily to build an adder/subtractor?

Building 32-bit Adder

• Just connect the carry-out of

the least significant bit FA to

the carry-in of the next least

significant bit and

connect …

• Ripple Carry Adder (RCA)

• Advantage: simple logic, so

small (low cost).

• Disadvantage: slow and lots of

glitching (so lots of energy

consumption).

18

Overflow Detection

• Can detect overflow by:

• Carry into MSB xor Carry out of MSB.

• xor operation:

• 0 xor 0 = 0;

• 1 xor 1 = 0;

• 0 xor 1 = 1;

• 1 xor 0 = 0;

19

Floating Point Representation

• Fixed point representation of fractional number (decimal).

• an-1an-2…a0﹒b1b2…bm = an-1x2n-1 + an-2x2n-2 +…+ a0x20﹒b1x2-1 +

b2x2-2 + … + bmx2-m

• 11.101 = 1×21 + 1×20 + 1×2-1 + 0x2-2 + 1×2-3 = 3.625

• We need a way to represent

– Very small numbers, e.g., .000000001. To represent 2-98 using

fixed point, we need 99 bits.

– Very large numbers, e.g., 3.15576 ∗ 1099. To represent 299-1

using fixed point, we need 99 bits.

20radix (base)

decimal point

Mantissa

exponent

+ 6.02 x 10

23

Scientific Notation

sign

Floating Point Representation

• In mathematics, we have standard (Scientific

Notation) for representing fractional numbers.

• In computer systems, we also need a standard

to represent fractional numbers → IEEE754

floating point format.

• The most widely used standard for floating point

computation.

• Advantages of the standard (IEEE754):

• Simplify exchange of data includes fractional number.

• Simplify floating point arithmetic algorithms.

• Increase accuracy of the numbers that can be stored.

21

Floating Point Representation

• How do computer systems store a fractional number

which is in scientific notation?

• Can you figure out what the number is if I just tell you the

mantissa, exponent, and sign?

• In computer systems, fractional numbers are often

stored using 32-bit space and divide these 32 bits into 3

parts:

• S: store the sign.

• E: store the exponent.

• M: store the mantissa.

• No need to store the base.

22

radix (base)

decimal point

Mantissa

exponent

+ 1.011 x 2

35

S E M

1 8 23

sign

More details

• Scientific notation in binary: +1.011 × 235

• S is the sign bit, 0 means +ve, 1 means –ve

• E is the biased exponent, assume E is N bits.

• E = exponent + bias, e.g. E = 35 + 127

• bias = 2N-1 – 1, bias is 127 for single precision and 1023 for

double precision.

• exponent = E – bias

• M is the normalized binary number with “hidden” leading

‘1’, called significand.

• M = Mantissa – 1, e.g. M = 1.011 – 1 = .011

• Mantissa = 1 + M

23

1 8 23

S E M

1 11 52

S E M

Single precision

Double precision

actual value = (–1)S ∗ (1+M) × 2E – bias

0.7510 = 0.112= 1.12 x 2-1 (normalized)

S = 0 (positive number)

E = exponent + 127 = -1+127 = 126 =01111110

M = Mantissa – 1 = 1.1 – 1 = .10000000000000000000000

32 bits = 00111111010000000000000000000000

= 0x3F400000

Conversion

• Convert –11.510 into Single Precision FP in Hex

• Convert 0.7510 into Single Precision FP in Hex

24

-11.510 = -1011.12=-1.01112 x 23 (normalized)

S = 1 (negative number)

E = exponent + 127 = 3+127 = 130 = 10000010

M = Mantissa – 1 = 1.0111 – 1 = .01110000000000000000000

32 bits = 11000001001110000000000000000000

= 0xC1380000

Conversion

• What is the decimal value of the following IEEE Single

precision number?

25

1 8 bits 23 bits

1 01111110 10000000000000000000000

sign bit S = 1 = negative

E = 01111110 = 126

exponent = E – 127 = 126-127 = -1

significand M = 0.1000….2

Mantissa = 1 + M = 1+0.1000….2 = 1.12

Value = – 1.12 x 2-1 = -0.112 = -(0.5+0.25) = -0.75

Conversion (Exercises)

• Convert single precision FP 0xC0A00000 to decimal

• Convert single precision FP 0x41380000 to decimal

26

0xC0A0000 = 11000000101000000000000000000000

sign = 1 = negative

exponent = E – 127 = 129-127 = 2

Mantissa = 1 + M = 1.012

value = -1.012 x 22 = -1012 = -5

0x41380000 = 01000001001110000000000000000000

sign = 0 = positive

exponent = E – 127 = 130-127 = 3

Mantissa = 1 + M = 1.01112

value = 1.01112 x 23 = 1011.12 = 11.5

Advantages

• For ease of sorting

• 1st bit determine whether the number is positive or

negative.

• Sorting is then based on exponent, a larger exponent

implies the number is bigger.

• For more accuracy

• Observe that after normalization, no leading ‘0’ and

must start with ‘1’, hidden this leading ‘1’ makes the

significand actually 24 bits long (53 bits long for

double precision) → can use more bits to store the

mantissa.

27

Range

• Notice that the IEEE 754 standard reserves the smallest

E (all 0s) and largest E (all 1s) for special purpose. Will

address this issue later.

• Smallest magnitude can be represented

• Smallest E = 00000001 = 1

• Smallest M = 00000000000000000000000

• Smallest magnitude = 1.02 x 2(1-127) ≈ 1.8 x 10 -38

• Largest magnitude can be represented

• Largest E = 11111110 = 254

• Largest M = 11111111111111111111

• Largest magnitude = 1.1112… x 2(254-127) ≈ 3.4 x 1038

• Range the IEEE754 can represent

• (+1.8 x 10 -38 , +3.4 x 1038) and (-3.4 x 1038, -1.8 x 10 -38)

• How about zero and numbers outside these range?

28

Underflow and overflow

29

-1.8 x 10-38-3.4 x 1038 1.8 x 10-38 3.4 x 10380

negative

overflow

negative

underflow

positive

underflow

positive

overflow

Special number

• Representation of Zero

• All 0s in E and M

• +0 and -0 indicated by S (0 mean +)

• Representation of +/- infinity

• E: all 1s, M: all 0s

• +/- indicated by S (0 means +)

• Representation of Not a Number (NaN)

• E: all 1s, M: non zero number

• e.g. sqrt of –ve number

• HW decides what M is

• Denormalized number

• E: all 0s, M: non zero number

• Computers cause exception

30

S 11111111 00000000…0

S 11111111 Non zero

S 00000000 00000000000000000000000

S 00000000 Non zero

Arithmetic Add

31

Start

1. Compare the exponents. Right Shift the smaller

one until its exponent match the larger number

2. Add significands

3. Normalize the sum and shfit the exponent accordingly

Overflow or

underflow?

4. Round significand

Still

normalized?

End

Exception

yes

yes

No

No

• Assume 3 digits significand

and 2 digits exponent

• 6.42 x 101 + 9.51 x 102

1. 6.42 x 101 = 0.642 x 102

2. 0.642+9.51 = 10.152

3. 10.152 x 102 = 1.0152 x 103

(no over/under flow)

4. After rounding, 1.015 x 103

(normalized)

5. Ans : 1.015 x 103

Arithmetic Multiplication

32

Start

1. Get the new biased exponent, by adding E1+E2-bias

2. Multiply significands

3. Normalize the product and shift the exponent accordingly

Overflow or

underflow?

4. Round significand

Still

normalized?

End

Exception

yes

yes

No

No

5. Set the sign to +ve if two no. are in the same sign,

-ve otherwise

• Assume 3 digits significand

and 2 digits exponent

• 8.76 x 101 * 1.47 x 102

1. (1+127)+(2+127) – 127 =

(3+127)

2. 8.76 x 1.47 = 12.8772

3. 12.8772 x 103=1.28772 x 104

(No over/under flow)

4. After rounding, 1.288 x 104

(normalized)

5. Set to +ve

6. Ans : 1.288 x 104

Common Pitfall for FP

• Floating point addition is NOT associative.

• Is (a+b)+c equivalent to a+(b+c)?

• No in some circumstances, but why?

• FP numbers have limited precision, only approximate

result can be stored.

• a = -1.5 x 1038, b = 1.5 x 1038, c = 1.0

• Everyone knows (a+b)+c = a+(b+c) = 1.0 in

mathematics.

• How about do this in C program using float type?

33

Common Pitfall for FP

a = -1.5 x 1038, b = 1.5 x 1038, c = 1.0

• printf (“%f”, (a+b)+c); Result = 1.0

• printf (“%f”, a+(b+c)); Result = 0

• It is nearly no effect for adding a very small number to a

very big number.

• The small number becomes zero when normalizes the

exponents of two numbers (step 1 of addition algorithm).

• Don’t assume associate rule holds for Floating Point

Number! Always avoid adding a very small number to a

very big number first.

34

Common Pitfall for FP

• Case 1

• a = -238, b = 238, c = 1.0

• Is ((a+b)+c) equal to (a+(b+c))?

• Case 2

• a = -228, b = 228, c = 1.0

• Is ((a+b)+c) equal to (a+(b+c))?

• Case 3

• a = -22, b = 22, c = 1.0

• Is (a+b)+c) equal to (a+(b+c))?

• Q1: What is the largest exponent that these two

equations are still equal?

• Q2: What is the smallest exponent that these two

equations are not equal?

35

Decreasing the

exponent.

NOT EQUAL

EQUAL

Common Pitfall for FP

• Equality test may NOT hold for FP.

• Is 10/3*3 equal to 10?

• No, but why?

• Round off errors easily occur during each

intermediate step!

• Not wise to test ‘absolute’ equality of two FP numbers.

36

Common Pitfall for FP

float d;

int e = 10;

d = (10/3)*3;

if (d==e)

printf(“1. equality work!

”);

else

printf(“2. equality not work!

”);

if (d > e)

printf(“3. compare magnitude work!

”);

37

Summary

• Fixed point representation

• Two’s complement

• Floating point representation

• IEEE754

• Conversion between single precision floating

point format and decimal format.

• Addition and multiplication

• Pitfall

38

CO101�Principle of Computer Organization

Analog vs. Digital

Number Systems

Conversion from Decimal Integer

Machine number representations

Sign and magnitude

Problems of sign and magnitude

Two’s complement

Two’s complement

Two’s complement

32-bit Binary Representations

Addition and subtraction

Digital Signal Representation

Logic Gates

Truth Table

Building a 1-bit Binary Half Adder

Building a 1-bit Binary Full Adder

Building 32-bit Adder

Overflow Detection

Floating Point Representation

Floating Point Representation

Floating Point Representation

More details

Conversion

Conversion

Conversion (Exercises)

Advantages

Range

Underflow and overflow

Special number

Arithmetic Add

Arithmetic Multiplication

Common Pitfall for FP

Common Pitfall for FP

Common Pitfall for FP

Common Pitfall for FP

Common Pitfall for FP

Summary