Transcript Integer Representation

Integer Representations &
Base Conversion
Section 3.6
MSU/CSE 260 Fall 2009
1
Object Representation
.
Objects/Concepts
.
Representation
A one-to-one function is required
MSU/CSE 260 Fall 2009
2
Object Representation…
Need symbols; how many?
What are other issues?





Physical cost of representation
Representation and algorithms
We’ll concentrate on “number” representation.
MSU/CSE 260 Fall 2009
3
ASCII code for characters
CHAR CODE
A 001000001
B 001000010
C 001000011
+ 000101011
*
000101010
CHAR CODE
a
001100001
b
001100010
c
001100011
.
000101110
% 000100101
MSU/CSE 260 Fall 2009
4
Encoding baseball teams
Fixed size 3-bit code
A’s
000

Cardinals 001

Mariners 010

Orioles
011

Tigers
100

Twins
101
Which set of teams?
011100101000

Variable size coding
A’s
1

Cardinals 01

Mariners
0000

Orioles
0001

Tigers
0010

Twin
0011
Which set of teams?
01100010011

MSU/CSE 260 Fall 2009
5
2^n strings of exactly n bits each in length:
uniform length code








n=1: {0,1}
n=2: {00, 01, 10, 11}
n=3: {000,001,010,011, 100,101,110,111}
n=8: 256 unique strings (character set)
n=10: 1024 strings
n=30: over one billion strings
n=33: unique string for every person
n=64: new IP address size
MSU/CSE 260 Fall 2009
6
Physical reps for 0 and 1





Up versus Down
5 volts versus 0 volts
Hot versus cold
Pit versus no pit on CD surface
Red checker versus black checker
MSU/CSE 260 Fall 2009
7
CD has many tracks of spots





Shiny spot is 0
Burned spot is 1
5 billion spots total
700 MB total
44,000 x 16 spots for
just 1 second of high
fidelity music
Laser reads shiny
versus dull spots
CD
CD spins
MSU/CSE 260 Fall 2009
8
Example: Numbers Using only one symbol
▲
1
▲▲
2
3
.
.
.
12
▲▲▲
▲▲▲▲▲▲▲▲▲▲▲▲
.
.
.
As long as we have a one-to-one function, we have a correct presentation
MSU/CSE 260 Fall 2009
9
Example: Using two symbols
▲■▲▲
1
■▲
2
▲■
3
.
.
.
12
▲
.
.
.
As long as we have a one-to-one function, we have a correct presentation
MSU/CSE 260 Fall 2009
10
Example: Using two symbols
▲
1
▲▲
2
▲▲▲
3
.
.
.
12
▲■▲▲
.
.
.
As long as we have a one-to-one function, we have a correct presentation
MSU/CSE 260 Fall 2009
11
Understanding Number Representation


We usually use {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} as base to
write numbers, but we can use any base.
Remember that :
453  4  10  5  10  3  10
2



1
0
The above is a positional system representation
It has a “compact” manual
There are other representations
MSU/CSE 260 Fall 2009
12
Representation of Integers…

Theorem: Let b be a positive integer > 1. We can write
every positive integer uniquely in the following form:
n  ak b  ak 1b
k

k 1

 a1b  a0b
1
0
where k is a positive integer and
a0, a1, …ak {0, 1, 2, …, b – 1} and ak ≠ 0.
Example:
453  4  10  5  10  3  10
2
1
n  a2b  a1b  a0b
2
MSU/CSE 260 Fall 2009
1
0
0
13
Base conversion
To convert a number, say 6543, in base 10 to an
equivalent number in another base, say 7, we need
to come up with the coefficients in the following
expression:

6543  a4 74  a3 73  a2 72  a1 71  a0 70
It seems that we have only one equation but many
unknowns.



We use the restriction that the coefficients are all integers
between 0 and 6.
A series of divisions would do
MSU/CSE 260 Fall 2009
14
Example: Base conversion
6543  a4 7 4  a3 73  a2 7 2  a1 71  a0 70
6543  a4 7 4  a3 73  a2 7 2  a1 71  a0
6543  ( a4 73  a3 7 2  a2 7  a1 ) 7 
Quotient
a0
Re mainder
6543  934  7  5
934  a4 73  a3 7 2  a2 7  a1
934  ( a4 7 2  a3 7  a2 )7  a1
and so on...
MSU/CSE 260 Fall 2009
15
Integer n and base b
n  ak bk  ak 1bk 1 
n  ( ak b
k 1
n  (( ak b
 ak 1b
k 2
k 2
 ak 1b
 a3b3  a2b2  a1b1  a0b0

k 3

 a3b  a2b  a1 )b  a0
2
1
 a3b  a2 )b  a1 )b  a0
MSU/CSE 260 Fall 2009
1
16
From decimal to another base
n is to be converted
b is desired new base
ak is kth digit of number
(k goes from right to left)
The base b expansion of n is
(ak-1…a1a0)b
MSU/CSE 260 Fall 2009
qn
k 0
while (q  0)
ak  q mod b
q
q  
b
k  k 1
end while
17
Example: Decimal 50 to base 2
50 = 25*2 + 0
25 = 12*2 + 1
12 = 6*2 + 0
6 = 3*2 + 0
3 = 1*2 + 1
1 = 0*2 + 1
So, the base 2 representation is 110010
MSU/CSE 260 Fall 2009
18
Conversion from decimal to octal
What is 22910 in base 8?
229 mod 8  5 (229  8  28  5)  a0  5
 229 / 8  28
28 mod 8  4 (28  8  3  4)  a1  4
 28 / 8  3
3 mod 8  3  a2  3
So, 22910  3458
MSU/CSE 260 Fall 2009
19
Example: Decimal 229 to base 8
229 = 28*8 + 5
28 = 3*8 + 4
3 = 0*8 + 3
So, decimal 229 is 345 in base 8
MSU/CSE 260 Fall 2009
20
Bases used in Computer Science
Base 2 (Binary),


bits in computer, has two symbols {0,1}
Base 8 (Octal),


has eight symbols {0,1,2,3,4,5,6,7}
Base 16 (Hexadecimal)



has sixteen symbols
{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}.
Note that A=10, B=11, C=12, D=13, E=14, F=15.
MSU/CSE 260 Fall 2009
21
Exercise
Convert 6.96 to binary, up to 5 places









First we convert 6 to binary, which is 110
0.96 ×2 = 1.92, so the first digit after binary point is 1
0.92 ×2 = 1.84, so the 2nd digit after binary point is 1
0.84 ×2 = 1.68, so 3rd digit after binary point is 1
0.68 ×2 = 1.36, so the 4th digit after binary point is 1
0.36 ×2 = 0.72, so the 5th digit after binary point is 0
….
So, 6.96 is 110.11110…. in binary
MSU/CSE 260 Fall 2009
22
Converting Bases Related by Powers
Since 8 = 23 then every 3 binary digits makes an Octal digit.
Since 16=24 then every 4 binary digits makes a Hexadecimal
digit
Octal (base 8)
Binary (base 2)
53671 base 10
Hexadecimal (base 16)
MSU/CSE 260 Fall 2009
1 5 0
6 4 7
001101 000 11010 0111
13
1
10
7
D
1
A
7
23
Representation of integers in different bases
Hexadecimal, Octal and Binary Representation of Integers
Representation
Base
10
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
8
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
2
0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
MSU/CSE 260 Fall 2009
24
Algorithms for Integer Operation


Computers use binary numbers to perform
operations in integers.
In order to handle integer operations in binary
system first we should convert the decimal
numbers into integers and then do the
operations using binary numbers.
MSU/CSE 260 Fall 2009
25
Addition of Integers in Base 2


A procedure to perform addition is based on the usual
method for adding numbers with pencil and paper.
Example:
11
 carry bits
1110
+ 1011
=11001




(14)10
(11)10
(25)10
An overflow may happen when adding two numbers.
MSU/CSE 260 Fall 2009
26
Multiplying Integers in Base 2


Example
110

(6)10
 101

(5)10
110
+ 000
1 1 0___
= 11110

(30)10
Up to 2n bits may be needed to represent the product of two n-bit
numbers.
MSU/CSE 260 Fall 2009
27
More Examples on Base Arithmetic
Compute

Answer:


(1221)3
Compute

222 + 222 in base 4.
Answer:


(1110)4
Compute

222 + 222 in base 3.
222 + 222 in base 5.
Answer:


(444)5
MSU/CSE 260 Fall 2009
28
A MATLAB function for dec to base
function rep = decimal2base ( decimal, base )
%
% Convert input decimal number to rep in base.
% Output is an array of digits 0,1, ... base-1.
%
position = 1;
rep(1) = 0;
while decimal>0
digitValue = mod(decimal,base);
rep(position) = digitValue; % stack it in array
position = position+1;
decimal = floor(decimal/base);
end
% Flip the output array so higher order digit are at "left".
rep = fliplr(rep);
MSU/CSE 260 Fall 2009
29
results
>> decimal2base(983, 5)
ans =
1
2
4
1
3
>> decimal2base(453, 5)
ans =
3
3
0
3
>> decimal2base(6543, 7)
ans =
2
5
0
3
5
>> decimal2base(78, 2)
ans =
1
0
0
1
1
1
0
MSU/CSE 260 Fall 2009
30
Horner’s rule for computing polynomial








Consider the compiler processing the STRING
x = 983;
Compute number value as characters are read
val = 0;
val = val*10 + 9
val = val*10 + 8
val = val*10 + 3
O(N) * ops and O(N) + ops
Computing all the powers separately would
require O(N2) * ops (n+(n-1)+ … + 2+1)
MSU/CSE 260 Fall 2009
31
Factoring the polynomial p(x)






P(x) = anxn + an-1xn-1 + … + a2x2 + a1x + a0
P(x) = (anxn-1 + an-1xn-2 + … + a2x + a1) x + a0
P(x) = ((anxn-2 + an-1xn-3 + … + a2) x + a1) x + a0
P(X) = ((…((anx + an-1) x + an-2 ) x … + a1) x + a0
This shows a simple repetition of n multiplies
and n adds (Horner’s rule).
It could take n multiplies just to compute the
term anxn if a simple loop were used for this.
(If we have a fixed x, such as a base, we could
store its powers in an array and not compute
them each time.)
MSU/CSE 260 Fall 2009
32
The following example shows a hash
function using this polynomial form





The key is a string of characters – any length.
The characters are the coefficients of the
polynomial.
The value of x, or the base value, is 32, which
makes multiplication very fast via shifting left 5
bits
For speed, the logical and ‘∧’ is used instead of
‘*’ and also for the addition!
Many tests have shown this function to be fast
and uniform over the table size.
MSU/CSE 260 Fall 2009
33
Hash function effort O(n): n = #chars
int TABLESIZE = 10000; // default size
// Hash function from figure 19.2 of old Weiss text (page 611).
// This function mixes the bits of the key to produce a pseudo
// random integer between 0 and TABLESIZE-1
unsigned int Hash(const string& KEY, const int tableSize)
{
unsigned int HashValue = 0;
// compute value of polynomial P(X), where KEY[i] are the coefficients
// and X=32; multiplying by X is done by a left shift of 5 bits
// and arithmetic is "abbreviated" using bit operations.
for( int i=0; i<KEY.length(); i++ ) // use every character of key
// Horner's rule. Also, use the bitwise OR instead of + op
// for speed and overflow suppression
{ HashValue = ( HashValue << 5 ) ^ KEY[i] ^ HashValue; }
return HashValue % tableSize;
}
MSU/CSE 260 Fall 2009
34
C++ details:
http://docs.hp.com/en/B3901-90013/ch05s04.html
exp1 << exp2
Left shifts (logical shift) the bits in exp1 by exp2 positions.
exp1 >> exp2
Right shifts (logical or arithmetic shift) the bits in exp1 by exp2
positions.
exp1 & exp2
Performs a bitwise AND operation.
exp1 ^ exp2
Performs a bitwise OR operation.
exp1 | exp2
Performs a bitwise inclusive OR operation.
~exp1
Performs a bitwise negation (one's complement) operation.
MSU/CSE 260 Fall 2009
35
Program to call hash function
int main()
{
string plainText;
int digitalSignature;
cout << "\n-----+----- Crypto/Hashing Demonstration -----+-----\n";
cout << "\n====== Give TABLESIZE (between 10 and 1000000): ";
cin >> TABLESIZE;
while ( 1 )
{
cout << "\nGive plain text string = " ;
cin >> plainText;
if ( plainText == "quit") break;
digitalSignature = Hash(plainText, TABLESIZE);
cout << "\nYour digital signature is: " << digitalSignature << endl;
}
return 0;
MSU/CSE 260 Fall 2009
36
Using a polynomial hash function
-----+----- Crypto/Hashing Demonstration -----+----====== Give TABLESIZE (between 10 and 1000000): 20
Give plain text string = harrycarrie
Your digital signature is: 10
Give plain text string = spartyparty
Your digital signature is: 3
Give plain text string = sparty
Your digital signature is: 13
Give plain text string = party
Your digital signature is: 2
Give plain text string = 122345678901234567890!@#$%^&&*
Your digital signature is: 13
MSU/CSE 260 Fall 2009
37