Transcript Chapter 1 - Data Types - BYU Computer Science Students

S01 - Data Types
Required:
Recommended:
PM: Ch 3, pgs 27-35
PM: Ch 5.1-6, pgs 47-56
Code: Chs 1-9, 20
Wiki: Signed Numbers
Two's Complement
Wiki: Two's_complement
Wiki: Fixed Point
Floating Point
CS 224
Chapter
Lab
Homework
L01: Data Types
L02: FSM
HW01
HW02
L03: Blinky
L04: Microarch
L05b: Traffic Light
L06a: Morse Code
HW03
HW04
HW05
HW06
L07b: Morse II
L08a: Life
L09b: Snake
L10a: Threads
HW07
HW08
HW09
HW10
S00: Introduction
Unit 1: Digital Logic
S01: Data Types
S02: Digital Logic
Unit 2: ISA
S03: ISA
S04: Microarchitecture
S05: Stacks / Interrupts
S06: Assembly
Unit 3: C
S07: C Language
S08: Pointers
S09: Structs
S10: Threads
S11: I/O
BYU CS 224
S01 - Data Types
2
Data Types Learning Outcomes…
Students will be able to:
 Explain the meaning and use of a computer data type.





Represent an integral decimal number as an unsigned binary number,
signed magnitude number, signed 1’s and 2’s complement binary
number, hexadecimal number, or a character.
Convert decimal to binary equivalents and sign extension.
Account for carry and overflow when doing binary arithmetic.
Represent a fractional decimal number in fixed point and floating point
formats.
Articulate the meaning/use of computer word size, endianness,
memory alignment, and casting in developing computer programs.
BYU CS 224
S01 - Data Types
3
Data
Data

What is Data?


Computer data is information processed / stored by a
computer.
What kinds of data do computers use?







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, …
…
BYU CS 224
S01 - Data Types
4
Digital Binary System
Binary Digital System

What is a Binary Digital System?




How are bits represented?





Binary (base 2) means there are two symbols, 0 and 1.
Digital means there are a finite number of values.
Basic unit of information is the binary digit, or bit.
Voltages
Residual magnetism
Light
Polarization
What about more than two values?



A collection of 2 bits has 4 possible values: 00, 01, 10, 11
A collection of 3 bits has 8 possible values: 000, 001, 010, 011,
100, 101, 110, 111
A collection of n bits has 2n possible values.
BYU CS 224
S01 - Data Types
5
Data Types
Data Types

Everything stored in computer memory is
represented as one’s and zero’s



Data Type = Representation + Operations



integers, real numbers, characters
program code
How the data is represented in memory
What operations are valid for the data
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 224
S01 - Data Types
6
Data Types
Some Important Data Types

Unsigned integers



Signed integers




Bounded negative, zero, positive numbers w/fraction
-2.5, 0.0, 100.125, …
Floating point numbers



Negative, zero, positive numbers
…, -3, -2, -1, 0, 1, 2, 3, …
Fixed point numbers


Only non-negative numbers
0, 1, 2, 3, 4, …
Unbounded negative, zero, positive numbers w/fraction
PI = 3.14159 x 100
Characters


8-bit, signed integers
‘0’, ‘1’, ‘2’, … , ‘a’, ‘b’, ‘c’, … , ‘A’, ‘B’, ‘C’, … , ‘@’, ‘#’,
BYU CS 224
S01 - Data Types
7
Why are Data Types Important?

Inefficient data types require more storage.



Inefficient data types require more memory.


Extra bytes take up not only space on disk, but also computer
memory, restricting number of records and adding extra I/O.
Inefficient data types result in decreased performance.


Database tables require minimum size fields.
Backup files, table indexes, and extra time to save data.
More disk storage results in more logical I/O, longer queries,
data type conversions, and fewer cache hits.
Bad things can happen with arithmetic operations.

Mismatch of data types, overflow, and conversion errors can be
disastrous!
BYU CS 224
S01 - Data Types
8
Data Types
Data Type Problems



Logic design and computer architecture courses describe
how to implement fast and efficient arithmetic circuits.
For programmers, what really matters is how the finite
word sizes used to represent integer and floating point
data determines what values can be represented and the
behavior of different operations.
For example:
void show_squares()
{
int x;
for (x = 5; x <= 5000000; x *= 10)
printf("x = %d x^2 = %d\n", x, x*x);
}
BYU CS 224
S01 - Data Types
9
Data Types
Data Type Problems

When compiled on most machines, this program produces
the following values:
x
x
x
x
x
x
x


=
=
=
=
=
=
=
5 x^2 = 25
50 x^2 = 2500
500 x^2 = 250000
5000 x^2 = 25000000
50000 x^2 = -1794967296
500000 x^2 = 891896832
5000000 x^2 = -1004630016
The “square” of a number can be negative!
Since data type int uses a 32-bit, two's complement
representation on most machines, programs cannot
represent the value 2.5 X 109 as an int.
BYU CS 224
S01 - Data Types
10
Data Types Learning Outcomes…
Students will be able to:

Explain the meaning and use of a computer data type.

Represent an integral decimal number as an unsigned
binary number, signed magnitude number, signed 1’s
and 2’s complement binary number, hexadecimal
number, or a character.

Convert decimal to binary equivalents and sign extension.
Account for carry and overflow when doing binary arithmetic.
Represent a fractional decimal number in fixed point and floating point
formats.
Articulate the meaning/use of computer word size, endianness,
memory alignment, and casting in developing computer programs.



BYU CS 224
S01 - Data Types
11
Digital Binary System
What are Decimal Numbers?

“Decimal” means that we have ten digits to use in
our representation of numbers




What is 3,546?



Ten Symbols: 0 through 9
Positional notation
Most widely used by modern civilizations
3 thousands + 5 hundreds + 4 tens + 6 ones.
3,54610 = 3103 + 5102 + 4101 + 6100
How about negative numbers?

Need an additional symbol(s)
BYU CS 224
S01 - Data Types
12
Digital Binary System
What are Binary Numbers?

“Binary” means that we have two digits to use in
our representation of numbers




What is the decimal value of binary 1011?



Two Symbols: 0 and 1
Positional notation
More adaptable for computers
1 eights + 0 fours + 1 twos + 1 ones
10112 = 123 + 022 + 121 + 120
How about negative numbers?


We don’t want to add additional symbols
So…
BYU CS 224
S01 - Data Types
13
Digital Binary System
“The World is Analog”


The analog world relies on exact physical values which
are affected by temperature, age, etc.
The digital world uses approximate physical values which
are not affected by age or temperature.


Music that never degrades.
Pictures that never get dusty or scratched.
2

Computers use analog voltages to approximate physical
values.
1.8
1.6
1.4

A logical ‘1’ is a relatively high voltage (2.4V - 5V).
A logical ‘0’ is a relatively low voltage (0V – 0.5V).
1.2
x(n)

1
0.8
0.6
0.4
0.2
0
BYU CS 224
0
10
20
30
40
n
50
S01 - Data Types
60
70
80
14
Digital Binary System
Binary Nomenclature

By using groups of bits, we can achieve high precision.





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
IEC International Standard names and symbols for binary prefixes:
SI Name (Symbol)
Value
Byte (B)
100
Kilobyte (kB)
103
Megabyte (MB)
Binary
Value
20
1 byte
Kibibyte
210
1024 bytes
106
Mebibyte
220
1,048,576 bytes
Gigabyte (GB)
109
Gibibyte
230
1,073,741,824 bytes
Terabyte (TB)
1012
Tebibyte
240
1,099,511,627,776 bytes
Petabyte (PB)
1015
Pebibyte
250
1,125,899,906,842,624 bytes
Exabyte (EB)
1018
Exbibyte
260
1,152,921,504,606,846,976 bytes
Zettabyte (ZB)
1021
Zebibyte
270
1,180,591,620,717,411,303,424 bytes
Yotabyte (YB)
1024
Yobibyte
280
1,208,925,819,614,629,174,706,176 bytes
BYU CS 224
S01 - Data Types
15
Unsigned
Unsigned Integers

Computers use weighted positional notation
most
significant
329
102 101 100
22
3x100 + 2x10 + 9x1 = 329

101
21
least
significant
20
1x4 + 0x2 + 1x1 = 5
What do these unsigned binary numbers represent?
0000 0
0110 6
BYU CS 224
1111 15
1010 10
0001 1
1000 8
S01 - Data Types
0111 7
1100 12
1011 11
1001 9
16
Unsigned
Unsigned Binary Arithmetic

Base 2 addition – just like base 10!

Add from right to left, propagating carry
carry
10010
+ 1001
10010
+ 1011
1111
+
1
11011
11101
10000
10111
+ 111
11110
Subtraction, multiplication, division,…
BYU CS 224
S01 - Data Types
17
Hexadecimal
Hexadecimal Notation


Binary is hard to read (very verbose)
Hexadecimal is a common alternative

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 224
=
=
=
=
0x478F
0xDEAD
0xBEEF
0xA5A5
0x is a common
prefix for writing
numbers which means
hexadecimal
S01 - Data Types
Binary Hex
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
18
Quiz 1.1
Convert the following unsigned numbers to
their decimal equivalent:
Unsigned Number
000101012
111111112
1216
AB16
123
BYU CS 224
S01 - Data Types
Number10
19
Data Types Learning Outcomes…
Students will be able to:

Explain the meaning and use of a computer data type.

Represent an integral decimal number as an unsigned
binary number, signed magnitude number, signed 1’s
and 2’s complement binary number, hexadecimal
number, or a character.

Convert decimal to binary equivalents and sign extension.
Account for carry and overflow when doing binary arithmetic.
Represent a fractional decimal number in fixed point and floating point
formats.
Articulate the meaning/use of computer word size, endianness,
memory alignment, and casting in developing computer programs.



BYU CS 224
S01 - Data Types
20
Signed
Signed Integers

Integers of n bits have 2n distinct values






Signed integer 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
MSB indicates sign: 0=positive, 1=negative
Examples: Sign-magnitude, 1’s complement, and 2’s complement
Positive signed integers are treated just like unsigned –
zero in most significant bit (MSB)
 00101 = 5
Negative signed integers have a one in the MSB
 sign-magnitude – 10101 = -5
 one’s complement – 11010 = -5
 two’s complement – 11011 = -5
BYU CS 224
S01 - Data Types
21
Signed
Sign-Magnitude Integers

Representations





 15decimal
 -15
0
 -0
Range


01111binary
11111
00000
10000
To negate a number,
toggle the sign bit.
Left-bit encodes sign:
0 = + (or 0)
1 = - (or 0)
-(2(n-1)-1) to 2(n-1)-1
Problems



Two representations of zero (+0 and –0)
Arithmetic circuits are complex and cumbersome
Negation/absolute value operations are easy, but
addition/subtraction operations are difficult.
BYU CS 224
S01 - Data Types
22
Signed
1’s Complement Integers

Representations





 6decimal
 -6
0
 -0
Range


00110binary
11001
00000
11111
To negate a number,
invert number bit-by-bit.
Left-bit encodes sign:
0 = + (or 0)
1 = - (or 0)
-(2(n-1)-1) to 2(n-1)-1
Problems


Two representations of zero (+0 and –0)
Arithmetic circuits use binary addition with end-around
carry (ie. resulting carry out of the most significant bit of the sum
is added to the least significant bit of the sum.)
BYU CS 224
S01 - Data Types
23
Signed
2’s Complement Integers

Representation





 6decimal
 -6
0
 -1
Left-bit encodes sign:
0 = + (or 0)
1 = -
Range


00110binary
11010
00000
11111
To negate a number,
1’s complement + 1.
–2(n-1) to 2(n-1)-1
Simplifies logic circuit construction


Addition is performed using simple binary addition
Bottom line: simpler/faster hardware units!
BYU CS 224
S01 - Data Types
24
Signed
2’s Complement Integer

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 224
01001 (9)
10110 (1’s comp)
+
1
10111 (-9)
S01 - Data Types
25
Signed
2’s Complement

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 2’s complement numbers?
0000
0110
1111
1010
0001
BYU CS 224
1000
0111
1100
1011
1001
0
6
-1
-6
1
S01 - Data Types
-8
7
-4
-5
-7
26
Signed
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 224
011010000
(1’s comp)
(flip)
(copy)
100110000
S01 - Data Types
27
Quiz 1.2
What is the decimal number represented
by the following binary digits?
Number10
(unsigned)
(sign-magnitude)
101112
(1's complement)
(2's complement)
BYU CS 224
S01 - Data Types
28
Data Types Learning Outcomes…
Students will be able to:


Explain the meaning and use of a computer data type.
Represent an integral decimal number as an unsigned binary number,
signed magnitude number, signed 1’s and 2’s complement binary
number, hexadecimal number, or a character.

Convert decimal to binary equivalents and sign
extension.

Account for carry and overflow when doing binary arithmetic.
Represent a fractional decimal number in fixed point and floating point
formats.
Articulate the meaning/use of computer word size, endianness,
memory alignment, and casting in developing computer programs.


BYU CS 224
S01 - Data Types
29
Conversions
Decimal to Binary Conversion
1. Continually divide the number by 2 and prepend the
remainders until zero.
2
43
2
21 R 1
2
10 R 1
2
5 R0
2
2 R1
2
1 R0
0101011
1  25 + 0  24 + 1  23 + 0  22 + 1  21 + 1  20
32 +
0
+
8
+ 0
+
2 + 1
= 43
0 R1
2. Unsigned to signed conversion: prepend a zero.
3. Do a 2’s complement to negate number:
-(0101011) = 1010101
BYU CS 224
S01 - Data Types
30
Sign-Extension
Sign-Extension


You can make a number wider by simply replicating its
leftmost bit as desired.
What is the decimal value of the following 2’s
complement numbers?
0110 = 6
000000000000000110 = 6
1111 = -1
11111111111111111 = -1
1 = -1
BYU CS 224
S01 - Data Types
All the same!
(Sign-extended values)
31
Quiz 1.3
Convert the following decimal numbers to
their 8-bit, 2’s complement binary number
equivalent:
Number10
5
-35
BYU CS 224
Binary (2’s complement)
S01 - Data Types
32
Data Types Learning Outcomes…
Students will be able to:



Explain the meaning and use of a computer data type.
Represent an integral decimal number as an unsigned binary number,
signed magnitude number, signed 1’s and 2’s complement binary
number, hexadecimal number, or a character.
Convert decimal to binary equivalents and sign extension.

Account for carry and overflow when doing binary
arithmetic.

Represent a fractional decimal number in fixed point and floating point
formats.
Articulate the meaning/use of computer word size, endianness,
memory alignment, and casting in developing computer programs.

BYU CS 224
S01 - Data Types
33
Signed
2’s Complement Binary Addition

Rules of Binary Addition:






0+0=0
0+1=1
1+0=1
1 + 1 = 0, with carry
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 224
S01 - Data Types
0000 0101 =
+ 1111 1101 =
--------0000 0010 =
1111
1110
1101
1100
1011
0000
-1 0
0001
0010
1
-2
2
-3
3
4
-4
-5
5
-6
1010
1001
-
6
-7 -8
1000
+5
-3
-+2
7
0011
0100
0101
0110
0111
+
34
Overflow
2’s Complement Overflow





Overflow = the result doesn’t fit in the capacity of the
representation (data type).
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, overflow is only reported as a CPU status bit.
NOTE: CARRY OUT IS NOT OVERFLOW!
carry
00100110
+ 11101101
100010011
BYU CS 224
carry
38
-19
19
00100110
+ 01101101
010010011
S01 - Data Types
38
109
-109
35
Quiz 1.4
1. Perform the following 3 additions given the indicated
data types:
Sign-Magnitude
00100110
+ 11101101
1’s Complement
00100110
+ 11101101
2’s Complement
00100110
+ 11101101
2. What data type uses the same arithmetic logic as an
unsigned integer?
3. Which data type has the simplest arithmetic logic?
BYU CS 224
S01 - Data Types
36
Fractional Data Types
Data Types Learning Outcomes…
Students will be able to:




Explain the meaning and use of a computer data type.
Represent an integral decimal number as an unsigned binary number,
signed magnitude number, signed 1’s and 2’s complement binary
number, hexadecimal number, or a character.
Convert decimal to binary equivalents and sign extension.
Account for carry and overflow when doing binary arithmetic.

Represent a fractional decimal number in fixed point
and floating point formats.

Articulate the meaning/use of computer word size, endianness,
memory alignment, and casting in developing computer programs.
BYU CS 224
S01 - Data Types
38
Fixed Point
Fixed Point Numbers

Bounded negative, zero, positive numbers
w/fraction.




Fractions are created by dividing a binary number into
an integral and fractional part.
The program is responsible for knowing the position of
the “decimal point”.
Un-signed or signed (generally 2’s complement).
Requires less processing resources than floating-point.
-29 28
27
26
25
24
23
22
21
20
2-1 2-2 2-3 2-4 2-5 2-6
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 = 3.5
Whole or integral Part
Fractional Part
Decimal Point
BYU CS 224
S01 - Data Types
39
Fixed Point
Fixed Point Number Examples
Q16.0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0
=
82
Q15.1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0
=
41
Q14.2
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0
=
20.5
Q13.3
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
=
10.375
Q12.4
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
=
5.1875
Q11.5
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
=
2.59375
Q10.6
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
=
1.296875
BYU CS 224
S01 - Data Types
40
Fixed Point
Fixed Point Numbers
Q10.6
0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0
Intregal part
Fractional part
 With a fixed-point fractional part, we can have 10.75
 The more bits you use in your fractional part, the more
fractional accuracy (and less integral values).
Accuracy is 2 -(# fraction bits).
For example, if we have 6 bits in our fractional part (like the above
example), our accuracy is 2-6 = 0.015625.
 Divide by 2(# fraction bits) to convert to decimal.
BYU CS 224
S01 - Data Types
41
Quiz 1.5
What is the decimal equivalent of the following 2’s
complement Q8.8 fixed point number?
-27 26 25
24
23
22
21
20 2-1 2-2 2-3 2-4 2-5 2-6 2-7 2-8
0
1
0
1
1
1
0
0
Integral Part
BYU CS 224
1
0
1
1
0
0
0
0
=
Fractional Part
S01 - Data Types
42
Floating Point
Floating Point Numbers

Why floating point?



Numbers such as , e, 7 cannot be expressed by a fixed
number of significant figures.
Computers using base-2 representation cannot precisely
represent certain exact base-10 numbers.
Fractional quantities are typically represented in
computer using “floating point” form, e.g.,
Number = -1s  1.fraction  2(exponent – 127)
Mantissa
0.5 <= m < 1
BYU CS 224
S01 - Data Types
Base
43
Floating Point
Floating Point Numbers

Unbounded negative, zero, positive numbers
w/fraction.


Binary scientific notation.
IEEE 754 Standard - 32 / 64 bit floating point.
1
s
8
exponent
23
fraction
N = -1s  1.fraction  2(exponent – 127)



Exponent is biased by 127 (2exponent-1 – 1).
Normalized - implied leading 1 in mantissa (fraction or
significand).
Special bit patterns - zero (all 0’s), infinity, NaN.
BYU CS 224
S01 - Data Types
44
Floating Point
Normalizing Floating Point

Scientific Notation




8
s exponent
23
fraction
N = -1s  1.fraction  2(exponent – 127)
Base 2 equivalences




0.00123  103 = 1.23
0.01230  102 = 1.23
0.12300  101 = 1.23
1
0.0112  2(129-127) = .375  22 = 1.5
0.1102  2(128-127) = .75  21 = 1.5
1.1002  2(127-127) = 1.5  20 = 1.5
1 is assumed
and not stored
in number.
Floating point normalization


Fraction is shifted left (decrementing exponent) until greater than 1
– then the 1 is dropped.
Allows for one more binary bit of precision.
BYU CS 224
S01 - Data Types
45
Floating Point
Floating Point Numbers

What does this represent?
0 10000000 10000000000000000000000
Positive
Exponent is
128 – 127 = 1
Fraction is 1.1 = 20 + 2-1 = 1 + 1/2 = 1.5
The final number is 1.5 x 21 = 3.0

And this one?
1 10000001 10101000000000000000000
Negative
Exponent is
129 – 127 = 2
Fraction is 1.10101 = 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 224
S01 - Data Types
46
Quiz 1.6
What is the decimal equivalent of the following 32bit floating point number?
1 10000011 11000000000000000000000 =
1
8
s exponent
23
fraction
N = -1s  1.fraction  2(exponent – 127)
BYU CS 224
S01 - Data Types
47
Fixed Point
Decimal to Fixed Point
Example: convert -22.625 to Q12.4
-25 24 23 22 21 20 2-1 2-2 2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10
1. Multiply unsigned value by 16 (24):

Integral Part

Fractional Part
To convert a decimal number to
Q(integer,fraction) fixed point:
1. Convert integral and fractional
parts separately.
or
1. Multiply the unsigned number by 2
raised to the power of the number
fractional bits.
2. Truncate (or round).
3. Convert unsigned integer to binary.
4. Do 2’s complement (if needed).
2. Convert decimal 362 to binary by
dividing by 2 and prepending
remainders:









S01 - Data Types
362 / 2 = 181
181 / 2 = 90
90 / 2 = 45
45 / 2 = 22
22 / 2 = 11
11 / 2 = 5
5/2=2
2/2=1
1/2=0
0
10
010
1010
01010
101010
1101010
01101010
101101010
3. Pad leading zeros:

0000000101101010
4. Do 2’s complement (if needed):

BYU CS 224
22.625 * 16 = 362
1111111010010110
48
Quiz 1.7
Convert the following decimal number to a 2’s
complement, 16-bit (Q6.10) fixed point number.
-25 24 23 22 21 20 2-1 2-2 2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10
-25.8125 =
Integral Part
BYU CS 224
S01 - Data Types
Fractional Part
49
Floating Point
Decimal to Floating Point
1
8
s exponent
Example: convert 22.625 to FP
23
fraction
1. Convert decimal 22 to binary:
N = -1s  1.fraction  2(exponent – 127)

2210 = 101102
2. Convert decimal 0.625 to binary:

To convert a decimal number to
binary IEEE 754 floating point:
1. Convert the absolute value of the
decimal number to a binary integer
plus a binary fraction.
2. Normalize the number in binary
scientific notation to obtain fraction
and exponent.
3. Bias exponent by 127, set s=0 for
a positive number and s=1 for a
negative number, and combine.

3. Combine integer and fraction:

S01 - Data Types
10110.1012  20
4. Normalize:





10110.1012  20
1011.01012  21
101.101012  22
10.1101012  23
1.01101012  24
5. Bias exponent, drop the leading bit,
and combine sign, exponent, and
fraction:

BYU CS 224
0.62510 = 0.1012
0 10000011 01101010000000000000000
50
Quiz 1.8
What is the IEEE 754 binary floating point equivalent
of the following decimal number?
-37.375 =
2(exponent – 127)
BYU CS 224
(1).Fraction
S01 - Data Types
51
Review
Floating Point Numbers

What does this represent?
0 10000000 10000000000000000000000
Positive
Exponent is
128 – 127 = 1
Fraction is 1.1 = 20 + 2-1 = 1 + 1/2 = 1.5
The final number is 1.5 x 21 = 3.0

0x40400000 = 3.0
0xc0d40000 = -1.65625
And this one?
1 10000001 10101000000000000000000
Negative
Exponent is
129 – 127 = 2
Fraction is 1.10101 = 20 + 2-1 + 2-3 + 2-5
= 1 + 1/2 + 1/8 + 1/32
= 1 21/32 = 1.65625
The final number is -1.65625 x 22 = -6.625
BYU CS 224
S01 - Data Types
52
Floating Point Behavior

Programmer must be aware of accuracy limitations!
(1 + 1030) + –1030
1030 – 1030
0

=? 1 + (1030 + –1030)
=? 1 + 0
 1
Operations not associative!
(1.0 + 6.0) ÷ 640.0 =? (1.0 ÷ 640.0) + (6.0 ÷ 640.0)
7.0 ÷ 640.0 =? .001563 + .009375
.010938
.010937 

×,÷ not distributive across +,-
BYU CS 224
S01 - Data Types
53
Rounding vs. Chopping

IEEE 754 floating point significant digits:




32 bit float (4 bytes) with 23 bit mantissa results in 6 to 9
decimal digits (~7 digits on average).
64 bit double (8 bytes) with 52 bit mantissa results in 15 to 17
decimal digits (~16 digits on average).
Numbers like 0.5, 0.25, 0.75, 0.125 are stored exactly, but 0.1 is
not (ie., if you need to store cents precisely, do not use float or
double).
pi = 3.141592653589793238462643383279502884197…


Error = Real value (analog) – floating point value (discrete)
Chopping – easy, fast, truncation error.


float (chopped)
pi = 3.141592
et = 0.00000065
Rounding – more accurate, but computational overhead.

BYU CS 224
float (rounded)
pi = 3.141593
et = 0.00000035
S01 - Data Types
54
float's vs int's
BYU CS 224
S01 - Data Types
55
Data Types Learning Outcomes…
Students will be able to:






Explain the meaning and use of a computer data type.
Represent an integral decimal number as an unsigned binary number,
signed magnitude number, signed 1’s and 2’s complement binary
number, hexadecimal number, or a character.
Convert decimal to binary equivalents and sign extension.
Account for carry and overflow when doing binary arithmetic.
Represent a fractional decimal number in fixed point and floating point
formats.
Articulate the meaning/use of computer word size,
endianness, memory alignment, and casting in
developing computer programs.
BYU CS 224
S01 - Data Types
56
Word Size
Word Size

Word size is the natural size of data used by a
particular computer design and usually refers to:






Size of registers
Amount of data transferred to/from memory in single operation
Largest possible address
Size of the smallest instruction
Number of bits processed by the CPU in a single operation
Every computer has a base word size



Early machines were 8 bits.
Today’s Intel Pentium machines are 32 or 64 bit
MPS430 is 16-bits
BYU CS 224
S01 - Data Types
57
Data Storage

Computer memory is the storage space in a computer
where data and instructions are stored.





Data Alignment


Memory is a contiguous block of consecutive memory locations.
Each location holds a fixed number of bits (usually 8-bits or byte).
Each location has a unique binary (hexadecimal) memory address.
The address denotes the smallest unit of accessible memory.
Objects larger than the smallest addressable unit (such as an int)
are aligned if the address of the object is a multiple of the size of
the object. (ie., address mod size equals 0)
Little and Big Endian


Storage and transmission order for multi-byte data types.
Little endian – least significant bytes stored first (lower address).
BYU CS 224
S01 - Data Types
58
Computer Memory

Computer memory can be viewed as
a linear array of contiguous bytes.
Memory
by an address.
int
cat is
= indexed
0x1234;
// 2 bytes
= 10; location depends
// 1 byte
char
Data goat
type memory
upon
data bat
alignment.
long
= 0x12345678; // 4 bytes
bird data
= 4;
// 1 byte
char
Multi-byte
type storage order
depends
upon
char
sheep
= endianess.
-2;
// 1 byte


To align data types, it may be
necessary to insert some meaningless
bytes between the end of the last data
structure and the start of the next,
which is called data structure padding.
Address
Value
0x0200:
0x0202:
0x34
0x12
0x0a
0x0203:
padding
0x0204:
0x78
0x56
0x34
0x12
0x04
0xfe
0x0201:
0x0205:
0x0206:
0x0207:
0x0208:
0x0209:
0x020A:
0x020B:
BYU CS 224
S01 - Data Types
59
Quiz 1.9
Fill in hexadecimal byte memory values
for the following global variable
declarations:
char dog = 1;
int pig = 2;
unsigned long apple = 3;
float camel = 4;
 Begin at address 0x0200.
 Data type sizes are
 chars: 1 byte
 ints: 2 bytes
 longs and floats: 4 bytes
 Pad for correct word data alignment.
 Use little endian storage order.
BYU CS 224
S01 - Data Types
Address
Value16
0x0200:
0x0201:
0x0202:
0x0203:
0x0204:
0x0205:
0x0206:
0x0207:
0x0208:
0x0209:
0x020A:
0x020B:
60
Other Data Types
ASCII Characters
ASCII Codes

The American Standard Code for Information Interchange
(ASCII) is a character-encoding scheme based on the
ordering of the English alphabet.




Represent text in computers
7-bit, unsigned integers
1st 32 codes unprintable
Developed from teletype
BYU CS 224
S01 - Data Types
62
Unicode Characters
Unicode Codes


Unicode is a computing industry standard for the
consistent encoding, representation and handling of text
expressed in most of the world's writing systems.
Latest version of Unicode contains a repertoire of more
than 110,000 characters covering 100 scripts.












0000-001F Control Characters
0020-00FF Latin (ASCII + extended)
0250-02AF IPA Extentions
0300-036F Diacritical Marks
0400-052F Cyrillic (Russian, Ukrainian, Bulgarian)
0530-058F Armenian
0590-05FF Hebrew (Hebrew, Yiddish)
0600-077F Arabic (Arabic, Persian, Kurd, Syrian)
0780-07BF Thaana (Maldivian)
07C0-07FF Nko
0800-083F Samaritan
0840-085f Mandaic
BYU CS 224
S01 - Data Types
Mandraic
Devanagari (sanskrit, hindi)
Bengali
Gujarati (abugida)
Oriya
Telugu
Malayalam
Thai
Lao
Tibetab
Georgian
Hangul Jamo
…
63
Data Types
Additional Data Types

Proposed C fixed-point









ISO/IEC 9899:1999
#include <stdfix.h>
_Fract, _Accum
TI: UQ8.8
bool (added to C in 1999)
enums
Complex
BCD
EBCDIC
BYU CS 224
S01 - Data Types
64
C
MSP430 C Variable Data Types
Type
Size
Representation
Minimum
Maximum
8 bits
ASCII
-128
127
bool 8 bits
ASCII
0
255
short, signed short
16 bits
2's complement
-32768
32767
unsigned short
16 bits
Binary
0
65535
int, signed int
16 bits
2's complement
-32768
32767
unsigned int
16 bits
Binary
0
65535
long, signed long
32 bits
2's complement
-2,147,483,648
2,147,483,647
unsigned long
32 bits
Binary
0
4,294,967,295
enum
16 bits
2's complement
-32768
32767
float
32 bits
IEEE 32-bit
1.175495e-38
3.4028235e+38
double
32 bits
IEEE 32-bit
1.175495e-38
3.4028235e+38
long double
32 bits
IEEE 32-bit
1.175495e-38
3.4028235e+38
pointers, references
16 bits
Binary
0
0xFFFF
function pointers
16 bits
Binary
0
0xFFFF
char, signed char
unsigned char
BYU CS 224
S01 - Data Types
65
Type Casting


In binary operations (e.g., +, -, /,
etc.) with operands of mixed
data types, the resultant data
type will take the higher order
data type of the two operands.
Data type conversion


Casting – explicitly convert a
variable (expression) from one
data type to another data type.
Promotion or data coercion –
implicitly change a “smaller” data
type into a “larger” data type. (Also
called “widening”.)
BYU CS 224
S01 - Data Types
long double
Higher
double
float
unsigned long long
long long
unsigned long
long
unsigned int
int
unsigned short
short
unsigned char
char
Lower
66
Quiz 1.10











Loop counter
Gender
# of CD’s
Sound amplitude
Pi
GPA
GPS Coordinates
Bank account
Message
Population
Real numbers (physical)
BYU CS 224
______________________
______________________
______________________
______________________
______________________
______________________
______________________
______________________
______________________
______________________
______________________
S01 - Data Types
67
BYU CS 224
S01 - Data Types
68