Transcript Week 6(PowerPoint) - CS

1 01
10
1 01
01 1 01
How Computers Represent Data - Text Codes
•
A text code is a system that uses binary numbers (1s
and 0s) to represent characters understood by humans
(letters and numerals).
•
An early text code system, called EBCDIC, uses eightbit codes, but is used primarily in older mainframe
systems.
•
In the most common text-code set, ASCII, each
character consists of eight bits (one byte) of data.
ASCII is used in nearly all personal computers.
•
In the Unicode text-code set, each character consists of
16 bits (two bytes) of data.
Text Codes
Code
Examples from the
ASCII Text Code
Character
00110000
0
00110001
1
00110010
2
00110011
3
00110100
4
00110101
5
01000001
A
01000010
B
01000011
C
01000100
D
01000101
E
Goal: Representing Numbers in Binary

Base 10 (decimal) - Numbers are represented using 10
numerals: 0, 1, 2, 3 … 9

Base 2 (binary) - Numbers are represented using 2 numerals:
0, 1

Base 10 - Each position represents a power of 10:
101 = 1*102 + 0*101 + 1*100 = 100 + 1
110 = 1*102 + 1*101 + 0*100 = 100 + 10

Base 2 - Each position represents a power of 2: 101b = 1*22 +
0*21 + 1*20 = 100b + 1b = 4 + 1
110b = 1*22 + 1*21 + 0*20 = 100b + 10b = 4+2



Numbers in base 10 are called decimal numbers,
they are composed of 10 numerals.
d3d2d1d0 = d3*103 + d2*102 + d1*101 + d0*100
9786 = 9*1000 + 7*100 + 8*10 + 6*1
= 9*103 + 7*102 + 8*101 + 6*100
Numbers in base 2 are called binary numbers, they are composed of
the numerals 0 and 1.
b3b2b1b0 = b3*23 + b2*22 + b1*21 + b0*20
110101 = 1*32 + 1*16 + 0*8 + 1*4 + 0*2 + 1*1
= 1*25 + 1*24 + 0*23 + 1*22 + 0*21 + 1*20
1111 1111 1111 1111 = 32768 + 16384 + 8192 +
4096 +
15
2048 + 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 2 + 214 + … +
21 + 20 =
S 2n = 2n+1 - 1 = 216 -1
Converting from Binary to Decimal




Easy: Multiply each numeral by its exponent.
1001b = 1*23 + 1*20 = 1*8 + 1*1 = 9d
0111b = 0*23 + 1*22 + 1*21 + 1*20
= 100b + 10b + 1b
=4+2+1
=7
110110b = 1*25 + 1*24 + 0*23 + 1*22 + 1*21
= 100000b + 10000b + 100b + 10b
= 32 + 16 + 4 + 2
= 54
Converting from Binary to Decimal

Given an array that holds a 32 digit binary number called
binary:

int[] binary = {1, 0, 0, 1};
int decimal = 0;
for(int i=binary.length-1;i>=0;i--)
decimal += binary[i]*Math.pow(2,i);

The powers of 2:
20 = 1
21 = 2
24 = 16
25 = 32
28 = 256 29 = 512
211 = 2048 212 = 4096
216 = 65536
22 = 4
23 = 8
26 = 64
27 = 128
210 = 1024 = 1K
213 = 8192
220 = 1048576 = 1M
Converting From Decimal to Binary
In Java it looks like this:
int decimal = readInt();
int res;
int power;
for(int n=31; n>=0; n--){
power = (int)Math.pow(2,n);
res = decimal/power;
decimal = decimal - res*power;
System.out.print(res);
}
A Base Conversion Example
500/29 = 0 ; 500 - 0 = 500
500/28 = 1 ; 500 - 256 = 244
244/27 = 1 ; 244 - 128 = 116
116/26 = 1 ; 116 - 64 = 52
52/25 = 1 ; 52 - 32 = 20
20/24 = 1 ; 20 - 16 = 4
500d = 111110100b
4/23 = 0 ; 4 - 0 =
4/22 = 1 ; 4 - 4 =
0/21 = 0 ; 0 - 0 =
0/20 = 0 ; 0 - 0 =
4
0
0
0
Representation of Numbers

int, long, short, char - positive numbers are stored as a
binary number where the MSB (Most Significant Bit) is 0
A short is represented by 16 bits (2 bytes)
100d = 26 + 25 + 22 =
0000000001100100
An int is represented by 32 bits (4 bytes)
65545d = 216 + 23 + 20 =
00000000000000010000000000001001
A char is represented by 16 bits (2 bytes)
‘0’ = 48d = 25 + 24 =00000000 00110000
Signed and Unsigned Numbers



How do we distinguish between them?
Solution: Use 1 bit to represents the sign. The name of
this scheme is called:
sign and magnitude
10001111b = -15 00001111b = +15 (8 bit numbers)
There are several problems with this scheme:
• where do we put the sign?
• an extra step is needed to calculate the sign bit
– Add the magnitudes.
– Calculate the sign.
• there is both a positive and negative zero
10000000b = -0
00000000b = +0
Two's Complement





New Solution: Leading 0s mean positive and leading 1s
mean negative.
01111111b > 0
10000000b < 0 (8 bit numbers)
The largest positive number is:
2,147,483,647d (231 -1) = 01111…11111b
The smallest negative number is:
-2,147,483,648d (-231) = 10000…00000b
It is followed by -2,147,483,647d (1000…0001b) up to -1
(1111…1111b).
The sum of a number and its inverse is 100...0, where 1
is an overflow and is thrown away.
Two’s Complement







+3 = 00000011
+2 = 00000010
+1 = 00000001
+0 = 00000000
-1 = 11111111
-2 = 11111110
-3 = 11111101
Benefits



One representation of zero
Arithmetic works easily (see later)
Negating is fairly easy
• 3 = 00000011
• Boolean complement gives 11111100
• Add 1 to LSB
11111101
Geometric Depiction of Twos
Complement Integers
Negative Decimal to Binary



Translate the number to binary.
Flip the bits (1 -> 0, 0 -> 1)
Add 1


-100d = -01100100 = 10011011 + 1 = 10011100
-1d = - 00000001 = 11111110 + 1 = 11111111b
-128d = -10000000 = 01111111 + 1 = 10000000b
11000101b = 00111010 + 1 = 00111011 = -59d
In a short:
-25,000d = -0110000110101000 = 1001111001010111 + 1 =
10011110011000b
Conversion Between Lengths







Positive numbers pack with leading zeros
+18 =
00010010
+18 = 00000000 00010010
Negative numbers pack with leading ones
-18 =
10010010
-18 = 11111111 10010010
i.e. pack with MSB (sign bit)
Hexadecimal Numbers

Numbers in base 16 are called hexadecimal numbers,
they are composed of 16 numerals
(0-9,a-f).
9786hex = 9*163 + 7*162 + 8*161 + 6*160 =
= 9*4096 + 7*256 + 8*16 + 6*1 = 38790d
0xabcdef = 10*165 + 11*164 + 12*163 + 13*162 +
14*161 + 15*160 = 11259375d

The conversion from binary to hex is very easy, each hex digit is 4
binary digits:
0x0 = 0000 0x1 = 0001 0x2 = 0010 0x3 = 0011
0x4 = 0100 0x5 = 0101 0x6 = 0110 0x7 = 0111
0x8 = 1000 0x9 = 1001 0xa = 1010 0xb = 1011
0xc = 1100 0xd = 1101 0xe = 1110 0xf = 1111
Binary <-> Hexadecimal




Using the previous table it is easy to represent 32 bit
binary numbers in a short form:
0100 1010 0010 1101 1000 1100 0111 1001 =
4
a
2
d
8
c
7
9 =
0x4a2d8c79.
0x12390ab4 =
0001 0010 0011 1001 0000 1010 1011 0100
1
2
3
9
0
a
b
4
0xffffffff =
1111 1111 1111 1111 1111 1111 1111 1111
Every 2 Hex digits are a byte
Decimal -> Hexadecimal

Conversion from decimal to hexadecimal is similar to
converting decimal to binary.
int decimal=readInt();
int res;
int power;
for(int n=7;n>=0;n--){
power = (int)Math.pow(16,n);
res = decimal/power;
decimal = decimal - res*power;
if(res>9)
System.out.print((char)((res - 10) + 'a'));
else
System.out.print(res);
}
Octal & Hex in Java

Java allows numbers in octal (start with 0) and
hexadecimal (start with 0x or 0X).
int num1 = 015;
int num2 = 0x1a;
num1 is 13
num2 is 26
Addition
 Lets
add 6 to 7:
00…00111 = 7d
00…00110 = 6d
00…01101 = 13d
 Lets add 11 to 5:
00…01011 = 11d
00…00101 = 5d
00…10000 = 16d
(0)
(0)
(1)
(1)
(0)
(Carries)
0
0
0
1
1
1
0
0
0
1
1
0
(0) 0
(0) 0
(0) 1
(1) 1
(1) 0
(0) 1
Substraction

Subtraction uses addition, the operand is simply
negated before being added:
7 - 6 = 7 + (-6) =
00…00111 = 7d
11…11010 = -6d
00…00001 = 1d
Overflow

Overflow occurs when the result of a operation can't be represented by the
hardware. This can happen when we add two numbers of the same sign or
subtract two large numbers of opposing signs.

Overflow is detected by the following table:
Operation
A+B
A+B
A- B
A- B
A
B
>=0 >=0
<0 <0
>=0 <0
<0 >=0
Result
<0
>=0
<0
>=0
Multiplication

Look at the following pencil and paper example:
X

1000d
1001d
1000
0000
0000
1000
1001000d
By restricting the digits to 1 & 0 (which is binary) the
algorithm is simple, at each step:
• Place a copy of the multiplicand if the multiplier digit is 1.
• Place 0 if the digit is 0.
• The position for the next step is shifted left by one place.
Real Numbers


Numbers with fractions
Could be done in pure binary
• 1001.1010 = 24 + 20 +2-1 + 2-3 =9.625


Where is the binary point?
Fixed?
• Very limited

Moving?
• How do you show where it is?
Sign bit
Floating Point



Biased
Exponent
Significand or Mantissa
+/- .significand x 2exponent
Point is actually fixed between sign bit and body of
mantissa
Exponent indicates place value (point position)
Signs for Floating Point


Mantissa is stored in 2s compliment
Exponent is in excess or biased notation
•
•
•
•
•
e.g. Excess (bias) 128 means
8 bit exponent field
Pure value range 0-255
Subtract 128 to get correct value
Range -128 to +127
Normalization





FP numbers are usually normalized
i.e. exponent is adjusted so that leading bit (MSB) of
mantissa is 1
Since it is always 1 there is no need to store it
(c.f. Scientific notation where numbers are normalized
to give a single digit before the decimal point
e.g. 3.123 x 103)
Floating Point Examples
X
X
X
X
Expressible Numbers
IEEE 754




Standard for floating point storage
32 and 64 bit standards
8 and 11 bit exponent respectively
Extended formats (both mantissa and exponent) for
intermediate results
FP Arithmetic +/-




Check for zeros
Align significands (adjusting exponents)
Add or subtract significands
Normalize result
FP Arithmetic x/






Check for zero
Add/subtract exponents
Multiply/divide significands (watch sign)
Normalize
Round
All intermediate results should be in double length
storage