程序代写代做代考 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
