Transcript Today’s Topics - University of Cincinnati

Click toToday’s
edit Master
title
style
Topics
• Click to edit Master text styles
• How information is encoded
– Second level
– signed •magnitude
Third level
– 1s complement
– Fourth level
» Fifth level
– 2s complement
• Base conversion
• Arithmetic and logical operations
1
Click
to
edit
Master
title
style
Symbolic Representation of Voltage
• Click
edit
text styles
• Devices
that to
react
to Master
presence/absence
of
voltage–(within
tolerance) are easier to
Secondalevel
build than•devices
that react to a specific
Third level
voltage
– Fourth level
» Fifth level
• We use 1 and 0 for presence/absence
• bit = binary digit
• 8 bits = 1 byte
2
Click toPositional
edit Master
title
style
Notation
• Click to edit Master
text styles
1
• 1 position: 0 or 1 (2 )
– Second level
• Third level
2
• 2 positions:–00,
01,
Fourth
level10, 11 (2 )
» Fifth level
• 3 positions: 000, 001, 010, 011, 100,
101, 110, 111 (23)
A single wire can represent only one
thing, a collection of k them can
represent (2k) different things
3
Click to edit
Master
title
style
Data Types
• Click to edit Master text styles
• A data type is a set of values and
– Second level
operations
over
those
values
• Third level
– Fourth level
» Fifth level
– ASCII codes for keyboard characters
– 2s complement integers
– others will be illustrated
4
Click Binary
to edit
Master
title
style
or Base-2 Integers
• Click to edit Master text styles
• Decimal representation
– Second level
• 107 = 1x100+0x10+7
• Third level
1+ level
Fourth
• d2·102+ d1–·10
d0·100
» Fifth level
• Binary representation
• 107 = 01101011
• 0·27+ 1·26+ 1·25+ 0·24+ 1·23+ 0·22+ 1·21+
1·20
• a7·27+ a6·26+ a5·25+ a4·24+ a3·23+ a2·22+
a1·21+ a0·20
5
Click toInteger
edit Master
title
style
Data Types
• Click to edit Master text styles
• Unsigned integers: non-negative values
– Second
level
k
from 0 to• 2Third
-1 for
k
bits
level
– Fourthuse
level half of the 2k
• Signed integers:
» Fifth level
values for positive
and half for negative
– signed magnitude: leading bit represents
the sign (0=positive) and remaining bits
are the value
– 1s complement: flip bits for negative value
– 2s complement: 1s complement + 1
6
Click to edit
Master
title
style
1s Complement
• Click to edit Master text styles
• Flip bits to represent negative values:
– Second level
• Third level
– Fourth
4 islevel
0100
» Fifth level
-4 is 1011
• Basic logic circuits for signed
magnitude and 1s complement are
more complex than 2s complement
7
Click
to
edit
Master
title
style
Motivation for 2s Complement
• Click to edit Master text styles
• From a device standpoint, it would be nice if
levelthe representation for 0
adding–xSecond
to -x yields
level circuits that don’t care
… then we• Third
can build
– Fourth
level
if the operands
are positive
or negative
» Fifth level
• Binary addition:
00011
00110
01001
8
ClickComputing
to edit Master
title
style
2s Complement
Click value
to editfor
Master
textintegers
styles
• Use• binary
positive
– Second level
• Compute representation for negative
level
integers: • Third
– Fourth level
– take 1s complement
» Fifth level
– add 1
• Example: what is 9 in binary?
– what is its 1s complement value?
– what is 1 + 1s complement value?
– What do you get when you sum 9 and -9 in
binary?
9
Click
to
edit
Master
title
style
Binary to Decimal Conversion
• Click to edit Master text styles
– Second level
• Represent values from -2k-1 to 2k-1-1 with k
• Third level
bits
– Fourth level
» Fifth level
• Algorithm:
– if the leading bit is 1, apply 2s complement to
obtain the magnitude of the negative number
– sum the powers of 2 with coefficients of 1
10
Click
to
edit
Master
title
style
Decimal to Binary Conversion
• For•positive
do the computation
Click numbers,
to edit Master
text styles
below –and
prefixlevel
with a leading 0
Second
• For negative
numbers,
• Third
level use the absolute value
in the computation
below, add a leading 0,
– Fourth level
and take the 2s complement
» Fifth level
• Algorithm:
– divide 2 into the dividend, write the
remainder on the right
– the quotient becomes the new dividend;
repeat until the quotient is 0
– read the binary number from the bottom up
11
Click
to edit
Master
title style
Decimal
to Binary
Conversion
•
Example
• Click to edit Master text styles
Lets convert –124 to 8-bit 2’s complement binary
representation
– Second level
1) |-124|•=Third
124 level
2) Compute –binary
of 124
Fourthrepresentation
level
3) Add leading 0» and
2’s complement
Fifthcompute
level
2) 1242=62 remainder 0
3)
01111100
10000011
10000100
62  2=31 remainder 0
31  2=15 remainder 1
15  2=7 remainder 1
7  2=3 remainder 1
3  2=1 remainder 1
1111100
1  2=0 remainder 1
12
Click
to
edit
Master
title
style
Operations on Bits: Arithmetic
• Click to edit Master text styles
– Second level
• Third
level already … so we can
• We can do
addition
– Fourth level
do subtraction,» too
Fifth level
a - b = a + -b
• Compute the 2s complement of b, add it
to a
13
Click to edit
Master
title
style
Sign Extension
• Click to edit Master text styles
• To add –two
numbers
Second
levelof different sizes, it is
necessary to
makelevel
them the same length
• Third
– Fourth level
» Fifth level
• For positive numbers, pad with leading 0s
• For negative numbers, pad with leading 1s
• Does not change the values!
14
Click to editOverflow
Master title style
• Happens
when
of twotext
positive
• Click
to the
editsum
Master
styles
numbers
is largerlevel
than the largest possible
– Second
positive number
• Third level
• Or alternately,– Fourth
the sum
of two negative
level
numbers is smaller
than
the smallest possible
» Fifth
level
negative number
• We check to see if we get a negative value
when adding two positive numbers, or vice
versa
• Why is there never an overflow with the sum
of a positive and negative value?
15
Click
to
edit
Master
title
style
Operations on Bits: Logical Ops
• Click
edit Master
textOR,
styles
• Basic
logic to
functions:
AND,
NOT,
XOR – Second level
• Third level
• Result from–treatment
Fourth level of 0 as FALSE and 1
as TRUE
» Fifth level
• Truth tables: consider all possible
combinations of input values and shows
output values in last column
• For n inputs, there are n+1 columns and 2n
rows
16
Click
to
edit
Master
title
style
Truth table for the AND operator
• Click to edit Master text styles
a level
– Second
• Third
0 level
b
0
– Fourth level
0 » Fifth level1
a AND b
0
0
1
0
0
1
1
1
17
Click toLogical
edit Master
title
style
Operations
•
•
•
•
• Click to edit Master text styles
AND: true when both inputs are 1, else false
– Second level
OR: true when
either
• Third
level input is 1, else false
Fourth
level are the same, else true
XOR: false if –both
inputs
» Fifth level
NOT: invert/complement
input
• All ops can be applied to an entire bitstring
(NOT) or pair of bitstrings (AND, OR, XOR) by
corresponding positions
18
Click to edit
Master
title
style
Logic Functions
• Click to edit Master text styles
– Second
level
• Used for
comparisons,
e.g., if two integers
• Thirdthe
level
are identical,
output of XOR is all 0s
– Fourth level
» Fifth level
• Basis for implementing all of the
computer’s functionality!
19
Click toOther
editRepresentations
Master title style
• Click to edit Master text styles
– Second
• Floating
point: level
real numbers using
• Third
level
normalized
scientific
notation
– Fourth level
• ASCII: 256 possible
symbols (keyboard
» Fifth level
input)
• Hexadecimal: base 16
– each group of 4 bits is a hex digit
– convenience for humans
20