CMPT 295
Unit - Data Representation
Lecture 3 – Representing integral numbers in memory - unsigned and signed
1
Last Lecture
von Neumann architecture
Architecture of most computers
Its components: CPU, memory, input and ouput, bus
One of its characteristics: Data and instructions (code/programs) both stored in memory
A look at memory: defined byte-addressable memory, (compressed) diagram of memory
A look at memory content
Why we abstract the content of a memory cell using the two values of the binary numeral
system -> ‘0’ and ‘1’
Algorithm for converting binary to hexadecimal (hex)
1. Partition bit vector into groups of 4 bits, starting from right, i.e., least significant byte (LSB)
If most significant byte (MSB) does not have 8 bits, pad it: add 0’s to its left
Determined by a 2. Translate each group of 4 bits into its hex value
microprocessor.
Describes how a Encoding scheme gives meaning to bit vectors (memory content)
NOTE:
microprocessor little endian versus big endian: Order in which bytes are stored in memory C logical
orders the bytes Bit manipulation – regardless of what a bit vector represents operators and
when it reads them C bitwise (bit-
from and writes Boolean algebra: bitwise operations => AND (&), OR (|), XOR (^), NOT (~) level) operators
them to memory. Shift operations: left shift x << y, logical and arithmetic right shift x >> y behave
differently!
Right logical shift: Fill x with y 0’s on the left of x
2 Watch out for
Right arithmetic shift: Fill x with y copies of x‘s sign bit on the left of x && versus &,
Sign bit is most significant bit (MSb) before shifting occurred || versus |, …
If memory size is 26 bytes, then size = 64 bytes. In order to access each
From Lecture 2 of the 64 bytes of memory, we need 64 distinct memory addresses. To
express each of these 64 memory addresses, we require 6 bits.
size-1
size-1
= 6310
= 0x003F
leading zeros
= 0x3F
= 001111112
6 bits
leading zeros
63
3
Today’s Menu
Representing data in memory
“Under the Hood” - von Neumann architecture
Bits and bytes in memory
How to diagram memory -> used in this course and other references
How to represent memory content (series of bits) -> in binary, in hexadecimal and conversion
What kind of information (data) do series of bits represent -> encoding scheme
Order of bytes in memory -> endian
Bit manipulation – bitwise operations
Boolean algebra + shifting
Representing integral numbers in memory
Unsigned and signed
Converting, expanding and truncating
Arithmetic operations
Representing real numbers in memory
4 IEEE floating point representation
Floating point in C – casting, rounding, addition, …
Warm up exercise!
As a warm up exercise, fill in the blanks!
If the context is C (on our target machine)
char => _____ bits/ _____ byte
short => _____ bits/ _____ bytes
int => _____ bits/ _____ bytes
long => _____ bits/ _____ bytes
float => _____ bits/ _____ bytes
double=> _____ bits/ _____ bytes
pointer (e.g. char *)
5 => _____ bits/ _____ bytes
Remember
from our
Unsigned integral numbers previous
lecture:
What if the byte at M[0x0002] represented an unsigned integral
bit vector or
bit pattern
number, what would be its value?
X = 011010012 w=8 w =>width of
the bit vector
w−1
xi 2
i
B2U(X) =
Let’s apply the encoding scheme: i=0
0 x 27 + 1 x 2 6 + 1 x 2 5 + 0 x 2 4 + 1 x 2 3 + 0 x 2 2 + 0 x 2 1 + 1 x 2 0 =
For w = 8, range of possible unsigned values: [ ]
For any w, range of possible unsigned values: [ ]
6
B2U(X) Encoding Scheme (conversion)
Positional notation: expand and sum all terms
10i 2i
10i-1 2i-1
100 4
••• 10 ••• 2
1 1
di di-1 ••• d2 d1 d0
w−1
xi 2
i
Example: 24610 = 2 x 102 + 4 x 101 + 6 x 100 B2U(X ) =
i=0
1’s = 100
7 10’s = 101
100’s = 102
Homework 1
Range of possible values?
If the context is C on our target machine
unsigned char?
unsigned short?
unsigned int?
unsigned long?
8
Examples of “Show your work”
U2B(X) Conversion (into 8-bit binary numbers => w = 8)
Method 1 - Using subtraction: Method 2 - Using division:
subtracting decreasing dividing by 2
power of 2 until reach 0 until reach 0
24610 => 246 – 128 = 118 ->128 = 1 x 27 24610 => 246 / 2 = 123 -> R = 0
118 – 64 = 54 -> 64 = 1 x 26 123 / 2 = 61 -> R = 1
54 – 32 = 22 -> 32 = 1 x 25 61 / 2 = 30 -> R = 1
22 – 16 = 6 -> 16 = 1 x 24 30 / 2 = 15 -> R = 0
6 – 8 = nop! -> 8 = 0 x 23 15 / 2 = 7 -> R = 1
6 – 4=2 -> 4 = 1 x 22 7/2 =3 -> R = 1
2– 2=0 -> 2 = 1 x 21 3/2 =1 -> R = 1
0 – 1 = nop! -> 1 = 0 x 20 1/2 =0 -> R = 1
9 246 => 1 1 1 1 0 1 1 02 246 => 1 1 1 1 0 1 1 02
Always check your answer! How?
U2B(X) Conversion – A few tricks
Decimal -> binary
Trick: When decimal number is 2n, then its binary representation is 1 followed
by n zeros
Let’s try: if X = 32 => X = 25, then n = 5 => 1000002 (w = 6)
What if w = 8?
Decimal -> hex
Trick: When decimal number is 2n, then its hexadecimal representation is 2i
followed by j zeros, where n = i + 4j and 0 <= i <=3
Let try: if X = 8192 => X = 213, then n = 13 and 13 = i + 4j => 1 + 4 x 3
=> 0x2000
Two ways to check answer:
1. Convert hex number into a binary number, then use conversion B2U(…)
10
2. 1 x 25 = 32, 2 x 163 = 2 x 4096 = 8192
Remember:
Let’s change the content of
Signed integral numbers M[0x0001] to 111101002 ?
11110100
What if the byte at M[0x0001] represented a signed integral
number, what would be its value? T => Two’s Complement w =>width of
the bit vector
X = 111101002 w = 8 w−2
w−1 i
Let’s apply the encoding scheme: B2T (X ) = − xw−1 2 + xi 2
i=0
Sign bit
-1 x 27 + 1 x 26 + 1 x 25 + 1 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 0 x 20 =
What would be the bit pattern of the …
Most negative value (TMin):
Most positive value (TMax):
For w = 8, range of possible signed values: [ ]
11 For any w, range of possible signed values: [ ]
Examples of “Show your work”
T2B(X) Conversion -> Two’s Complement
w=8
Method 1 If X < 0, (~(U2B(|X|)))+1 Method 2 If X < 0, U2B(X + 2w)
If X = -14 If X = -14
1. |X| => |-14| = 1. X + 2w => -14 +
2. U2B(14) => 2. U2B(242) =>
3. ~(000011102) =>
Using subtraction:
242 – 128 = 114 -> 1 x 27
4. (111100012)+1 => 114 – 64 = 50 -> 1 x 26
50 – 32 = 18 -> 1 x 25
Binary addition: 18 – 16 = 2 -> 1 x 24
11110001 2 – 8 -> nop! -> 0 x 23
+ 00000001 2 – 4 -> nop! -> 0 x 22
2–2=0 -> 1 x 21
0 – 1 -> nop! -> 0 x 20
12
Always check your answer! How?
Properties of unsigned & signed conversions
w=4
X B2U(X) B2T(X)
0000 0 0
0001 1 1 Equivalence
0010 2 2
0011 3 3 Both encoding schemes (B2U
0100 4 4 and B2T ) produce the same bit
0101 5 5 patterns for nonnegative values
0110 6 6
0111 7 7 Uniqueness
1000 8 –8 Every bit pattern produced by
1001 9 –7
these encoding schemes (B2U
1010 10 –6
1011 11 –5 and B2T ) represents a unique
1100 12 –4 (and exact) integer value
13
1101 13 –3 Each representable integer has
1110 14 –2
unique bit pattern
1111 15 –1
Converting unsigned signed – Method 1
of same size (same data type)
Unsigned Signed (Two’s Complement)
U2T
ux U2B X B2T x
w=8
If ux = 12910 then x =
Maintain Same Bit Pattern
Signed (Two’s Complement) T2U Unsigned
x T2B X B2U ux
w=4
Homework 2: If x = -510 then ux =
Maintain Same Bit Pattern
Conclusion - Converting between unsigned and signed numbers:
Both have same bit pattern, however, this bit pattern may be interpreted
14
differently, i.e., producing a different integral value
Converting unsigned signed – Method 2
w=4 Signed Bits Unsigned
0 0000 0
1 0001 T2U(X) 1
2 0010 2
3 0011 3
4 U2T(X) 0100 4
5 0101 5
6 0110 6
7 0111 7 Step 1 of
-8 1000 8 Method 2
on Slide 11
-7 1001 9
-6 1010 10
-5 + 16 (+24) 1011 T2U(X) 11
-4 1100 - 16 (-24) 12
-3 U2T(X) 1101 13
-2 1110 14
15
-1 1111 15
15
Visualizing the relationship between
signed & unsigned
UMax
If w = 4, 24 = 16 UMax – 1
-16
TMax + 1 Unsigned
TMax TMax Range
+16
Signed 0 0
(Two’s Complement) –1
Range –2
16
TMin
Converting unsigned (or signed) of different
sizes (i.e., data types) in C
X •••
1. Small data type -> larger data type
Sign extension (may require padding)
Unsigned: zero extension X 0 0 • • • 0 0 •••
Sign bit
Signed: sign bit extension X •••
Conclusion: Value unchanged
•••
Let’s try: X ••• •••
Going from a data type that has a width of 3 bits (w = 3) to a data
type that has a width of 5 bits (w = 5)
Unsigned: X = 3 => 0112 w = 3
new X = <= w=5
Signed: X = 3 => 0112 w = 3 X = -3 => 1012 w = 3
17 new X = <= w=5 new X = <= w=5
Converting unsigned (or signed) of different
sizes (i.e., data types) in C
2. Large data type -> smaller data type
Truncation X ••• •••
Conclusion: Value may be altered
X •••
Let’s try:
Going from a data type that has a width of 5 bits (w = 5) to a data
type that has a width of 3 bits (w = 3)
Unsigned: X = 27 => 110112 w = 5
new X = <= w=3
Signed: X = -15 => 100012 w = 5 X = -1 => 111112 w = 5
18 new X = <= w=3 new X = <= w=3
Summary
Interpretation of bit pattern B into either unsigned value U or signed value T
B2U(X) and U2B(X) encoding schemes (conversion)
B2T(X) and T2B(X) encoding schemes (conversion)
Signed value expressed as two’s complement => T
Conversions from unsigned <-> signed values
Method 1: U2T(X) and T2U(X) => U2B(X) then B2T(X), T2B(X) then B2U(X)
Method 2: U2T(X) and T2U(X) => adding or subtracting 2w
Implication in C: when converting (implicitly via promotion and explicitly via casting):
Sign:
Unsigned <-> signed (of same size) -> Both have same bit pattern, however,
this bit pattern may be interpreted differently
Can have unexpected effects -> producing a different value
Size:
Small -> large (for signed, e.g., short to int and for unsigned, e.g., unsigned short to unsigned int)
sign extension: For unsigned -> zeros extension, for signed -> sign bit extension
Both yield expected result –> resulting value unchanged
Large -> small (e.g., unsigned int to unsigned short)
truncation: Unsigned/signed -> most significant bits are truncated (discarded)
May not yield expected results -> original value may be altered
19 Both (sign and size): 1) size conversion is first done then 2) sign conversion is done
(e.g., int to unsigned short or unsigned short to int )
Next Lecture
Representing data in memory
“Under the Hood” - von Neumann architecture
Bits and bytes in memory
How to diagram memory -> used in this course and other references
How to represent memory content (series of bits) -> in binary, in hexadecimal and conversion
What kind of information (data) do series of bits represent -> encoding scheme
Order of bytes in memory -> endian
Bit manipulation – bitwise operations
Boolean algebra + shifting
We shall demonstrate Representing integral numbers in memory
with a demo what we Unsigned and signed
covered today!
Converting, expanding and truncating
Arithmetic operations
Representing real numbers in memory
20 IEEE floating point representation
Floating point in C – casting, rounding, addition, …
