KAIST - CS230
Bits and Bytes (2/2)
Spring, 2022
Topics
Representing information as bits
Byte representations
» Numbers (Integers and
Floating Pointers)
» characters and strings
» Instructions
CS230 S’22
class03.ppt
Fractional binary numbers
What is 1011.1012?
CS230 S’22
Fractional Binary Numbers
2i
2i-1
4
••• 2
1
bi bi-1 ••• b2 b1 b0 b-1 b-2 b-3 ••• b-j
1/2
1/4 •••
1/8
Representation 2-j
Bits to right of “binary point” represent fractional powers of 2
Represents rational number:
CS230 S’22
Fractional Binary Numbers: Examples
Value Representation
5 3/4 = 23/4 101.112 = 4 + 1 + 1/2 + 1/4
2 7/8 = 23/8 010.1112 = 2 + 1/2 + 1/4 + 1/8
1 7/16 = 23/16 001.01112 = 1 + 1/4 + 1/8 + 1/16
Observations
Divide by 2 by shifting right (unsigned)
Multiply by 2 by shifting left
Numbers of form 0.111111…2 are just below 1.0
1/2 + 1/4 + 1/8 + … + 1/2i + … ➙ 1.0
Use notation 1.0 – ε
CS230 S’22
Representable Numbers
Limitation #1
Can only exactly represent numbers of the form x/2k
Other rational numbers have repeating bit representations
Value Representation
1/3 0.0101010101[01]…2
1/5 0.001100110011[0011]…2
1/10 0.0001100110011[0011]…2
Limitation #2
Just one setting of binary point within the w bits
Limited range of numbers (very small values? very large?)
CS230 S’22
Representing Floats
Float F = 15213.0;
Decimal: 15213
Binary: 0011 1011 0110 1101
Hex: 3 B 6 D
IEEE Single Precision Floating Point Representation
Hex: 4 6 6 D B 4 0 0
Binary: 0100 0110 0110 1101 1011 0100 0000 0000
15213: 1110 1101 1011 01
Not same as integer representation, but consistent across machines
Can see some relation to integer representation, but not obvious
CS230 S’22
IEEE Floating Point
IEEE Standard 754
Established in 1985 as uniform standard for floating point
arithmetic
Before that, many idiosyncratic formats
Supported by all major CPUs
Some CPUs don’t implement IEEE 754 in full
e.g., early GPUs, Cell BE processor
Driven by numerical concerns
Nice standards for rounding, overflow, underflow
Hard to make fast in hardware
Numerical analysts predominated over hardware designers
in defining standard
CS230 S’22
Floating Point Representation
Example:
Numerical Form: 1521310 = (-1)0 x 1.11011011011012 x 213
(–1)s M 2E
Sign bit s determines whether number is negative or positive
Significand M normally a fractional value in range [1.0,2.0).
Exponent E weights value by power of two
Encoding
MSB s is sign bit s
exp field encodes E (but is not equal to E)
frac field encodes M (but is not equal to M)
s exp frac
CS230 S’22
Precision options
Single precision: 32 bits
≈ 7 decimal digits, 10±38
s exp frac
1 8-bits 23-bits
Double precision: 64 bits
≈ 16 decimal digits, 10±308
s exp frac
1 11-bits 52-bits
Other formats: half precision, quad precision
CS230 S’22
Three “kinds” of floating point
numbers
s exp frac
1 e-bits f-bits
00…00 exp ≠ 0 and exp ≠ 11…11 11…11
denormalized normalized special
CS230 S’22
“Normalized” Values v = (–1)s M 2E
When: exp ≠ 000…0 and exp ≠ 111…1
Exponent coded as a biased value: E = exp – Bias
exp: unsigned value of exp field
Bias = 2k-1 - 1, where k is number of exponent bits
Single precision: 127 (exp: 1…254, E: -126…127)
Double precision: 1023 (exp: 1…2046, E: -1022…1023)
Significand coded with implied leading 1: M = 1.xxx…x2
xxx…x: bits of frac field
Minimum when frac=000…0 (M = 1.0)
Maximum when frac=111…1 (M = 2.0 – ε)
Get extra leading bit for “free” CS230 S’22
Normalized Encoding Example
Value: float F = 15213.0; v = (–1)s M 2E
1521310 = 111011011011012
E = exp – Bias
= 1.11011011011012 x 213
Significand
M = 1.11011011011012
frac = 110110110110100000000002
Exponent
E = 13
Bias = 127
exp = 140 = 100011002
Result:
0 10001100 11011011011010000000000
s exp frac CS230 S’22
Denormalized Values v = (–1)s M 2E
E = 1 – Bias
Condition: exp = 000…0
Exponent value: E = 1 – Bias (instead of exp – Bias) (e.g. single
precision: -126)
Significand coded with implied leading 0: M = 0.xxx…x2
xxx…x: bits of frac
Cases
exp = 000…0, frac = 000…0
Represents zero value
Note distinct values: +0 and –0 (depending on sign bit)
exp = 000…0, frac ≠ 000…0
Numbers closest to 0.0
Equispaced
CS230 S’22
Special Values
Condition: exp = 111…1
Case: exp = 111…1, frac = 000…0
Represents value ∞ (infinity)
Operation that overflows
Both positive and negative
E.g., 1.0/0.0 = −1.0/−0.0 = +∞, 1.0/−0.0 = −∞
Case: exp = 111…1, frac ≠ 000…0
Not-a-Number (NaN)
Represents case when no numeric value can be determined
E.g., sqrt(–1), ∞ − ∞, ∞ × 0
CS230 S’22
C float Decoding Example v = (–1)s M 2E
E = exp – Bias
float: Bias = 2k-1 – 1 = 127
0xC0A00000
binary:
1 8-bits 23-bits
E = 129
S = 1 -> negative number
M = 1.010 0000 0000 0000 0000 0000
M = 1 + 1/4 = 1.25
v = (–1)s M 2E =
CS230 S’22
C float Decoding Example #1v = (–1)s M 2E
E = exp – Bias
float:
0xC0A00000
binary: 1100 0000 1010 0000 0000 0000 0000 0000
1 1000 0001 010 0000 0000 0000 0000 0000
1 8-bits 23-bits
E = 129
S = 1 -> negative number
M = 1.010 0000 0000 0000 0000 0000
M = 1 + 1/4 = 1.25
v = (–1)s M 2E =
CS230 S’22
C float Decoding Example #1v = (–1)s M 2E
E = exp – Bias
float: Bias = 2k-1 – 1 = 127
0xC0A00000
binary: 1100 0000 1010 0000 0000 0000 0000
0000
1 1000 0001 010 0000 0000 0000 0000 0000
1 8-bits 23-bits
E = exp – Bias = 129 – 127 = 2 (decimal)
S = 1 -> negative number
M = 1.010 0000 0000 0000 0000 0000
M = 1 + 1/4 = 1.25
v = (–1)s M 2E = (-1)1 * 1.25 * 22 = -5
CS230 S’22
C float Decoding Example #2 v = (–1)s M 2E
E = 1 – Bias
float:
0x001C0000
binary: 0000 0000 0001 1100 0000 0000 0000 0000
0 0000 0000 001 1100 0000 0000 0000 0000
1 8-bits 23-bits
E = 129
S = 1 -> negative number
M = 0.010 0000 0000 0000 0000 0000
M = 1 + 1/4 = 1.25
v = (–1)s M 2E =
CS230 S’22
C float Decoding Example #2 v = (–1)s M 2E
E = 1 – Bias
float: Bias = 2k-1 – 1 = 127
0x001C0000
binary: 0000 0000 0001 1100 0000 0000 0000
0000
0 0000 0000 001 1100 0000 0000 0000 0000
1 8-bits 23-bits
E = 1 – Bias = 1 – 127 = –126 (decimal)
S = 0 -> positive number
M = 0.001 1100 0000 0000 0000 0000
M = 1/8 + 1/16 + 1/32 = 7/32 = 7*2–5
v = (–1)s M 2E = (-1)0 * 7*2–5 * 2–126 = 7*2–131
v ≈ 2.571393892 X 10–39 CS230 S’22
Visualization: Floating Point Encodings
−∞ +∞
−Normalized −Denorm +Denorm +Normalized
NaN NaN
−0 +0
CS230 S’22
Tiny Floating Point Example
s exp frac
1 4-bits 3-bits
8-bit Floating Point Representation
the sign bit is in the most significant bit
the next four bits are the exp, with a bias of 7
the last three bits are the frac
Same general form as IEEE Format
normalized, denormalized
representation of 0, NaN, infinity
CS230 S’22
Dynamic Range (s=0 only) v = (–1)s M 2E
norm: E = exp – Bias
s exp frac E Value
denorm: E = 1 – Bias
0 0000 000 -6 0
0 0000 001 -6 1/8*1/64 = 1/512 closest to zero
Denormalized 0 0000 010 -6 2/8*1/64 = 2/512 (-1)0(0+1/4)*2-6
numbers …
0 0000 110 -6 6/8*1/64 = 6/512
0 0000 111 -6 7/8*1/64 = 7/512 largest denorm
0 0001 000 -6 8/8*1/64 = 8/512 smallest norm
0 0001 001 -6 9/8*1/64 = 9/512 (-1)0(1+1/8)*2-6
…
0 0110 110 -1 14/8*1/2 = 14/16
0 0110 111 -1 15/8*1/2 = 15/16 closest to 1 below
Normalized 0 0111 000 0 8/8*1 = 1
numbers 0 0111 001 0 9/8*1 = 9/8 closest to 1 above
0 0111 010 0 10/8*1 = 10/8
…
0 1110 110 7 14/8*128 = 224
0 1110 111 7 15/8*128 = 240 largest norm
0 1111 000 n/a inf
CS230 S’22
Distribution of Values
6-bit IEEE-like format
e = 3 exponent bits
f = 2 fraction bits s exp frac
Bias is 23-1-1 = 3
1 3-bits 2-bits
Notice how the distribution gets denser toward zero.
8 values
-15 -10 -5 0 5 10 15
Denormalized Normalized Infinity
CS230 S’22
Distribution of Values (close-up view)
6-bit IEEE-like format
e = 3 exponent bits
f = 2 fraction bits s exp frac
Bias is 3
1 3-bits 2-bits
-1 -0.5 0 0.5 1
Denormalized Normalized Infinity
CS230 S’22
Special Properties of the IEEE Encoding
FP Zero Same as Integer Zero
All bits = 0
Can (Almost) Use Unsigned Integer Comparison
Must first compare sign bits
Must consider −0 = 0
NaNs problematic
Will be greater than any other values
What should comparison yield? The answer is complicated.
Otherwise OK
Denorm vs. normalized
Normalized vs. infinity
CS230 S’22
Floating Point Operations: Basic Idea
x +f y = Round(x + y)
x ×f y = Round(x × y)
Basic idea
First compute exact result
Make it fit into desired precision
Possibly overflow if exponent too large
Possibly round to fit into frac
CS230 S’22
Rounding
Rounding Modes (illustrate with $ rounding)
$1.40 $1.60 $1.50 $2.50 –$1.50
Towards zero $1 $1 $1 $2 –$1
Round down (−∞) $1 $1 $1 $2 –$2
Round up (+∞) $2 $2 $2 $3 –$1
Nearest Even* (default) $1 $2 $2 $2 –$2
*Round to nearest, but if half-way in-between then round to nearest even
CS230 S’22
Rounding Binary Numbers
Binary Fractional Numbers
“Even” when least significant bit is 0
“Half way” when bits to right of rounding position = 100…2
Examples
Round to nearest 1/4 (2 bits right of binary point)
Value Binary Rounded Action Rounded Value
2 3/32 10.000112 10.002 (<1/2—down) 2
2 3/16 10.001102 10.012 (>1/2—up) 2 1/4
2 7/8 10.111002 11.002 ( 1/2—up) 3
2 5/8 10.101002 10.102 ( 1/2—down) 2 1/2
CS230 S’22
Rounding 1.BBGRXXX
Guard bit: LSB of result
Sticky bit: OR of remaining bits
Round bit: 1st bit removed
Round up conditions
Round = 1, Sticky = 1 ➙ > 0.5
Guard = 1, Round = 1, Sticky = 0 ➙ Round to even
Fraction GRS Incr? Rounded
1.0000000 000 N 1.000
1.1010000 100 N 1.101
1.0001000 010 N 1.000
1.0011000 110 Y 1.010
1.0001010 011 Y 1.001
1.1111100 111 Y 10.000
CS230 S’22
Representing Strings
char S[6] = "15213";
Strings in C
Represented by array of characters
Linux/Alpha S Sun S
Each character encoded in ASCII format
Standard 7-bit encoding of character set 31 31
Other encodings exist, but uncommon 35 35
Character “0” has code 0x30 32 32
» Digit i has code 0x30+i 31 31
33 33
String should be null-terminated 00 00
Final character = 0
Compatibility
Byte ordering not an issue
Data are single byte quantities
Text files generally platform independent
Except for different conventions of line termination character(s)!
CS230 S’22
Machine-Level Code Representation
Encode Program as Sequence of Instructions
Each simple operation
Arithmetic operation
Read or write memory
Conditional branch
Instructions encoded as bytes
Alpha’s, Sun’s, Mac’s use 4 byte instructions
» Reduced Instruction Set Computer (RISC)
PC’s use variable length instructions
» Complex Instruction Set Computer (CISC)
Different instruction types and encodings for different
machines
Most code not binary compatible
Programs are Byte Sequences Too!
CS230 S’22
Representing Instructions
int sum(int x, int y)
{ Alpha sum Sun sum PC sum
return x+y; 00 81 55
} 00 C3 89
30 E0 E5
For this example, Alpha &
42 08 8B
Sun use two 4-byte
01 90 45
instructions
80 02 0C
Use differing numbers of
FA 00 03
instructions in other cases
6B 09 45
PC uses 7 instructions with 08
lengths 1, 2, and 3 bytes 89
Same for NT and for Linux EC
NT / Linux not fully binary 5D
compatible C3
Different machines use totally different instructions and encodings
CS230 S’22
Ariane 5 S/W Bug
Ariane 5 flight 501 (June 4, 1996)
Exploded 37 seconds after liftoff
Lost 4 cluster mission
spacecraft worth $370 million
Why?
Computed horizontal velocity as
floating point number (64bit)
Converted to 16-bit integer
Careful analysis of Ariane 4
trajectory proved 16-bit is enough
Reused a module from 10-year-old
software
Overflowed for Ariane 5
No precise specification for the S/W
CS230 S’22
