Transcript Ch 1 Powerpoint

Binary Arithmetic
•
•
•
•
Binary addition
Binary subtraction
Binary multiplication
Binary division
1
Complements of Binary
Numbers
• 1’s complements
• 2’s complements
2
Complements of Binary
Numbers
• 1’s complement
• Change all 1s to 0s and all 0s to 1s
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
3
Complements of Binary
Numbers
• 2’s complement
• Find 1’s complement and then add 1
1
1’s complement
2’s complement 0
0
0
1
1
1
0
1
0
1
0
1
0
1
Input bits
Adder
Output bits (sum)
0
1
0
1
0
0
1
1
Carry
In
1
(add 1)
0
4
Signed Numbers
5
Topics for Signed Numbers
• Signed-magnitude form
• 1’s and 2’s complement form
• Decimal value of signed numbers
(How to convert)
• Range of values (max and min)
• Floating-point numbers
6
Signed Numbers
• Signed-magnitude form
– The sign bit is the left-most bit in a signed
binary number
– A 0 sign bit indicates a positive magnitude
– A 1 sign bit indicates a negative magnitude
7
Signed Numbers
• 1’s complement form
– A negative value is the 1’s complement of
the corresponding positive value
• 2’s complement form
– A negative value is the 2’s complement of
the corresponding positive value
8
Signed Numbers
• Decimal value of signed numbers
– Sign-magnitude
– 1’s complement
– 2’s complement
9
Signed Numbers
• Range of Values
Total combinations = 2n
2’s complement form:
– (2n – 1) to + (2n – 1 – 1)
Range for 8 bit number:
n=8
-(28-1) = -27 = -128
minimum
+(28-1) – 1 = +27 - 1 = +127 maximum
Total combination of numbers is 28 = 256.
10
Signed Numbers
Range for 16 bit number:
n = 16
-(216-1) = -215 = -32768
minimum
+(216-1) - 1 = +215 = +32767 maximum
Total combinations is 216 = 65536 (64K)
8 bit examples:
10000000 =
-128
11111111 =
-1
10000001 =
-127
01111111 =
+127
11
Signed Numbers
• Floating-point numbers
– Can represent very large or very small numbers
based on scientific notation. Binary point “floats”.
• Two Parts
– Mantissa represents magnitude of number
– Exponent represents number of places that
binary point is to be moved
• Three forms
–
–
–
–
Single-precision (32 bits)
float
Double-precision (64 bits)
double
Extended-precision (80 bits)
long double
Also have Quadruple and Quadruple extended!
12
Single Precision
32 bits
S
1 bit
Exponent (E)
8 bits
Mantissa (fraction, F)
23 bits
• IEEE 754 standard
– Mantissa (F) has hidden bit so actually has 24
bits. Gives 7 significant figures.
• 1st bit in mantissa is always a one
– Exponent (E) is biased by 127 called
Excess-127 Notation
• Add 127 to exponent so easier to compare
• Range of exponents is -126 to +128
– Sign (S) bit tells whether number is negative or
13
positive
Single Precision
• Example: Convert 577710 to Floating Point
• 1st, convert to binary using divide by 2 method
• 577710 = 10110100100012
• Positive number, so sign bit (S) equals 0.
• 2nd, count number of places to move binary
point
10110100100012 = 1.011010010001 x 212
Add 127 to 12 = 13910 = 100010112
• Mantissa is fractional part, 011010010001
• Finally, put everything together
S
E
0
10001011
F
Fill in with trailing zeroes
01101001000100000000000
14
Special Cases
• Zero and infinity are special cases
– Can have +0 or -0 depending on sign bit
– Can also have +∞ or -∞
• Not a Number (NaN)
– if underflow or overflow
Type
Zeroes
Exponent Mantissa
0
0
Denormalized numbers 0
non zero
e
Normalized numbers
1 to 2 − 2 any
Infinities
2 −1
NaNs
2 −1
e
e
0
non zero
15
Examples
Type
Exponent
Mantissa
Value
Zero
0000 0000
000 0000 0000 0000 0000 0000
0.0
One
0111 1111
000 0000 0000 0000 0000 0000
1.0
Denormalized
number
0000 0000
100 0000 0000 0000 0000 0000
5.9×10
Large normalized
number
1111 1110
111 1111 1111 1111 1111 1111
3.4×10
Small normalized
number
0000 0001
000 0000 0000 0000 0000 0000
1.18×10
Infinity
1111 1111
000 0000 0000 0000 0000 0000
Infinity
NaN
1111 1111
010 0000 0000 0000 0000 0000
NaN
-39
38
-38
16
Double Precision
• Exponent has 11 bits so uses
Excess-1023 Notation
• Mantissa has 53 bits (one hidden)
• 53 bits gives 16 significant figures
17
Arithmetic Operations with
Signed Numbers
•
•
•
•
Addition
Subtraction
Multiplication
Division
18
Arithmetic Operations with
Signed Numbers
Addition of Signed Numbers
• The parts of an addition function are:
– Augend
– Addend
– Sum
- The first number
- The second number
- The result
Numbers are always added two at a time.
19
Arithmetic Operations with
Signed Numbers
Four conditions for adding numbers:
1. Both numbers are positive.
2. A positive number that is larger than a
negative number.
3. A negative number that is larger than
a positive number.
4. Both numbers are negative.
20
Arithmetic Operations with
Signed Numbers
Signs for Addition
• When both numbers are positive, the
sum is positive.
• When the larger number is positive and
the smaller is negative, the sum is
positive. The carry is discarded.
21
Arithmetic Operations with
Signed Numbers
Signs for Addition
• When the larger number is negative and
the smaller is positive, the sum is
negative (2’s complement form).
• When both numbers are negative, the
sum is negative (2’s complement form).
The carry bit is discarded.
22
Examples (8 bit numbers)
• Add 7 and 4 (both positive)
00000111
+00000100
00001011
• Add 15 and -6 (positive > negative)
Discard carry
• Add 16 and -24 (negative > positive)
Sign bit is negative so negative
number in 2’s complement form
• Add -5 and -9 (both negative)
Discard carry
7
+4
11
00001111
+11111010
1 00001001
15
+ -6
9
00010000
+11101000
11111000
16
+ -24
-8
11111011
+11110111
1 11110010
-5
+ -9
-14
23
Overflow
• Overflow occurs when number of bits in
sum exceeds number of bits in addend or
augend.
• Overflow is indicated by the wrong sign.
• Occurs only when both numbers are
positive or both numbers are negative
Sign Incorrect
Magnitude Incorrect
01111101
126
+ 00111010
_________
+ 58
____
10110111
183
24
Arithmetic Operations with
Signed Numbers
Subtraction of Signed Numbers
• The parts of a subtraction function are:
– Minuend
- The first number
– Subtrahend - The second number
– Difference - The result
Subtraction is addition with the sign of the
subtrahend changed.
25
Arithmetic Operations with
Signed Numbers
Subtraction
• The sign of a positive or negative binary
number is changed by taking its 2’s
complement
• To subtract two signed numbers, take
the 2’s complement of the subtrahend
and add. Discard any final carry bit.
26
Subtraction Examples
• Find 8 minus 3.
Discard carry
• Find 12 minus -9.
• Find -25 minus 19.
Discard carry
• Find -120 minus -30.
00001000
+11111101
1 00000101
00001100
+00001001
00010101
11100111
+11101101
1 11010100
10001000
+00011110
10100110
8
- 3
5
Minuend
Subtrahend
Difference
12
- -9
21
-25
- 19
-44
-120
- -30
-90
27
Arithmetic Operations with
Signed Numbers
Multiplication of Signed Numbers
• The parts of a multiplication function are:
– Multiplicand
– Multiplier
– Product
- First number
- Second number
- Result
Multiplication is equivalent to adding a
number to itself a number of times equal to
the multiplier.
28
Arithmetic Operations with
Signed Numbers
There are two methods for multiplication:
• Direct addition
– add multiplicand multiple times equal to the
multiplier
– Can take a long time if multiplier is large
• Partial products
– Similar to long hand multiplication
The method of partial products is the most
commonly used.
29
Arithmetic Operations with
Signed Numbers
Multiplication of Signed Numbers
• If the signs are the same, the product is
positive. (+ X + = + or - X - = +)
• If the signs are different, the product is
negative. (+ X - = - or - X + = -)
30
Multiplication Example
• Both numbers must be in uncomplemented form
• Multiply 3 by -5.
Opposite signs, so product will be negative.
310 = 000000112
-510 = 111110112
2’s complement of -5
00000101
00000011
X 00000101
00000011
+ 0000000
00000011
+ 000011
00001111
Multiplicand
Multiplier
First partial product
Second partial product
Sum of 1st and 2nd
Third partial product
Sum and Final Product
Final result is negative, so take 2’s complement.
11110001 is the result which in decimal is -15.
31
Arithmetic Operations with
Signed Numbers
Division of Signed Numbers
• The parts of a division operation are:
– Dividend
– Divisor
– Quotient
dividend
 quotient
divisor
Division is equivalent to subtracting the
divisor from the dividend a number of
times equal to the quotient.
32
Arithmetic Operations with
Signed Numbers
Division of Signed Numbers
• If the signs are the same, the quotient is
positive.
(+ ÷ + = + or - ÷ - = +)
• If the signs are different, the quotient is
negative. (+ ÷ - = - or - ÷ + = -)
33
Division Example
• Both numbers must be in uncomplemented form
• Divide 01100100 by 00110010.
Both numbers are positive so
quotient will be positive.
Set the quotient to zero initially.
Subtract the divisor from the
dividend by using 2’s complement
addition. (11001110)
Ignore the carry bit.
Subtract the divisor from the
1st partial remainder using 2’s
complement addition.
quotient: 00000000
01100100
+ 11001110
1 00110010
Dividend
2’s complement of Divisor
First partial remainder
Add 1 to quotient: 00000000 + 1 = 00000001
00110010
+ 11001110
1 00000000
First partial remainder
2’s complement of Divisor
zero remainder
Add 1 to quotient: 00000001 + 1 = 00000010
34
So final quotient is 00000010 and final remainder is 00000000
Hexadecimal Numbers
35
Hexadecimal Numbers
• Decimal, binary, and hexadecimal
numbers
• 4 bits is a nibble
• FF16 = 25510
36
Hexadecimal Numbers
• Binary-to-hexadecimal conversion
• Hexadecimal-to-decimal conversion
• Decimal-to-hexadecimal conversion
37
Hexadecimal Numbers
•
Binary-to-hexadecimal conversion
1. Break the binary number into 4-bit
groups
2. Replace each group with the
hexadecimal equivalent
•
Convert 1100101001010111 to Hex
C
•
A
5
7
= CA5716
Convert 10A416 to binary
0001
0000 1010 0100 = 0001000010100100
38
Hexadecimal Numbers
•
Hexadecimal-to-decimal conversion
1. Convert the hexadecimal to groups of 4-bit
binary
2. Convert the binary to decimal
39