Transcript n301SwitchPartTwo - Department of Computer and Information

The Switch, Part 2
CSCI N301: Fundamental Computer
Science Concepts
Copyright ©2004  Department of Computer & Information Science
Goals
By the end of this unit, you should
understand …
• How to perform binary addition and
subtraction
• How computers represent signed numbers
(positive and negative)
• How to use Twos Complement
• How to represent a number using
Scientific Notation.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Review
• The engineering decision to use simple,
two-state switches to build computers
forced computers to “think” in binary.
• How do we convert to and from binary?
• What about octal?
• What about hexadecimal?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Arithmetic
• Computer processing requires a little
more capability in binary math,
notably arithmetic.
• Let’s consider addition and
subtraction …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
• Just a few combinations are
possible:
– 02 + 02 = 02
– 02 + 12 = 12
– 12 + 02 = 12
• What about 12 + 12?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
12 + 12 = 102
• Remember what that 10 means: it
means a zero in the right column, and a
one in the left column
• When you carry in base two, you are
bringing a power of two to the left…
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
1+ 1+
11102
+10112
=1410
110012
=2510
=1110
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Subtraction
• Subtraction in base two is similar to
addition
– 112 – 112 = 002
– 112 – 002 = 112
– 102 – 002 = 102
• What about 102 - 12?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
102 - 12 = 12
• Think about borrowing in decimal – you are
really borrowing a power of your base …
• In Base-10, we borrow 10 from the left
column and give it to the next column to the
right. So …
• In Base-2, we borrow 2 from the left column
and give it to the next column to the right.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
0
1
0
1
1
001100112
-000101102
0 0 0 1 1 1 01 2
=5110
=2210
=2910
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Borrowing: A Little Trick
• Many students find it convenient to just mentally
convert the binary number to decimal, complete
the subtraction, and then convert the answer
back to binary.
• Consider 102 – 12 = ?
– A one in binary is still a one in decimal
– When you borrow for the zero, you bring over a power of two,
which is equal to two
– The decimal conversion for the borrowing is 2-1, which is 1
– And 110 = 12
• Be sure to add your answer back up as a check
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Negative Numbers
• We have mastered binary math for
positive integers
• But what about negative numbers?
• Handling the negative sign has
proven somewhat problematic, as we
will see …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Negative Integers:
Sign/Magnitude Notation
• The first solution for encoding negative numbers
in binary form was to dedicate a switch (which
we now know is a memory location) to
communicate whether a number was positive or
negative
• The only thing required was to agree, in the
bank of switches representing the number,
which switch referred to the sign
• In one of the more popular encoding notations
for negative numbers, the first switch is the sign.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Negative Integers:
Sign/Magnitude Notation
• A 0 setting means the number is positive, a 1 setting
means the number is negative.
• This encoding scheme (for signed integers) is called
sign/magnitude notation.
• The first switch is the sign, the remaining switches
represent the binary magnitude of the number.
• Which highlights one of our key concepts about binary
encoding – the leftmost digit could be a negative sign, or
a “one” in magnitude
• The computer must be told which interpretation/decoding
scheme to use
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sign/Magnitude: The Problem
• What was wrong with this scheme?
– Great for all numbers except 0 …
– This encoding scheme allows you to come up with 2 distinct
encoding schemes for 0, one with a positive sign, and one with
the negative sign
– The one with the negative sign has no mathematical meaning,
and the ambiguity of two patterns representing the same number
is problematic.
• So, most computers use a different scheme than
sign/magnitude for representing negative
integers …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Twos Complement
• Twos Complement solves the
ambiguity problem.
• The scheme works because we are in
binary math, which has only 2 digits.
• Offsetting one moves you to the only
other possible digit, etc.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Twos Complement
• In Twos Complement, you encode positive
integers normally.
• To use Twos Complement for negatives:
– Complement every digit in the number (change 1s to
0s and 0s to 1s)
– Add 1 to the complemented number
• Example:
–101 = 010 + 1 = 011
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Twos Complement: Math
• Twos Complement allows us to add the
representation and processing of negative
integers to our growing computing capability.
• To add a positive and negative number, first
perform the twos complement trick on the
negative number, and then add normally.
• To add two negative numbers, first encode both
of them in 2’s complement, and then add
normally.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
What about fractional values?
• Our goal is to learn how to encode all
numbers in a way that they can be
represented using switch settings
– We can encode positive integers
– We can encode negative integers
• But what about decimal numbers
(numbers with fractional values)?
• To store decimal numbers, most
computers utilize scientific notation …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Math and Scientific Notation
• As a civilization, we now work with
numbers so big and so small that
mathematicians have already had to
wrestle with creating a manageable
notation.
• Scientists developed scientific notation as
a standard way to represent numbers.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Math and Scientific Notation
• Consider the following example:
+/-5.334 * 10+/-23
• The 5.334 part is the mantissa.
• The 10 part is the base.
• The 23 part is the exponent.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Scientific Notation
• Let’s move up a level of abstraction to the
more generalized case of scientific
notation:
+/- M * B+/-E
–
–
–
–
M is the mantissa.
B is the base.
E is the exponent.
+/- means the number can be positive or negative.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Switch Math: the Holes
• If we can figure out how to use
scientific notation to encode base ten
decimal numbers in a binary form of
scientific notation, we can represent
any finite number in our computer and
our switch math will be complete …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Interpreting Scientific Notation
• It turns out that handling scientific notation,
or any other encoding scheme, is
amazingly simple
– We design the computer to know which interpretation
scheme to use!
– We will just figure out how to program in some logic
that says “if a number is tagged as being in scientific
notation, just use a look up chart to interpret the
number.”
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Interpreting Scientific Notation
• Given an encoded number, to decode it such
that it is in scientific notation, you would need to
know several things –
– How big is the overall memory allocation (how many
switches were used)?
– How many switches are dedicated to the mantissa,
and which are they?
– How many switches are dedicated to the exponent,
and which are they?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
One Last Thing!
• Okay, so we know we will always
need to know the encoding scheme to
interpret scientific notation.
• But, once we know the encoding
scheme for any given computer, we
need to be able to encode in this
scientific notation form …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Fractional Value Numbers
• Consider the decimal (base 10) number: +5.75
• How can we encode this is switches?
• We already know how to do half of the encoding
– the integer part (the numbers to the left of the
decimal point).
• Let’s break the problem into two parts, the left
hand side (of the decimal point) and the right
hand side …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Left Side of a Decimal Number
• Okay, our number is 5.75
• To convert the 510 to ?2:
– Use successive division
Division
Remainder
5/2=2
2/2=1
1/2 =0
1
0
1
510 = 1012
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Right Side of a Decimal Number
• On the left hand side, we divided
successively by 2 to convert
• On the right hand side, we multiply
successively by 2 to convert
– We are multiplying numbers by 2 to “promote” them to
the left hand side of the decimal place.
– Once promoted, we record them as a digit in our
answer.
• This process is called extraction….
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Extraction
STEP ONE: Draw a
table with two
columns. Label the
columns for the
expression and the
extraction,
respectively.
Expression
Extract.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Extraction
STEP TWO: Write
down your original
number and
multiply it by 2. Put
the whole number
part in the
Extraction column.
Expression
Extract.
0.75 * 2 = 1.50
1
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Extraction
STEP THREE: Bring
down the fractional
part (the number to
the right of the
decimal point) and
multiply it by two.
Extract the whole
number, as before.
Repeat until you
extract 0.
Expression
Extract.
0.75 * 2 = 1.50
1
0.50 * 2 = 1.00
1
0.00 * 2 = 0.00
0
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Extraction
STEP FOUR: Read
the extraction
column, from top to
bottom. This
number represents
your binary
equivalent.
Expression
Extract.
0.75 * 2 = 1.50
1
0.50 * 2 = 1.00
1
0.00 * 2 = 0.00
0
0.7510 = 1102
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Both Sides Now
• 5.7510 = 101.1102 This isn’t in scientific
notation yet, but at least we have figured
out how to convert it to binary
• Recall the steps so far:
– Do the problem in halves
– For the left side of the decimal, use successive
division by 2 and read the remainders from bottom to
top
– For the right hand side of the decimal, use successive
multiplication by 2 and read the extractions from top
to bottom
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Try One More …
• Let’s try another problem. This time,
with a number that doesn’t convert to
binary as easily …
• Let’s try this number:
2.5410 = ?2
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Converting
• Remember our algorithm: left side by
successive division, right side by
successive multiplication
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Left Side of 2.54
• 2 by successive division
Division
2/2 = 1
1/0 = 0
Remainder
0
1
Reading the remainders from bottom to top,
210 = 102
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Right Side of 2.54
• Reading the extraction
column, top to bottom:
.5410 = 1000101002
• What would have if we
kept extracting, past .24 *
2?
• Let’s convert our number
back to Base-10 to see
what happens …
Division
Extraction
.54 * 2 = 1.08
1
.08 * 2 = 0.16
0
.16 * 2 = 0.32
0
.32 * 2 = 0.64
0
.64 * 2 = 1.28
1
.28 * 2 = 0.56
0
.56 * 2 = 1.12
1
.12 * 2 = 0.24
0
.24 * 2 = 0.48
0
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Go Back the Other Way
• Putting 10.1000101002 back to base
10
• Left hand side first, expanded
notation
• 102 = (0 * 20) + (1 * 21) = 0 + 2 = 210
• Now, to convert the right hand side…
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Right Side of a Decimal Number
• Remember, the left hand side represents
powers of two … positive powers of two
• Moving left from the decimal point, we saw the
unit values were 20, 21, 22, 23, 24, etc.
• Doesn’t it seem reasonable that the units to the
right of the decimal represent negative powers
of two?
• Moving from the right of the decimal point, we
will see unit values for 2-1, 2-2, 2-3, 2-4, 2-5, etc.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Okay, But What Does That Mean?
• Exactly what is a number
to a negative power, such
as 2-1, 2-2, 2-3?
• These are numbers you
already know we are just
used to seeing them
written in a different
format:
2 –1
1/21
½
.5
2 –2
1/22
¼
.25
2 –3
1/23
1/8
.125
2-4
1/24
1/16
.0625
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Back to Our Conversion …
•
•
•
•
Remember, we are translating 10.100010100
We finished the left hand side = 102 = 210
Now for the right hand side:
.100010100 =
– (1 * 2-1) + (0* 2-2) + (0* 2-3) + (0* 2-4) + (1* 2-5) + (0* 2-6) +
(1* 2-7) + (0* 2-8) + (0* 2-9)
– Which is equal to ½ + 1/32 + 1/128 (we can throw out the zero terms)
– Which is equal to 69/128 = .539
• Combining both sides, 10.1000101002 = 2.53910
• But we started with 2.54! Why did we get the error?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
The Imprecision of Conversions
• We started with 2.5410, took it to switch
units in binary, and then back to decimal
• Our result was 2.539
• This is a precision error:
– 2.539 / 2.540 = .99, so our percentage error is 1%!!!
• As you might imagine, in large, multi-step
calculations these errors can become
significant enough for you to see if you are
working in a package such as Excel….
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Storing Binary in Scientific Notation
• Remember, we said if we could encode a
decimal number in switch math, we were
good to go.
• Decimal numbers are usually stored in a
binary version of scientific notation.
• If we can take our translation of 2.54, and
store it in a binary version of scientific
notation, we can quit!
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Last Step
• There are several switch encoding
schemes for scientific notation.
• The good news, remember, is that you
(and the computer!) will always have to be
told which encoding scheme to use.
• One common encoding scheme is 16-bit
encoding …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
16 Bit Scientific Notation Encoding
• In 16 bit encoding, 16 bits (or switches)
are allocated to the numeric part of a
number expressed in scientific notation.
• There are a few different flavors of 16 bit
encoding, with a different allocation of
switches between the mantissa and the
exponent.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
One 16 Bit Encoding in Detail
• Remember the parts of a number in scientific
notation? – the mantissa, base and exponent?
• Each is assigned to specific locations in the 16
bit switch pattern. In the variation we are looking
at first:
–
–
–
–
–
Switch 1 = Sign of the mantissa
(Decimal point assumed to go next, but isn’t stored)
Switches 2-10 – next 9 switches are for the mantissa
Switch 11 – Sign of the exponent
Switches 12-16 – next 5 switches are for the exponent
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
16 Bit: More
• What happened to the base? We don’t have to
store that, because it will always be base two,
the binary base from the world of switches
• Don’t need to store the decimal point, because
the encoding scheme will guarantee it is placed
correctly when decoded
• There’s only one problem: our number must be
“normalized” before encoding
– This means that we need to adjust the exponent as
required to insure that the first significant digit is the
first digit to the right of the decimal point
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Normalizing
• Take the number 101.112, which is really
101.11 * 20
• Before we can store this number in scientific
notation, we must normalize it.
• We have to adjust the exponent until the first
significant digit, which is the leftmost 1, is the
first digit to the right of the decimal point.
• In other words, we have to move the decimal
place in our example 3 places to the left, so that
the number become .10111.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Normalizing
• How can we legally do this, without changing the
value of the number?
• Every time you move the decimal place to the
left, you must adjust the exponent by a positive
increment.
• In our case, we moved 3 decimal points to the
left, so our new exponent is 23
• In other words, 101.11 * 20 = .10111 * 23
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Normalizing Examples
• A couple more, to make sure we have
it:
• 1101.11 * 20 = .110111 * 24
• 101.1 * 20 = .1011 * 23
• .01 * 20 = .1 * 2-1
• .001 * 20 = .1 * 2-2
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm
• 1. Convert the base ten number to
base two, one side of the decimal
place at a time
– Left hand side, successive division
– Right hand side, successive multiplication
• In our case, 2.5410 = 10.1000101002
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm (con’t)
• Put number in normalized form
10.100010100 * 20 = .10100010100 * 22
• Determine what the encoding scheme is
• For the sake of our problem , assume the
following 16 bit encoding:
–
–
–
–
1 = Sign of mantissa
2-12 = Mantissa
13 = Sign of exponent
14-16 = Exponent
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm (con’t)
1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 16
4 5
0101 00 0 1 0 1 0 0 0 0 1 0
Using the described notation system, the decimal 2.5410
would be stored in switch binary math as the following
pattern of zeros and ones:
0101000101000010
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Questions?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science