Transcript EECC250 - Shaaban

Number Systems
• Standard positional representation of numbers:
An unsigned number with whole and fraction portions is
represented as:
an an1an2 an3 a1a0 .a1a1a2 a3 
The value of this number is given by:
N  an  b  an 1  b
n
n 1
1
  a0  b  a1  b  
0
• Where “b” is the base of the number system (e.g 2, 8, 10,
16) and “a” is a digit that range from 0 to b-1
• The "radix point" is used to separate the whole number
from the fractional portion. In base 10, this is the decimal
point; in base 2, the binary point.
EECC250 - Shaaban
#1 Lec # 0 Winter99 11-29-99
Number Systems Used in Computers
Name
of Base
Base
Set of Digits
Example
Decimal
b=10
a= {0,1,2,3,4,5,6,7,8,9}
Binary
b=2
a= {0,1}
Octal
b=10
a= {0,1,2,3,4,5,6,7}
Hexadecimal
b=16
a= {0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F} $FF16
Decimal 0 1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
Hex
Binary
2
3
4
5
6
7
8
9
A
0 1
0000 0001 0010
25510
%111111112
3778
B
C D E F
0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
EECC250 - Shaaban
#2 Lec # 0 Winter99 11-29-99
Converting from Decimal to Binary
An Example:
EECC250 - Shaaban
#3 Lec # 0 Winter99 11-29-99
Algorithm for Converting from Decimal to Any Base
•
•
•
Separate the number into its whole number (wholeNum) and fractional
(fracNum) portions.
Convert the whole number portion by repeating the following until
"wholeNum" is 0:
The "digit" resulting from each step is the
next digit under the new base starting
digit = wholeNum % base;
with position 0 to the left of the decimal
wholeNum /= base;
point.
Convert the fractional portion by repeating the following until "fracNum"
is 0 or sufficient precision has been reached:
fracNum *= base;
digit = (int)base;
fracNum -= base;
•
The "digit" resulting from each step is
the next digit under the new base
starting with position 0 to the right of
the decimal point.
The final answer is the whole number and fractional computation result
separated by a radix point.
EECC250 - Shaaban
#4 Lec # 0 Winter99 11-29-99
Algorithm for Converting from Any Base to Decimal
• Separate the number into its whole number (wholeNum) and
fractional (fracNum) portions.
• Convert the whole number portion by starting at the left end
advancing to the right where "wholeNum" is initially set to 0:
wholeNum = wholeNum * base + digit
– Example: 310716 to decimal
0
(3*16)
(49*16)
(748*16)
+3 = 0 + 3 = 3
+ 1 = 48 + 1 = 49
+ 0 = 784 + 0 = 748
+ 7 = 12544 +7 = 1255110
• Convert the fractional portion by starting at the right end and
advancing to the left where "fracNum" is initially set to 0:
fracNum = (fracNum + digit) / base;
• The final answer is the sum of the whole number and fractional parts.
EECC250 - Shaaban
#5 Lec # 0 Winter99 11-29-99
Algorithm for Converting Between Arbitrary Bases
• If the old base is base 10, then use the approach already
defined above for converting from base 10 to the new base.
• If the new base is base 10, then use the approach already
defined for converting from any base to base 10.
•
If neither the old or new base is base 10, then:
– Convert from the current base to base 10.
– Convert from base 10 to the new base.
EECC250 - Shaaban
#6 Lec # 0 Winter99 11-29-99
Binary to Hexadecimal Conversion
• Separate the whole binary number portion into groups of
4 beginning at the decimal point and working to the left.
Add leading zeroes as necessary.
• Separate the fraction binary number portion into groups
of 4 beginning at the decimal (actually binary) point and
working to the right. Add trailing zeroes as necessary.
• Convert each group of 4 to the equivalent hexadecimal
digit.
• Example:
3564.87510 = 1101 1110 1100.11102
= (D * 162) + (E*161) + (C*160)+(E*16-1)
= DEC.E16
EECC250 - Shaaban
#7 Lec # 0 Winter99 11-29-99
Binary to Octal Conversion
• Separate the whole binary number portion into groups of
3 beginning at the decimal point and working to the left.
Add leading zeroes as necessary.
• Separate the fraction binary number portion into groups of
3 beginning at the decimal (actually binary) point and
working to the right. Add trailing zeroes as necessary.
• Convert each group of 3 to the equivalent octal digit.
• Example:
3564.87510 = 110 111 101 100.1112
= (6 * 83) + (7*82) + (5*81)+(4*80)+(7*8-1)
= 6754.78
EECC250 - Shaaban
#8 Lec # 0 Winter99 11-29-99
Binary Coded Decimal (BCD)
• Binary Coded Decimal (BCD) is a way to store decimal numbers
in binary. This technique uses 4 bits to store each digit from
from 0 to 9. For example:
9810 = 1001 1000 in BCD
• BCD wastes storage since 4 bits are used to store 10 combinations
rather than the maximum possible 16.
• Arithmetic is more complex to implement in BCD.
•
BCD is frequently used in calculators.
• Processors may have special instructions to aid BCD calculations.
EECC250 - Shaaban
#9 Lec # 0 Winter99 11-29-99
Signed Binary Numbers
• Sign and Magnitude Representation:
– For an n-bit binary number:
Use the first bit (most significant bit, MSB) position to
represent the sign where 0 is positive and 1 is negative.
– Remaining n-1 bits represent the magnitude which may
range from:
-2(n-1) + 1 to 2(n-1) - 1
– This scheme has two representations for 0; i.e., both positive
and negative 0: for 8 bits: 00000000, 10000000
– Arithmetic under this scheme uses the sign bit to indicate the
nature of the operation and the sign of the result, but the sign
bit is not used as part of the arithmetic.
EECC250 - Shaaban
#10 Lec # 0 Winter99 11-29-99
Signed Binary Numbers
Complementary Representation:
– No sign digit or bit used
– The complement (negative representation) of an n-digit
number is defined as:
basen - number
– To obtain two’s Complement representation of an n-bit
binary number:
2n - number = 2n - 1 + number + 1
= (1111…111) + number + 1
or
– Invert each bit
– Add 1 to the result
EECC250 - Shaaban
#11 Lec # 0 Winter99 11-29-99
Properties of Two's Complement Numbers
• X plus the complement of X equals 0.
• There is one unique 0.
• Positive numbers have 0 as their leading bit (MSB);
while negatives have 1 as their MSB.
• The range for an n-bit binary number in 2’s
complement representation is:
from -2(n-1) to 2(n-1) - 1
• The complement of the complement of a number is the
original number.
• Subtraction is done by addition to the complement of
the number.
EECC250 - Shaaban
#12 Lec # 0 Winter99 11-29-99
Examples of Two’s Complement Addition
For n = 8 bits
Decimal
Binary
11 =
00001011 =
+ 21 = + 00010101 =
32
=
11 =
- 21 =
- 10 =
00100000 =
Hex
000B
+ 0015
21
- 11
0020
10
00001011 =
000B
+ 11101011
+ FFEB
11110110 =
Decimal
FFF6
Binary
=
00010101 =
= + 11110101 =
=
00001010 =
Hex
0015
+ FFF5
000A
- 11 =
11110101 =
FFF5
- 21 = + 11101011 = + FFEB
- 32 = 1 11100000 =
FFE0
EECC250 - Shaaban
#13 Lec # 0 Winter99 11-29-99
Two’s Complement Arithmetic Overflow
• Arithmetic overflow occurs with two's complement number addition if:
– The operands have the same sign (either positive or negative).
– The answer has a different sign.
• The overflow (V) may be represented algebraically by the following
equation:
____ ___
___
V = an-1 bn-1 sn-1 + an-1 bn-1 sn-1
• Consider 5-bit two's complement, the valid range of numbers is -16 to
+15. Consider the following overflow situations:
+12 01100
-12 10100
+13 01101
-13 10011
------ ------------ --------11001 = -7
00111 = +7
Overflow
Overflow
EECC250 - Shaaban
#14 Lec # 0 Winter99 11-29-99
What Values Can Be Represented in N Bits?
•
•
•
•
•
Unsigned:
0
2s Complement:
- 2 N-1
1s Complement: -2 N-1 +1
BCD
0
For 32 bits:
Unsigned:
2s Complement
2s Complement
BCD
0
- 2,147,483,648
- 2,147,483,647
0
to
to
to
to
2N - 1
2 N-1 - 1
2 N-1 - 1
10 N/4 - 1
to
to
to
to
4,294,967,295
2,147,483,647
2,147,483,647
99,999,999
• But, what about?
– Very large numbers?
9,369,396,989,487,762,367,254,859,087,678
– . . . or very small number?
0.0000000000000000000000000318579157
EECC250 - Shaaban
#15 Lec # 0 Winter99 11-29-99
Scientific Notation
Exponent
Decimal point
25
5.04 x 10
-24
- 1.673 x 10
Sign, Magnitude
Mantissa
Sign,
Radix (base)
Magnitude
EECC250 - Shaaban
#16 Lec # 0 Winter99 11-29-99
Representation of Floating Point Numbers in
Single Precision
IEEE 754 Standard
Value = N = (-1)S X 2 E-127 X (1.M)
0 < E < 255
Actual exponent is:
e = E - 127
Example:
1
sign S
8
E
23
M
exponent:
excess 127
binary integer
added
0 = 0 00000000 0 . . . 0
Magnitude of numbers that
can be represented is in the range:
Which is approximately:
mantissa:
sign + magnitude, normalized
binary significand with
a hidden integer bit: 1.M
-1.5 = 1 01111111 10 . . . 0
2
-126
(1.0)
1.8 x 10
- 38
127
(2 - 2 -23 )
to
2
to
3.40 x 10
38
EECC250 - Shaaban
#17 Lec # 0 Winter99 11-29-99
Representation of Floating Point Numbers in
Double Precision
IEEE 754 Standard
Value = N = (-1)S X 2 E-1023 X (1.M)
0 < E < 2047
Actual exponent is:
e = E - 1023
Example:
1
sign S
11
E
52
M
mantissa:
sign + magnitude, normalized
binary significand with
a hidden integer bit: 1.M
exponent:
excess 1023
binary integer
added
0 = 0 00000000000 0 . . . 0
Magnitude of numbers that
can be represented is in the range:
Which is approximately:
2
-1.5 = 1 01111111111 10 . . . 0
-1022
(1.0)
- 308
2.23 x 10
1023
(2 - 2 - 52 )
to
2
to
1.8 x 10
308
EECC250 - Shaaban
#18 Lec # 0 Winter99 11-29-99
IEEE 754 Special Number Representation
Single Precision
Double Precision Number Represented
Exponent
Significand
Exponent
Significand
0
0
0
0
nonzero
0
nonzero
1 to 254
anything
1 to 2046
anything
Floating Point Number
255
0
2047
0
Infinity
255
nonzero
2047
0
0
nonzero
Denormalized number
NaN (Not A Number)
EECC250 - Shaaban
#19 Lec # 0 Winter99 11-29-99
Basic Floating Point Addition Algorithm
Addition (or subtraction) involves the following steps:
(1) Compute exponent difference: Ye - Xe
(2) Align binary point: right shift Xm that many positions to form Xm 2 Xe-Ye
(3) Compute sum of aligned mantissas:
Xm2 Xe-Ye + Ym
(4) If normalization of result is needed, then a normalization step follows:
• Left shift result, decrement result exponent (e.g., 0.001xx…) or
• Right shift result, increment result exponent (e.g., 101.1xx…)
Continue until MSB of data is 1 (NOTE: Hidden bit in IEEE Standard)
(5) If result mantissa is 0, may need to set the exponent to zero by a special step.
EECC250 - Shaaban
#20 Lec # 0 Winter99 11-29-99
Start
(1)
(2)
(3)
(4)
(5)
Compare the exponents of the two numbers
shift the smaller number to the right until its
exponent matches the larger exponent
Floating Point
Addition
Add the significands (mantissas)
Normalize the sum, either shifting right and
incrementing the exponent or shifting left
and decrementing the exponent
Overflow or
Underflow ?
Generate exception
or return error
If mantissa =0
set exponent to 0
Done
EECC250 - Shaaban
#21 Lec # 0 Winter99 11-29-99
Logical Operations on Binary Values: AND, OR
AND, *, 
A B A AND B
0 0
0
0 1
0
1 0
0
1 1
1
Bitwise AND operation of two
numbers
Example:
A AND B
A 11011010 AND
B 01001101
= 01001000
OR , +, 
A B A OR B
0 0
0
0 1
1
1 0
1
1 1
1
Bitwise OR operation of two
numbers
Example:
A OR B
A 11011010 OR
B 01001101
= 11011111
EECC250 - Shaaban
#22 Lec # 0 Winter99 11-29-99
Logical Operations on Binary Values: XOR, NOT
Exclusive OR, EOR, XOR, 
A B A XOR B
0 0
0
0 1
1
1 0
1
1 1
0
Bitwise XOR operation of two
numbers
Example: A XOR B
A
B
=
__
NOT, ~, X
Inverts or complements a bit
Example:
A = 1101100
__
A = 0010011
1101101 0 XOR
01001101
10010111
EECC250 - Shaaban
#23 Lec # 0 Winter99 11-29-99