Data Representation
Using binary numbers to represent information
Data Representation
■ Goal: Store numbers, characters, sets, database records in the computer.
■ What we got: Circuit that stores 2 voltages, one for logic 0 (0 volts) and one for logic 1 (ex: 3.3 volts).
CSE 12 Fall 2020
2
Storing Information
Value Representation Value Representation Value Representation H 0 False 0 1e-4 0
T 1 True 1 5 1
• Use more bits for more items
• Three bits can represent 8 things: 000,001,…,111 • N bits can represent 2N things
N bits
8
16
32
64
Can represent
256
65,536
4,294,967,296
1.8446…x1019
Which is approximately
256
65 thousand (64K where K=1024)
4 billion
20 billion billion
CSE 12 Fall 2020
3
Storing Information
Byte is a unit of information. Remember 1 byte = 8 bits
Most computers today use:
Type
Character Integers Addresses
# of bits
8-16 32-64 32-64
CSE 12 Fall 2020
4
Integer Representation
Usual answers:
1. Represent0andconsecutivepositiveintegers • Unsigned integers
2. Representpositiveandnegativeintegers • Signed magnitude
• One’s complement
• Two’s complement
Unsigned and two’s complement the most common
CSE 12 Fall 2020
9
Unsigned Integers
• Integer represented is binary value of bits:
0000 -> 0, 0001 -> 1, 0010 -> 2, …
• Encodes only positive values and zero •Range: 0 to 2n –1, for n bits
CSE 12 Fall 2020
10
Unsigned Integers
If we have 4 bit numbers:
To find range make n = 4. Thus 24–1 is 15 Thus the values possible are 0 to 15
[0:15] = 16 different numbers
7 would be 0111
17 not represent-able -3 not represent-able
For 32 bits:
Range is 0 to 232 – 1 = [0: 4,294,967,295] Which is 4,294,967,296 different numbers
CSE 12 Fall 2020
11
Signed Magnitude Integers
• A human readable way of getting both positive and negative integers.
CSE 12 Fall 2020
12
Signed Magnitude Integers
Representation:
■ Use 1 bit of integer to represent the sign of the integer
◆ Signbitismsb:0is“+”,1is”–”
■ Rest of the integer is a magnitude, with same
encoding as unsigned integers.
■ To get the additive inverse of a number, just flip (invert, complement) the sign bit.
■ Range: -(2n-1 – 1) to 2n-1 -1 CSE 12 Fall 2020
13
Signed Magnitude – Example
If 4 bits then range is: -23 +1to23 –1
which is -7 to +7
Given only 4 bits to represent signed magnitude, what integer the following binary numbers represent:
0 101 = + 5 1 011 = 1011
•+12 is ? •Not possible range is -7 …. +7
• [-7,…, -1, 0, +1,…,+7] = 7 + 1 + 7 = 15 < 16 =
• What problems does this cause? CSE 12 Fall 2020
• 0101 is • -3 is ?
14
Signed Magnitude - Example
If 4 bits then range is: -23 +1to23 –1
which is -7 to +7
Questions:
•0101is0 101=+5
•-3 is ? is 1 011 = 1011
• +12 is ? Not possible range is -7 .... +7
• [-7,..., -1, 0, +1,...,+7] = 7 + 1 + 7 = 15 < 16 =
• What problems does this cause?
0 = 1 000 (negative zero)
0 = 0 000 (positive zero)
You are wasting two unique binary numbers (1000
and 0000) in representing the same integer value! CSE 12 Fall 2020
15
One’s Complement
• Historically important (in other words, not used today!!!)
• Early computers built by Semour Cray (while at CDC)
were based on 1’s complement integers.
• Positive integers use the same representation as unsigned.
• 0000 is 0
•0111 is 7, etc
• Negation is done by taking a bitwise complement of the positive representation.
• Complement = Invert = Not = Flip = {0 -> 1, 1 -> 0}
• A logical operation done on a single bit • Top bit is sign bit
CSE 12 Fall 2020
16
One’s Complement Representation
To get 1’s complement of –1
• Take +1: 0001 •Complementeachbit: 1110
• Don’t add or take away any bits.
Another example:
• 1100 ->flip 0011 3 -> -3
• This must be a negative number. To find out which,
find the inverse!
•0011 is +3
• 1100 in 1’s Complement must be?
Properties of 1’s complement:
• Any negative number will have a 1 in the MSB •Whatis0000? 0
• What is 1111? -0
CSE 12 Fall 2020
17
Two’s
Complement
• Variation on 1’s complement that does not have 2 representations for 0.
• This makes the hardware that does arithmetic simpler and faster than the other representations.
• The negative values are all “slid” by one, eliminating the –0 case.
• How to get 2’s complement representation:
• Positive: just as if unsigned binary • Negative:
• Take the positive value
• Take the 1’s complement of it • Add 1
CSE 12 Fall 2020
18
Two’s
Complement
Example, what is -5 in 2SC?
1. What is 5? 0101
2. Invert all the bits: 1010 (basically find the 1SC) 3.Addone: 1010+1=1011whichis-5in2SC
To get the additive inverse of a 2’s complement integer
1. Take the 1’s complement 2. Add 1
CSE 12 Fall 2020
19
What value is my negative number?
■ Assume 4-bit number…
◆ 1100 is negative, but what number is it? ◆ Take 2SC again using same method!
★ Invert all bits ★ Add 1
1100 > 0011 + 0001 0100
CSE 12 Fall 2020
20
Visualizing Signed Numbers
000
001
010
011
100
101
110
111
■ Signed Magnitude
■ One’s Complement
■ And… Two’s Complement
CSE 12 Fall 2020
unsigned
0
1
2
3
4
5
6
7
signed magnitude
0
1
2
3
-0
-1
-2
-3
1’s Complement
0
1
2
3
-3
-2
-1
-0
2’s Complement
0
1
2
3
-4
-3
-2
-1
21
Two’s
Complement
Number of integers representable is -2n-1 to 2n-1-1
So if 4 bits:
[-8,…,-1,0,+1,…,+7] = 8 + 1 + 7 = 16 = 24 numbers
CSE 12 Fall 2020
22
Interesting observation about 2SC representation
■ Assume you use n bits to represent your 2SC number
■ The integer 0 is always represented as 0….0 (n times)
■ The integer -1 is always represented as 11…..111 (n times)
CSE 12 Fall 2020
23
Sign Extension
How to change a number with a smaller number of bits into the same number (same representation) with a larger number of bits?
This must be done frequently by arithmetic units
0010 = 2 (4 bits)
0000 0010 = 2 (8 bits)
CSE 12 Fall 2020
29
Sign Extension – unsigned
Unsigned representation:
Copy the original integer into the LSBs, and put 0’s elsewhere.
Thus for 5 bits to 8 bits: xxxxx -> 000xxxxx
CSE 12 Fall 2020
30
Sign Extension – signed magnitude
Signed magnitude:
Copy the original integer’s magnitude into the LSBs & put the original sign into the MSB, put 0’s elsewhere.
Thus for 6 bits to 8 bits sxxxxx -> s00xxxxx
CSE 12 Fall 2020
31
Sign Extension – 1SC and 2SC
1’s and 2’s complement:
1. Copytheoriginaln-1bitsintotheLSBs
2. TaketheMSBoftheoriginalandcopyitelsewhere
Thus for 6 bits to 8 bits: sxxxxx -> sssxxxxx
CSE 12 Fall 2020
32
Sign Extension
What is -12 in 8-bit 2’s complement form 12
0000 1100 -> Binary
1111 0011 -> flip
1111 0100 -> +1
CSE 12 Fall 2020
33
Arithmetic and Logical Operations
Logical Operations
■ Operate on raw bits with 1 = true and 0 = false AND OR NAND NOR XOR XNOR
0
1
1
In2
1
0
1
0
0
1
|
1
1
1
~(&)
1
1
0
0
0
0
1
1
0
0
0
1
CSE 12 Fall 2020
In1
0
0
&
0
0
1
~(|)
1
^
0
~(^)
1
35
Logical Operations
■ “bit-wise” logical operations are done in parallel for corresponding bits
◆ Example & (AND): ★ X = 0011
★ Y = 1010
★ X AND Y = ?
CSE 12 Fall 2020
36
Logical Operations
■ “bit-wise” logical operations are done in parallel for corresponding bits
◆ Example & (AND): ★ X = 0011
★ Y = 1010
★X AND Y =X&Y=0010
CSE 12 Fall 2020
37