Transcript Chapter 02 - Data Types

Chapter 2 - Data Types
Today…


Unit 1 slides and homework in JFSB B115
Problems with CCE on Talmage Window’s
machines…





Drivers have to be installed with administrator
privileges
Ready shortly…
Help Sessions begin Monday @4:00 pm
Reading Assignments on-line under the
Schedule Tab
Concerns or problems??
BYU CS/ECEn 124
Chapter 2 - Data Types
2
Concepts to Learn…









Binary Digital System
Data Types
Conversions
Binary Arithmetic
Overflow
Logical Operations
Floating Point
Hexadecimal Numbers
ASCII Characters
BYU CS/ECEn 124
Chapter 2 - Data Types
3
Digital Binary System
What are Decimal Numbers?

“Decimal” means that we have ten digits to
use in our representation


the symbols 0 through 9
What is 3,546?
3 thousands + 5 hundreds + 4 tens + 6 ones.
3 + 5102 + 4101 + 6100
 3,54610 = 310


How about negative numbers?

Use two more symbols to distinguish positive
and negative, namely, + and -.
BYU CS/ECEn 124
Chapter 2 - Data Types
4
Digital Binary System
What are Binary Numbers?

“Binary” means that we have two digits to
use in our representation


the symbols 0 and 1
What is 1011?
1 eights + 0 fours + 1 twos + 1 ones
3 + 022 + 121 + 120
 10112 = 12


How about negative numbers?
We don’t want to add additional symbols
 So…

BYU CS/ECEn 124
Chapter 2 - Data Types
5
Digital Binary System
Binary Digital System




Binary (base 2) because there are two states, 0 and 1.
Digital because there are a finite number of symbols.
Basic unit of information is the binary digit, or bit.
Bit values are represented by various physical means.






Voltages
Residual magnetism
Light
Electromagnetic Radiation
Polarization
Values with more than two states require multiple bits.

A collection of 2 bits has 4 possible states: 00, 01, 10, 11

A collection of 3 bits has 8 possible states: 000, 001, 010, 011,
100, 101, 110, 111

A collection of n bits has 2n possible states.
BYU CS/ECEn 124
Chapter 2 - Data Types
6
Digital Binary System
Electronic Representation of a Bit

Relies only on approximate physical values.



A logical ‘1’ is a relatively high voltage (2.4V - 5V).
A logical ‘0’ is a relatively low voltage (0V - 1V).
Analog processing relies on exact values which
are affected by temperature, age, etc.



Analog values are never quite the same.
Each time you play a vinyl album, it will sound a bit different.
CDs sound the same no matter how many times you play them.
BYU CS/ECEn 124
Chapter 2 - Data Types
7
Digital Binary System
The Power of the Bit…

Bits rely on approximate physical values that are
not affected by age, temperature, etc.



By using groups of bits, we can achieve high
precision.






Music that never degrades.
Pictures that never get dusty or scratched.
8 bits => each bit pattern represents 1/256.
16 bits => each bit pattern represents 1/65,536
32 bits => each bit pattern represents 1/4,294,967,296
64 bits => each bit pattern represents 1/18,446,744,073,709,550,000
Disadvantage: bits only represent discrete values
Digital = Discrete
BYU CS/ECEn 124
Chapter 2 - Data Types
8
Digital Binary System
Binary Nomenclature





Binary Digit: 0 or 1
Bit (short for binary digit): A single binary digit
LSB (least significant bit): The rightmost bit
MSB (most significant bit): The leftmost bit
Data sizes





1 Nibble (or nybble) = 4 bits
1 Byte = 2 nibbles = 8 bits
1 Kilobyte (KB) = 1024 bytes
1 Megabyte (MB) = 1024 kilobytes = 1,048,576 bytes
1 Gigabyte (GB) = 1024 megabytes = 1,073,741,824
bytes
BYU CS/ECEn 124
Chapter 2 - Data Types
9
Data Types
What Kinds of Data?

All kinds…








Data type:


Numbers – signed, unsigned, integers, floating point,
complex, rational, irrational, …
Text – characters, strings, …
Images – pixels, colors, shapes, …
Sound – pitch, amplitude, …
Logical – true / false, open / closed, on / off, …
Instructions – programs, …
…
representation and operations within the computer
We’ll start with numbers…
BYU CS/ECEn 124
Chapter 2 - Data Types
10
Data Types
Some Important Data Types

Unsigned integers



Signed integers



negative, zero, positive numbers
…, -3, -2, -1, 0, 1, 2, 3, …
Floating point numbers



only non-negative numbers
0, 1, 2, 3, 4, …
numbers with decimal point
PI = 3.14159 x 100
Characters


8-bit, unsigned integers
‘0’, ‘1’, ‘2’, … , ‘a’, ‘b’, ‘c’, … , ‘A’, ‘B’, ‘C’, … , ‘@’, ‘#’,
BYU CS/ECEn 124
Chapter 2 - Data Types
11
Data Types
Unsigned Integers

Weighted positional notation

“3” is worth 300, because of its position, while “9” is
only worth 9
most
significant
329
102 101 100
22
3x100 + 2x10 + 9x1 = 329

least
significant
101
21
20
1x4 + 0x2 + 1x1 = 5
What do these unsigned binary numbers
represent?
0000
0110
BYU CS/ECEn 124
1111
1010
0001
1000
Chapter 2 - Data Types
0111
1100
1011
1001
12
Data Types
Unsigned Integers (continued…)
22
0
0
0
0
1
1
1
1
BYU CS/ECEn 124
21
0
0
1
1
0
0
1
1
20
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
Chapter 2 - Data Types
13
Data Types
Unsigned Binary Arithmetic

Base 2 addition – just like base 10!

add from right to left, propagating carry
carry
10010
+ 1001
11011
10010
+ 1011
11101
1111
+
1
10000
10111
+ 111
11110
Subtraction, multiplication, division,…
BYU CS/ECEn 124
Chapter 2 - Data Types
14
Data Types
Signed Integers

With n bits, we have 2n distinct values.



Positive integers


assign about half to positive integers (1 through 2n-1)
and about half to negative (- 2n-1 through -1)
that leaves two values: one for 0, and one extra
just like unsigned – zero in most significant (MS) bit
00101 = 5
Negative integers



sign-magnitude – set MS bit to show negative
10101 = -5
one’s complement – flip every bit to represent negative
11010 = -5
MS bit indicates sign: 0=positive, 1=negative
BYU CS/ECEn 124
Chapter 2 - Data Types
15
Data Types
Sign-Magnitude Integers

Representations





01111binary
11111
00000
10000
=> 15decimal
=> -15
=> 0
=> -0
The left-bit encodes
the sign:
0 = +
1 = -
Problems

Difficult addition/subtraction



check signs
convert to positive
use adder or subtractor as required
BYU CS/ECEn 124
Chapter 2 - Data Types
16
Data Types
1’s Complement Integers

Representations





00110binary
11001
00000
11111
=> 6decimal
=> -6
=> 0
=> -0
Problem

To negate a number,
Invert it, bit-by-bit.
The left-bit still
encodes the sign:
0 = +
1 = -
Difficult addition/subtraction


no need to check signs as before
cumbersome logic circuits

BYU CS/ECEn 124
end-around-carry
Chapter 2 - Data Types
17
Data Types
2’s Complement

Problems with sign-magnitude and 1’s
complement


two representations of zero (+0 and –0)
arithmetic circuits are complex



How to add two sign-magnitude numbers?
e.g., try 2 + (-3)
How to add to one’s complement numbers?
e.g., try 4 + (-3)
Two’s complement representation
developed to make circuits easy for
arithmetic.
BYU CS/ECEn 124
Chapter 2 - Data Types
18
Data Types
2’s Complement (continued…)

Simplifies logic circuit construction
because



addition and subtraction are always done
using the same circuitry.
there is no need to check signs and convert.
operations are done same way as in decimal



right to left
with carries and borrows
Bottom line: simpler hardware units!
BYU CS/ECEn 124
Chapter 2 - Data Types
19
Data Types
2’s Complement (continued…)

If number is positive or zero,


normal binary representation
If number is negative,



start with positive number
flip every bit (i.e., take the one’s complement)
then add one
00101 (5)
11010 (1’s comp)
+
1
11011 (-5)
BYU CS/ECEn 124
01001 (9)
10110 (1’s comp)
+
1
10111 (-9)
Chapter 2 - Data Types
20
Data Types
2’s Complement (continued…)

Positional number representation with a twist

the most significant (left-most) digit has a negative
weight
22
21
- 2n-1 2n-2  21 20
0110 =
+
= 6
1110 = -23 + 22 + 21 = -2


n-bits represent numbers in the range -2n-1 … 2n-1 - 1
What are these?
0000
0110
1111
1010
0001
BYU CS/ECEn 124
1000
0111
1100
1011
1001
Chapter 2 - Data Types
21
Data Types
2’s Complement Shortcut

To take the two’s complement of a
number:


copy bits from right to left until (and including)
the first “1”
flip remaining bits to the left
011010000
100101111
+
1
100110000
BYU CS/ECEn 124
011010000
(1’s comp)
(flip)
(copy)
100110000
Chapter 2 - Data Types
22
Data Types
2’s Complement Negation

To negate a number, invert all the bits and add 1
Number
0110
0111
0000
1111
0100
1000
BYU CS/ECEn 124
Decimal Value
Negated Binary Value
6
7
0
-1
4
-8
1010
1001
0000
0001
1100
1000
Chapter 2 - Data Types
(??)
23
Quiz
00100110 (unsigned int)
+ 10001101 (signed magnitude)
+ 11111101 (1’s complement)
+ 00001101 (2’s complement)
+ 10111101 (2’s complement)
(decimal)
BYU CS/ECEn 124
Chapter 2 - Data Types
24
Quiz
+
+
+
+
00100110
10001101
00011001
11111101
00010111
00001101
00100100
10111101
-31
11100001
11100000
10011111
BYU CS/ECEn 124
(unsigned int)
(signed magnitude)
(unsigned int)
(1’s complement)
(signed int)
(2’s complement)
(2’s complement)
(2’s complement)
Decimal
(2’s complement)
(1’s complement)
(signed magnitude)
Chapter 2 - Data Types
+
+
+
+
38
-13
25
-2
23
13
36
-67
-31
25
Conversions
Decimal to Binary Conversion

Continually divide the number by 2 and track
the remainders.
2 43
2 21 R 1
2 10 R 1
2 5 R0
2 2 R1
2

1 R0
0 R1
101011
1  25 + 0  24 + 1  23 + 0  22 + 1  21 + 1  20
32 +
0
+
8
+ 0
+
2 + 1
= 43
For negative numbers, do above for positive
number and negate result
BYU CS/ECEn 124
Chapter 2 - Data Types
26
Conversions
Decimal to Binary Conversion
Number
Binary Value
0101
5
0110
6
01111011
123
00100011
35
11011101
-35
1007 01111101111
BYU CS/ECEn 124
Chapter 2 - Data Types
27
Conversions
Sign-Extension in 2’s Complement

What do these represent?
0110 = 6
000000000000000110 = 6
1111 = -1
11111111111111111 = -1
1 = -1

You can make a number wider by simply
replicating its leftmost bit as desired.
BYU CS/ECEn 124
Chapter 2 - Data Types
28
Conversions
Word Sizes


In the preceding slides, every bit pattern
was a different length (15 was
represented as 01111).
Every real computer has a base word size


Memory fetches are word-by-word



our machine (MPS430) is 16-bits
even if you only want 8 bits (a byte)
Instructions are packed into words
Numeric representations are word-sized

15 is represented as 0000000000001111
BYU CS/ECEn 124
Chapter 2 - Data Types
29
Binary Arithmetic
Rules of Binary Addition

Rules of Binary Addition






0+0=0
0+1=1
1+0=1
1 + 1 = 0, with carry
5 + (-3) = 2
0000 0101 =
+ 1111 1101 =
--------0000 0010 =
+5
-3
-+2
Two's complement addition follows the same
rules as binary addition
Two's complement subtraction is the binary
addition of the minuend to the 2's complement
of the subtrahend

adding a negative number is the same as subtracting
a positive one
BYU CS/ECEn 124
Chapter 2 - Data Types
30
Binary Arithmetic
Adding 2’s Complement Integers
c
00110
+00101
01011

b1
00110
-00101
00001
Issues

Overflow: the result cannot be represented by the
number of bits available
0110
+0101
1011
BYU CS/ECEn 124
Hmmm. 6 + 5 -5.
Obviously something went wrong.
This is a case of overflow.
You can tell there is a problem - a positive
plus a positive cannot give a negative.
Chapter 2 - Data Types
31
Overflow
Overflow Revisited




Overflow = the result doesn’t fit in the
capacity of the representation
ALU’s are designed to detect overflow
It’s really quite simple
 if the carry in to the most significant
position (MSB) is different from the carry
out from the most significant position
(MSB), then overflow occurred.
Generally, overflows represented in CPU
status bit
BYU CS/ECEn 124
Chapter 2 - Data Types
32
Logical Operations
Logical Operations on Bits
A
0
0
1
1
B
0
1
0
1
AND
0
0
0
1
a = 001100101
b = 110010100
a AND b = ?
a OR b = ?
NOT a
= ?
A XOR b = ?
BYU CS/ECEn 124
A
0
0
1
1
B
0
1
0
1
A
0
0
1
1
OR
0
1
1
1
a
b
B
0
1
0
1
XOR
0
1
1
0
A
0
1
NOT
1
0
= 001100101
= 110010100
a AND b = 000000100
a OR b = 111110101
NOT a
= 110011010
A XOR b = 111110001
Chapter 2 - Data Types
33
Logical Operations
Examples of Logical Operations

AND

useful for clearing bits



OR

useful for setting bits



AND with zero = 0
AND with one = no change
11000101
AND 00001111
00000101
OR
OR with zero = no change
OR with one = 1
NOT


NOT
unary operation -- one argument
flips every bit
BYU CS/ECEn 124
Chapter 2 - Data Types
11000101
00001111
11001111
11000101
00111010
34
Floating Point
Floating Point Numbers


Binary scientific notation
32-bit floating point
1
s
8
exponent
23
mantissa
N  -1s 1. fraction 2exponent-127


Exponent is biased
Implied leading 1 in mantissa
BYU CS/ECEn 124
Chapter 2 - Data Types
35
Floating Point
Floating Point Numbers

Why the leading implied 1?

Always normalize after an operation



shift mantissa until leading digit is a 1
can assume it is always there, so don’t store it
Why the biased exponent?

To avoid signed exponent representations
1
s
8
exponent
23
mantissa
N  -1s 1. fraction 2exponent-127
BYU CS/ECEn 124
Chapter 2 - Data Types
36
Floating Point
Floating Point Numbers

What does this represent?
0 10000000 10000000000000000000000
Positive
number
Exponent is 128
which means the
real exponent is 1
Mantissa is to be interpreted as 1.1
This is 20 + 2-1 = 1 + 1/2 = 1.5
The final number is 1.5 x 21 = 3
BYU CS/ECEn 124
Chapter 2 - Data Types
37
Floating Point
Floating Point Numbers

What does this represent?
1 10000001 10101000000000000000000
Negative
number
Exponent is 129
which means the
real exponent is 2
Mantissa is to be interpreted as 1.10101
This is 20 + 2-1 + 2-3 + 2-5 =
1 + 1/2 + 1/8 + 1/32 = 1.65625
The final number is -1.65625 x 22 = -6.625
BYU CS/ECEn 124
Chapter 2 - Data Types
38
Hexadecimal
Hexadecimal Notation


Binary is hard to read and write by hand
Hexadecimal is a common alternative 0000 0
Binary Hex

16 digits are 0123456789ABCDEF
0100
1101
1011
1010
0111
1110
1110
0101
1000
1010
1110
1010
1111
1101
1111
0101
1. Separate binary code into
groups of 4 bits (starting
from the right)
2. Translate each group into a
single hex digit
BYU CS/ECEn 124
=
=
=
=
0x478F
0xDEAD
0xBEEF
0xA5A5
0x is a common
prefix for writing
numbers which means
hexadecimal
Chapter 2 - Data Types
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
39
Hexadecimal
Binary to Hex Conversion

Every four bits is a hex digit.

start grouping from right-hand side
011101010001111010011010111
3
A
8
F
4
D
7
This is not a new machine representation,
just a convenient way to write the number.
BYU CS/ECEn 124
Chapter 2 - Data Types
40
Hexadecimal
Decimal to Hex Examples
12decimal
= 1100
= 0xc
21decimal
= 0001 0101
= 0x15
55decimal
= 0011 0111
= 0x37
256decimal
= 0001 0000 0000 = 0x100
47decimal
= 0010 1111
= 0x2f
3decimal
= 0011
= 0x3
127decimal
= 0111 1111
= 0x7f
1029decimal = 0100 0000 0101 = 0x405
BYU CS/ECEn 124
Chapter 2 - Data Types
42
ASCII Characters
ASCII Codes




How do you represent characters? ‘A’
ASCII is a set of standard 8-bit, unsigned
integers (codes)
 ' ' = 32, '0' = 48, '1' = 49, 'A' = 65, 'B' = 66
Zero-extended to word size
To convert an integer digit to ASCII
character, add 48 (=‘0’)
 1 + 48 = 49 => ‘1’
BYU CS/ECEn 124
Chapter 2 - Data Types
43
ASCII Characters
ASCII Characters
0
0
NUL
1
DLE
2
SP
3
0
4
@
5
P
6
`
7
p
1
SOH
DC1
!
1
A
Q
a
q
2
STX
DC2
“
2
B
R
b
r
3
ETX
DC3
#
3
C
S
c
s
4
EOT
DC4
$
4
D
T
d
t
5
ENQ
NAK
%
5
E
U
e
u
6
ACK
SYN
&
6
F
V
f
v
7
BEL
ETB
‘
7
G
W
g
w
8
BS
CAN
(
8
H
X
h
x
9
HT
EM
)
9
I
Y
i
y
a
LF
SUB
*
:
J
Z
j
z
b
VT
ESC
+
;
K
[
k
{
c
FF
FS
,
<
L
\
l
|
d
CR
GS
-
=
M
]
m
}
e
SO
RS
.
>
N
^
n
~
f
SI
US
/
?
O
_
o
DEL
BYU CS/ECEn 124
Chapter 2 - Data Types
8-9
a-f
More
More
controls
symbols
44
ASCII Characters
Properties of ASCII Code





What is relationship between a decimal digit ('0',
'1', …) and its ASCII code?
What is the difference between an upper-case
letter ('A', 'B', …) and its lower-case equivalent ('a',
'b', …)?
Given two ASCII characters, how do we tell which
comes first in alphabetical order?
What is significant about the first 32 ASCII codes?
Are 128 characters enough? (http://www.unicode.org/)
BYU CS/ECEn 124
Chapter 2 - Data Types
45
ASCII Characters
Displaying Characters
48 Decimal
116 Decimal
53 Decimal
58 Decimal
BYU CS/ECEn 124
Chapter 2 - Data Types
46
Data Types
MSP430 Data Types

Words and bytes are supported directly by
the Instruction Set Architecture.




add.b
add.w
8-bit and 16-bit 2’s complement signed
integers
Other data types are supported by
interpreting variable length values as
logical, text, fixed-point, etc., in the software
that we write.
BYU CS/ECEn 124
Chapter 2 - Data Types
47
Review
Review: Representation

Everything is stored in memory as one’s
and zero’s




integers, floating point numbers, characters
program code
Data Type = Representation + Operations
You can’t tell what is what just by looking at
the binary representation


memory could have multiple meanings
it is possible to execute your Word document
BYU CS/ECEn 124
Chapter 2 - Data Types
48
Review
Review: Numbers…
Signed
1’s
Un-signed Magnitude Complement
7
6
5
4
3
2
1
0
-1
-2
-3
-4
Range:
BYU CS/ECEn 124
111
110
101
100
011
010
001
000
0 to 7
011
010
001
000, 100
101
110
111
-3 to 3
011
010
001
000, 111
110
101
100
-3 to 3
Chapter 2 - Data Types
2’s
Complement
011
010
001
000
111
110
101
100
-4 to 3
49
BYU CS/ECEn 124
Chapter 2 - Data Types
50
ASCII Characters
ASCII Characters
BYU CS/ECEn 124
Chapter 2 - Data Types
51