Data Representation

Outline
 Positional Number Systems
 Binary and Hexadecimal Numbers
 Base Conversions
 Integer Storage Sizes
 Binary and Hexadecimal Addition
 Signed Integers and 2's Complement Notation
 Sign Extension
 Binary and Hexadecimal subtraction
 Carry and Overflow
 Character Storage
 Positional Number Systems
Different Representations of Natural Numbers

XXVII Roman numerals (not positional)

27 Radix-10 or decimal number (positional)
110112 Radix-2 or binary number (also positional)

Fixed-radix positional representation with k digits

Number N in radix r = (dk–1dk–2 . . . d1d0)r

Value = dk–1×r k–1 + dk–2×r k–2 + … + d1×r + d0

Examples: (11011)2 = 1×24 + 1×23 + 0×22 + 1×2 + 1 = 27

(2103)4 = 2×43 + 1×42 + 0×4 + 3 = 147

 Binary Numbers
 Each binary digit (called bit) is either 1 or 0

 Bits have no inherent meaning, can represent

 Unsigned and signed integers

 Characters
Most Least
 Floating-point numbers Significant Bit Significant Bit

 Images, sound, etc. 7 6 5 4 3 2 1 0

1 0 0 1 1 1 0 1
27 26 25 24 23 22 21 20
 Bit Numbering
 Least significant bit (LSB) is rightmost (bit 0)

 Most significant bit (MSB) is leftmost (bit 7 in an 8-bit number)

 Converting Binary to Decimal
 Each bit represents a power of 2
 Every binary number is a sum of powers of 2

 Decimal Value = (dn-1  2n-1) + ... + (d1  21) + (d0  20)

 Binary (10011101)2 = 27 + 24 + 23 + 22 + 1 = 157

7 6 5 4 3 2 1 0
1 0 0 1 1 1 0 1
27 26 25 24 23 22 21 20

Some common
powers of 2
 Convert Unsigned Decimal to
Binary
 Repeatedly divide the decimal integer by 2
 Each remainder is a binary digit in the translated value

least significant bit

37 = (100101)2

most significant bit

stop when quotient is zero

 Hexadecimal Integers
 16 Hexadecimal Digits: 0 – 9, A – F
 More convenient to use than binary numbers

Binary, Decimal, and Hexadecimal Equivalents

Converting Binary to Hexadecimal
 Each hexadecimal digit corresponds to 4 binary bits

 Example:

Convert the 32-bit binary number to hexadecimal

1110 1011 0001 0110 1010 0111 1001 0100

 Solution:

E B 1 6 A 7 9 4
1110 1011 0001 0110 1010 0111 1001 0100
 Converting Hexadecimal to
Decimal
 Multiply each digit by its corresponding power of 16

Value = (dn-1  16n-1) + (dn-2  16n-2) + ... + (d1  16) + d0

 Examples:

(1234)16 = (1  163) + (2  162) + (3  16) + 4 =

Decimal Value 4660

(3BA4)16 = (3  163) + (11  162) + (10  16) + 4 =

Decimal Value 15268

 Converting Decimal to
Hexadecimal
 Repeatedly divide the decimal integer by 16
 Each remainder is a hex digit in the translated value

least significant digit

most significant digit

stop when
quotient is zero

Decimal 422 = 1A6 hexadecimal

 Integer Storage Sizes
Byte 8

Half Word 16 Storage Sizes

Word 32

Double Word 64

Storage Type Unsigned Range Powers of 2

Byte 0 to 255 0 to (28 – 1)
Half Word 0 to 65,535 0 to (216 – 1)
Word 0 to 4,294,967,295 0 to (232 – 1)
Double Word 0 to 18,446,744,073,709,551,615 0 to (264 – 1)

What is the largest 20-bit unsigned integer?

Answer: 220 – 1 = 1,048,575
 Binary Addition
 Start with the least significant bit (rightmost bit)
 Add each pair of bits
 Include the carry in the addition, if present

carry 1 1 1 1

0 0 1 1 0 1 1 0 (54)

+ 0 0 0 1 1 1 0 1 (29)

0 1 0 1 0 0 1 1 (83)
bit position: 7 6 5 4 3 2 1 0
 Hexadecimal Addition
 Start with the least significant hexadecimal digits
 Let Sum = summation of two hex digits
 If Sum is greater than or equal to 16
 Sum = Sum – 16 and Carry = 1

 Example:

carry: 1 1 1
1C37286A A + B = 10 + 11 = 21
+
9395E84B Since 21 ≥ 16
Sum = 21 – 16 = 5
AFCD10B5 Carry = 1
 Signed Integers
 Several ways to represent a signed number
 Sign-Magnitude
 Biased
 1's complement
 2's complement
 Divide the range of values into 2 equal parts
 First part corresponds to the positive numbers (≥ 0)
 Second part correspond to the negative numbers (< 0)
 Focus will be on the 2's complement representation
 Has many advantages over other representations
 Used widely in processors to represent signed integers
Two's Complement Representation
 Positive numbers 8-bit Binary Unsigned Signed
value value value
 Signed value = Unsigned value
00000000 0 0
 Negative numbers 00000001 1 +1
 Signed value = Unsigned value – 2n 00000010 2 +2
n = number of bits ... ... ...

 Negative weight for MSB 01111110 126 +126

01111111 127 +127
 Another way to obtain the signed
value is to assign a negative weight 10000000 128 -128
to most-significant bit 10000001 129 -127
... ... ...
1 0 1 1 0 1 0 0
11111110 254 -2
-128 64 32 16 8 4 2 1

= -128 + 32 + 16 + 4 = -76 11111111 255 -1

 Forming the Two's Complement
starting value 00100100 = +36
step1: reverse the bits (1's complement) 11011011
step 2: add 1 to the value from step 1 + 1
sum = 2's complement representation 11011100 = -36

Sum of an integer and its 2's complement must be zero:

00100100 + 11011100 = 00000000 (8-bit sum)  Ignore Carry

Another way to obtain the 2's complement: Binary Value

least

Start at the least significant 1 = 00100 1 00 significant 1

Leave all the 0s to its right unchanged 2's Complement

Complement all the bits to its left = 11011 1 00
 Sign Bit
 Highest bit indicates the sign

 1 = negative Sign bit

 0 = positive 1 1 1 1 0 1 1 0
Negative

0 0 0 0 1 0 1 0 Positive

For Hexadecimal Numbers, check most significant digit

If highest digit is > 7, then value is negative
Examples: 8A and C5 are negative bytes
B1C42A00 is a negative word (32-bit signed integer)
 Sign Extension
Step 1: Move the number into the lower-significant bits
Step 2: Fill all the remaining higher bits with the sign bit
 This will ensure that both magnitude and sign are correct
 Examples
 Sign-Extend 10110011 to 16 bits
10110011 = -77 11111111 10110011 = -77
 Sign-Extend 01100010 to 16 bits
01100010 = +98 00000000 01100010 = +98

 Infinite 0s can be added to the left of a positive number

 Infinite 1s can be added to the left of a negative number
 Two's Complement of a
Hexadecimal
 To form the two's complement of a hexadecimal
 Subtract each hexadecimal digit from 15

 Add 1

 Examples:

2's complement of 6A3D = 95C2 + 1 = 95C3

2's complement of 92F15AC0 = 6D0EA53F + 1 = 6D0EA540

2's complement of FFFFFFFF = 00000000 + 1 = 00000001

 No need to convert hexadecimal to binary

 Binary Subtraction
 When subtracting A – B, convert B to its 2's complement
 Add A to (–B)

borrow: 1 1 1 carry: 1 1 1 1

01001101 01001101
– +
00111010 11000110 (2's
complement)

00010011 00010011 (same result)

 Final carry is ignored, because

 Negative number is sign-extended with 1's
 You can imagine infinite 1's to the left of a negative number
 Adding the carry to the extended 1's produces extended zeros
 Hexadecimal Subtraction
16 + 5 = 21
Borrow: 1 1 1 Carry: 1 1 1 1 1
B14FC675 B14FC675
- +
839EA247 7C615DB9 (2's complement)

2DB1242E 2DB1242E (same result)

 When a borrow is required from the digit to the left, then

Add 16 (decimal) to the current digit's value

 Last Carry is ignored
 Ranges of Signed Integers
For n-bit signed integers: Range is -2n–1 to (2n–1 – 1)
Positive range: 0 to 2n–1 – 1
Negative range: -2n–1 to -1

Storage Type Unsigned Range Powers of 2

Byte –128 to +127 –27 to (27 – 1)
Half Word –32,768 to +32,767 –215 to (215 – 1)
Word –2,147,483,648 to +2,147,483,647 –231 to (231 – 1)
–9,223,372,036,854,775,808 to
Double Word –263 to (263 – 1)
+9,223,372,036,854,775,807

Practice: What is the range of signed values that may be stored in 20 bits?
 Carry and Overflow
 Carry is important when …
 Adding or subtracting unsigned integers
 Indicates that the unsigned sum is out of range
 Either < 0 or >maximum unsigned n-bit value
 Overflow is important when …
 Adding or subtracting signed integers
 Indicates that the signed sum is out of range
 Overflow occurs when
 Adding two positive numbers and the sum is negative
 Adding two negative numbers and the sum is positive
 Can happen because of the fixed number of sum bits
 Carry and Overflow Examples
 We can have carry without overflow and vice-versa
 Four cases are possible (Examples are 8-bit numbers)
1 1 1 1 1 1

0 0 0 0 1 1 1 1 15 0 0 0 0 1 1 1 1 15
+ +
0 0 0 0 1 0 0 0 8 1 1 1 1 1 0 0 0 248 (-8)

0 0 0 1 0 1 1 1 23 0 0 0 0 0 1 1 1 7

Carry = 0 Overflow = 0 Carry = 1 Overflow = 0

1 1 1 1

0 1 0 0 1 1 1 1 79 1 1 0 1 1 0 1 0 218 (-38)
+ +
0 1 0 0 0 0 0 0 64 1 0 0 1 1 1 0 1 157 (-99)

1 0 0 0 1 1 1 1 143 0 1 1 1 0 1 1 1 119
(-113)
Carry = 0 Overflow = 1 Carry = 1 Overflow = 1
 Range, Carry, Borrow, and
Overflow
 Unsigned Integers: n-bit representation

Numbers < min Numbers > max

Borrow = 1 Carry = 1
Finite Set of Unsigned Integers
Subtraction Addition

min = 0 max = 2n–1

 Signed Integers: n-bit 2's complement representation

Numbers < min Numbers > max

Negative Positive
Finite Set of Signed Integers
Overflow Overflow

min = -2n-1 0 max = 2n-1–1

 Character Storage
 Character sets
 Standard ASCII: 7-bit character codes (0 – 127)
 Extended ASCII: 8-bit character codes (0 – 255)
 Unicode: 16-bit character codes (0 – 65,535)
 Unicode standard represents a universal character set
 Defines codes for characters used in all major languages
 Used in Windows-XP: each character is encoded as 16 bits
 UTF-8: variable-length encoding used in HTML
 Encodes all Unicode characters
 Uses 1 byte for ASCII, but multiple bytes for other characters

 Null-terminated String
 Array of characters followed by a NULL character
 Printable ASCII Codes
0 1 2 3 4 5 6 7 8 9 A B C D E F
2 space ! " # $ % & ' ( ) * + , - . /
3 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
4 @ A B C D E F G H I J K L M N O
5 P Q R S T U V W X Y Z [ \ ] ^ _
6 ` a b c d e f g h i j k l m n o
7 p q r s t u v w x y z { | } ~ DEL

 Examples:
 ASCII code for space character = 20 (hex) = 32 (decimal)
 ASCII code for 'L' = 4C (hex) = 76 (decimal)
 ASCII code for 'a' = 61 (hex) = 97 (decimal)
 Control Characters
 The first 32 characters of ASCII table are used for control
 Control character codes = 00 to 1F (hexadecimal)
 Not shown in previous slide
 Examples of Control Characters
 Character 0 is the NULL character  used to terminate a string
 Character 9 is the Horizontal Tab (HT) character
 Character 0A (hex) = 10 (decimal) is the Line Feed (LF)
 Character 0D (hex) = 13 (decimal) is the Carriage Return (CR)
 The LF and CR characters are used together
 They advance the cursor to the beginning of next line
 One control character appears at end of ASCII table
 Character 7F (hex) is the Delete (DEL) character
Floating Point Arithmetic
 Outline

 Floating-Point Numbers

 IEEE 754 Floating-Point Standard

 The World is Not Just Integers
 Programming languages support numbers with fraction
 Called floating-point numbers
 Examples:
3.14159265… (π)
2.71828… (e)
0.000000001 or 1.0 × 10–9 (seconds in a nanosecond)
86,400,000,000,000 or 8.64 × 1013 (nanoseconds in a day)
last number is a large integer that cannot fit in a 32-bit integer
 We use a scientific notation to represent
 Very small numbers (e.g. 1.0 × 10–9)
 Very large numbers (e.g. 8.64 × 1013)
 Scientific notation: ± d . f1f2f3f4 … × 10 ± e1e2e3
 Floating-Point Numbers
 Examples of floating-point numbers in base 10 …
 5.341×103 , 0.05341×105 , –2.013×10–1 , –201.3×10–3
decimal point
 Examples of floating-point numbers in base 2 …
 1.00101×223 , 0.0100101×225 , –1.101101×2–3 , –1101.101×2–6
binary point
 Exponents are kept in decimal for clarity
 The binary number (1101.101)2 = 23+22+20+2–1+2–3 = 13.625
 Floating-point numbers should be normalized
 Exactly one non-zero digit should appear before the point
 In a decimal number, this digit can be from 1 to 9
 In a binary number, this digit should be 1
 Normalized FP Numbers: 5.341×103 and –1.101101×2–3
 NOT Normalized: 0.05341×105 and –1101.101×2–6
 Floating-Point Representation
 A floating-point number is represented by the triple
 S is the Sign bit (0 is positive and 1 is negative)
 Representation is called sign and magnitude
 E is the Exponent field (signed)
 Very large numbers have large positive exponents
 Very small close-to-zero numbers have negative exponents
 More bits in exponent field increases range of values
 F is the Fraction field (fraction after binary point)
 More bits in fraction field improves the precision of FP numbers

S Exponent Fraction

Value of a floating-point number = (-1)S × val(F) × 2val(E)

 Next . . .

 Floating-Point Numbers

 IEEE 754 Floating-Point Standard

 IEEE 754 Floating-Point Standard
 Found in virtually every computer invented since 1980
 Simplified porting of floating-point numbers
 Unified the development of floating-point algorithms
 Increased the accuracy of floating-point numbers
 Single Precision Floating Point Numbers (32 bits)
 1-bit sign + 8-bit exponent + 23-bit fraction
S Exponent8 Fraction23

 Double Precision Floating Point Numbers (64 bits)

 1-bit sign + 11-bit exponent + 52-bit fraction
S Exponent11 Fraction52
(continued)
 Normalized Floating Point
Numbers
 For a normalized floating point number (S, E, F)

S E F = f1 f2 f3 f4 …

 Significand is equal to (1.F)2 = (1.f1f2f3f4…)2

 IEEE 754 assumes hidden 1. (not stored) for normalized numbers
 Significand is 1 bit longer than fraction
 Value of a Normalized Floating Point Number is

(–1)S × (1.F)2 × 2val(E)

(–1)S × (1.f1f2f3f4 …)2 × 2val(E)
(–1)S × (1 + f1×2-1 + f2×2-2 + f3×2-3 + f4×2-4 …)2 × 2val(E)

(–1)S is 1 when S is 0 (positive), and –1 when S is 1 (negative)

 Biased Exponent Representation
 How to represent a signed exponent? Choices are …
 Sign + magnitude representation for the exponent
 Two’s complement representation
 Biased representation
 IEEE 754 uses biased representation for the exponent
 Value of exponent = val(E) = E – Bias (Bias is a constant)
 Recall that exponent field is 8 bits for single precision
 E can be in the range 0 to 255
 E = 0 and E = 255 are reserved for special use (discussed later)
 E = 1 to 254 are used for normalized floating point numbers
 Bias = 127 (half of 254), val(E) = E – 127
 val(E=1) = –126, val(E=127) = 0, val(E=254) = 127
 Biased Exponent – Cont’d
 For double precision, exponent field is 11 bits
 E can be in the range 0 to 2047
 E = 0 and E = 2047 are reserved for special use
 E = 1 to 2046 are used for normalized floating point numbers
 Bias = 1023 (half of 2046), val(E) = E – 1023
 val(E=1) = –1022, val(E=1023) = 0, val(E=2046) = 1023
 Value of a Normalized Floating Point Number is

(–1)S × (1.F)2 × 2E – Bias

(–1)S × (1.f1f2f3f4 …)2 × 2E – Bias
(–1)S × (1 + f1×2-1 + f2×2-2 + f3×2-3 + f4×2-4 …)2 × 2E –
Bias
Examples of Single Precision Float
 What is the decimal value of this Single Precision float?
10111110001000000000000000000000

 Solution:
 Sign = 1 is negative
 Exponent = (01111100)2 = 124, E – bias = 124 – 127 = –3
 Significant = (1.0100 … 0)2 = 1 + 2-2 = 1.25 (1. is implicit)
 Value in decimal = –1.25 × 2–3 = –0.15625
 What is the decimal value of?
01000001001001100000000000000000

 Solution: implicit
 Value in decimal = +(1.01001100 … 0)2 × 2130–127 =
(1.01001100 … 0)2 × 23 = (1010.01100 … 0)2 = 10.375
Examples of Double Precision Float
 What is the decimal value of this Double Precision float ?
01000000010100101010000000000000
00000000000000000000000000000000

 Solution:
 Value of exponent = (10000000101)2 – Bias = 1029 – 1023 = 6
 Value of double float = (1.00101010 … 0)2 × 26 (1. is implicit) =
(1001010.10 … 0)2 = 74.5
 What is the decimal value of ?
10111111100010000000000000000000
00000000000000000000000000000000

 Do it yourself! (answer should be –1.5 × 2–7 = –0.01171875)

 Converting FP Decimal to Binary
 Convert –0.8125 to binary in single and double precision
 Solution:
 Fraction bits can be obtained using multiplication by 2
 0.8125 × 2 = 1.625
 0.625 × 2 = 1.25
0.8125 = (0.1101)2 = ½ + ¼ + 1/16 = 13/16
 0.25 × 2 = 0.5
 0.5 × 2 = 1.0
 Stop when fractional part is 0
 Fraction = (0.1101)2 = (1.101)2 × 2 –1 (Normalized)
 Exponent = –1 + Bias = 126 (single precision) and 1022 (double)
Single
10111111010100000000000000000000
Precision
10111111111010100000000000000000 Double
Precision
00000000000000000000000000000000
 Largest Normalized Float
 What is the Largest normalized float?
 Solution for Single Precision:
01111111011111111111111111111111
 Exponent – bias = 254 – 127 = 127 (largest exponent for SP)
 Significand = (1.111 … 1)2 = almost 2
 Value in decimal ≈ 2 × 2127 ≈ 2128 ≈ 3.4028 … × 1038
 Solution for Double Precision:
01111111111011111111111111111111
11111111111111111111111111111111

 Value in decimal ≈ 2 × 21023 ≈ 21024 ≈ 1.79769 … × 10308

 Overflow: exponent is too large to fit in the exponent field
 Smallest Normalized Float
 What is the smallest (in absolute value) normalized float?
 Solution for Single Precision:
00000000100000000000000000000000
 Exponent – bias = 1 – 127 = –126 (smallest exponent for SP)
 Significand = (1.000 … 0)2 = 1
 Value in decimal = 1 × 2–126 = 1.17549 … × 10–38
 Solution for Double Precision:
00000000000100000000000000000000
00000000000000000000000000000000

 Value in decimal = 1 × 2–1022 = 2.22507 … × 10–308

 Underflow: exponent is too small to fit in exponent field
 Zero, Infinity, and NaN
 Zero
 Exponent field E = 0 and fraction F = 0
 +0 and –0 are possible according to sign bit S
 Infinity
 Infinity is a special value represented with maximum E and F = 0
 For single precision with 8-bit exponent: maximum E = 255
 For double precision with 11-bit exponent: maximum E = 2047
 Infinity can result from overflow or division by zero
 +∞ and –∞ are possible according to sign bit S
 NaN (Not a Number)
 NaN is a special value represented with maximum E and F ≠ 0
 Result from exceptional situations, such as 0/0 or sqrt(negative)
 Operation on a NaN results is NaN: Op(X, NaN) = NaN
 Denormalized Numbers
 IEEE standard uses denormalized numbers to …
 Fill the gap between 0 and the smallest normalized float
 Provide gradual underflow to zero
 Denormalized: exponent field E is 0 and fraction F ≠ 0
 Implicit 1. before the fraction now becomes 0. (not normalized)
 Value of denormalized number ( S, 0, F )

Single precision: (–1) S × (0.F)2 × 2–126

Double precision: (–1) S × (0.F)2 × 2–1022
Negative Negative Positive Positive
Overflow Underflow Underflow Overflow

-∞ Normalized (–ve) Denorm Denorm Normalized (+ve) +∞

-2128 -2–126 0 2–126 2128
 Special Value Rules

Operation Result
n /  0
 x  
nonzero / 0 
+  (similar for -)
0 / 0 NaN
- NaN (similar for -)
 /  NaN
 x 0 NaN
NaN op anything NaN
 Floating-Point Comparison
 IEEE 754 floating point numbers are ordered
 Because exponent uses a biased representation …
 Exponent value and its binary representation have same ordering
 Placing exponent before the fraction field orders the magnitude
 Larger exponent  larger magnitude
 For equal exponents, Larger fraction  larger magnitude
 0 < (0.F)2 × 2Emin < (1.F)2 × 2E–Bias < ∞ (Emin = 1 – Bias)
 Because sign bit is most significant  quick test of signed <

 Integer comparator can compare magnitudes

X = (EX , FX) Integer X<Y
Magnitude X=Y
Y = (EY , FY) Comparator X>Y
 Summary of IEEE 754 Encoding
Single-Precision Exponent = 8 Fraction = 23 Value
Normalized Number 1 to 254 Anything ± (1.F)2 × 2E – 127
Denormalized Number 0 nonzero ± (0.F)2 × 2–126
Zero 0 0 ±0
Infinity 255 0 ±∞
NaN 255 nonzero NaN

Double-Precision Exponent = 11 Fraction = 52 Value

Normalized Number 1 to 2046 Anything ± (1.F)2 × 2E – 1023
Denormalized Number 0 nonzero ± (0.F)2 × 2–1022
Zero 0 0 ±0
Infinity 2047 0 ±∞
NaN 2047 nonzero NaN