Transcript Some “facts” about software…

Data Representation – Chapter 3
Sections 3-2, 3-3, 3-4
Homework Assignment
• Questions/Requests/Comments/Concerns?
Number Range
• What is meant by “range”?
• How do you compute the range of a
given set of digits?
More Representations
• Integer values are represented by a
power series regardless of radix (base)
1410 = 1 x 101 + 4 x 100
11102 = 1 x 23 + 1 x 22 + 1 x 21 + 0 x 20
• What about fractions?
Fraction Representations
• Same principle applies
14.3710 = 1 x 101 + 4 x 100 + 3 x 10-1 + 7 x 10-2
“decimal point”
10.112 = 1 x 21 + 0 x 20 + 1 x 2-1 + 1 x 2-2
“binary point”
Fraction Representations
• To convert a decimal fraction to binary
– Multiple decimal fractional part by 2
– Output the integer part
– Repeat until you’ve reached the desired accuracy
.3125
x
2
0.6250
.6250
x
2
1.2500
0.312510 = 0.01012
.2500
x
2
0.5000
.5000
x
2
1.0000
Fraction Representations
• More on binary floating point
representations later (maybe)
Addition
• Decimal number addition
carry
121
+19
40
Addition
• Binary number addition
carries
1
111
10101
+10011
101000
• It works the same way in binary as it
does in decimal
Subtraction
• Decimal number subtraction
borrow
1 1
21
+19
02
Subtraction
• Binary number subtraction
borrow
01
10101
-10011
00010
• It works the same way in binary as it
does in decimal
Subtraction Questions
• What about when a subtraction results
in a negative value?
• How do you represent a negative value
in binary?
• How do you represent a negative value
in decimal?
Negative Numbers
• Decimal
- 27
• Place a “-” in front of the decimal digits
Negative Numbers
• Binary
-11011
• Place a “-” in front of the binary digits
• This is called signed-magnitude
representation
• In the hardware the sign is a designated
bit where 0 means “+” and 1 mean “–”
Negative Numbers
• Signed-magnitude is convenient for
humans doing symbolic manipulations
• It’s not convenient for computer
computations
• Why not?
– Consider subtraction (which is really
addition of a negative number)
Signed-Magnitude Subtraction
21
-17
4
Minuend
Subtrahend
Difference
17
-21
- 4
Minuend
Subtrahend
Difference
Signed-Magnitude Subtraction
if (M >= S)
compute M-S
else
compute S-M
place “-” on difference
• To perform subtraction we must first
perform a comparison!
– Therein lies the inconvenience
Negative Numbers Revisited
• Complement representation
• “(r-1)’s” complement
– Given Nr , an n-digit number of radix r
– “(r-1)’s” complement is (rn – 1) - Nr
“(r-1)’s” complement
• Decimal
1234510
n=5, r=10, N=12345
(105-1)-12345
(100000-1)-12345
99999-12345
87654
– “9’s” complement
“(r-1)’s” complement
• Binary
101102
n=5, r=2, N=10110
(25-1)-10110
(100000-1)-10110
11111-10110
01001
– “1’s” complement
– Note that the result is just an inversion of
the bits of the original number (1/0 and 0/1)
“(r-1)’s” complement
• So, how does this help us do
subtraction?
– It doesn’t really!
– Furthermore the representation of 0 is
ambiguous
0000 “+0”
1111 “-0”
Try it!
Another Complement
• “r’s” complement
– Given Nr , an n-digit number of radix r
– “r’s” complement is “(r-1)’s” complement + 1
(rn – 1) – Nr+ 1
rn – Nr if (Nr != 0)
0
if (Nr == 0)
“r’s” complement
• Let’s concentrate on the 2’s
complement (binary number system)
– “…leaving all least significant 0’s and the
first 1 unchanged, and then replacing 1’s
by 0’s and 0’s by 1’s in all other higher
significant bits.”
• Yeah, right!
– Take the “1’s” complement and add 1
“2’s” Complement
101102
n=5, r=2, N=10110
(25-1)-10110
(100000-1)-10110
11111-10110
01001
1’s complement
+
1
01010
2’s complement
2’s Complement “Subtraction”
Original Problem
0111
-0101
2’s Complement Problem
0111
+1011
10010
Carry Out
Answer
2’s Complement
2’s Complement “Subtraction”
Original Problem
2’s Complement Problem
0101
-0111
0101
+1001
01110
Carry Out
Answer
2’s Complement
2’s Complement “Subtraction”
2’s Complement Problem
2’s Complement Problem
0111
+1011
10010
0101
+1001
01110
Carry Out
Carry Out
Answer
2’s Complement
Answer
2’s Complement
• How do we know the sign of the result?
2’s Complement “Subtraction”
• Recall that we’re doing “fixed bit-length”
math
• When the numbers are “signed” then
the most significant bit (MSB)
represents the sign
– MSB=1 defined as negative
– MSB=0 defined as positive
Sign of the Result?
2’s Complement Problem
2’s Complement Problem
0111
+1011
10010
0101
+1001
01110
Carry Out
Carry Out
Answer
Answer
2’s Complement
2’s Complement
Sign Bit
Sign Bit
Sign of the Result?
• The result is in 2’s complement form
– If the sign bit is 1, take the 2’s complement
of the result to read off the magnitude in
“normal” binary notation
– If the sign bit is 0, the result is in “normal”
binary notation
Overflow
• What if the result is too big?
– Remember, this is fixed bit-length math
– When you add to n-bit numbers the result
may be up to n+1 bits long
Overflow
• When a signed positive number is added to a signed
(2’s complement) negative number an overflow
cannot occur
– The positive number magnitude will only get smaller
• When two signed negative numbers or two positive
numbers are added an overflow may occur
– Magnitude is going to get bigger
• When two signed positive numbers are added, the
sign bit is treated as part of the magnitude of the
number and the end carry (overflow) is not treated as
“overflow”
Overflow
• So, when is that “extra bit” an overflow
and when is it part of the result?
– Check the sign bit and the overflow bit
– If the two are not equal then an overflow
has occurred
– If the two are equal then there is no
overflow
Overflow
• In an overflow condition
– If the numbers are both positive, then the
sign bit becomes part of the magnitude of
the result
– If the numbers are both negative, then the
overflow bit is treated as the sign
• As we’ll see next time (logic gates)
there is a very simple way to detect
overflow
• Questions?
“2’s” Complement
• Is this cheating on the representation of
0 since we handled it with an conditional
statement?
• No! Try it based on the formula only!
• Don’t really need to specify it as two
cases
• I only did it because the book did
“2’s” Complement
• So, how does this help us do
subtraction?
• Addition of a 2’s complement
subtrahend.
– Take 2’s complement of the subtrahend
(negate the subtrahend)
– Add minuend to subtrahend
– Difference is in 2’s complement notation
• Note we’re using a fixed, pre-specified number
of bits
• If the result overflows, just ignore it for now
Other Binary Formats
•
Binary Coded Decimal (BCD)
–
–
–
•
Even parity/Odd parity
–
–
–
–
•
–
Count through a sequence of binary numbers in such a way that only 1 bit at a time
changes
What good is this?
American Standard Code for Information Interchange (ASCII)
–
–
•
For a binary number, count the number of 1’s
If the number is odd, attach an extra “1” for even parity or a “0” for odd parity
If the number is even, attach an extra “0” for even parity or a “1” for odd parity
What good is this?
Gray code
–
•
Convert each decimal digit to its binary representation and store
Requires 4 bits per digit – why?
Forget about BCD arithmetic
Standard set of binary patterns assigned to 256 characters
How many bits comprise the ASCII code?
Unicode
–
–
Up-to-date replacement for ASCII
Various schemes utilizing various bit lengths
Homework
• Textbook pages 89 – 91
– 3-9, 3-10, 3-13, 3-15, 3-16, 3-17, 3-23
– Due beginning of next lecture
• Begin reading Chapter 1