Lecture 2



Lecture 18 Integers, Divisions and Algorithms (Cont.)

Goals and Objectives:

• Understand how integers under different base representation and analyze algorithm complexity

• Understand how integers are stored in computer

Read 2.4, 2.5, p. 153-179

2. Integer Representations: (32 bits)

1. Unsigned Integer: range 0 to 232- 1

(1) Binary Representation( 0,1 in each digit)

(2) Decimal Representation( 0,1,2,...,9 in each digit)

(3) Octal Representation( 0,1,...,7 in each digit)

(4) Hexadecimal Representation( 0,1,...,9,A,...,F in each digit)

Base Change( use position value)

(1) Binary and Decimal

Base 2 to Base 10:

Ex. 0111 1011 (base 2)= 123 (base 10)

The right hand most bit has position value 1 (=20), the next left bit has position value= the previous bit position value * base (=21). Then sum the product of the digit and the corresponding position value

i.e 0111 1011 = 0*128+1*64+1*32+1*16+1*8+0*4+1*2+1*1=123

or 0111 1011 = 0*27+1*26+1*25+1*24+1*23+0*22+1*21+1*20=123

Base 10 to Base 2:

Ex. 123 = 0111 1011 (base 2)

divide 123 by the base(=2), until quotient =0. Then pick up all remainders

and start to write from the right hand most bit to the left

(2) Octal and Decimal

Base 8 to Base 10:

Ex. 173(base 8) = 123 (base 10)

use position value

173(base 8) = 1*64+7*8+3*1=123

Base 10 to Base 8:

Ex. 123 = 173(base 8)

divide 123 by the base(=8), until quotient =0. Then pick up all remainders

and start to write from the right hand most bit to the left

(3) Hexadecimal and Decimal

Base 16 to Base 10:

Ex. 7B (base 16) = 123(base 10)

use position value

7B(base 16) = 7*16+B*1=7*16+11*1=123

Base 10 to Base 16:

Ex. 123 = 7B (base 16)

divide 123 by the base(=16), until quotient =0. Then pick up all remainders

and start to write from the right hand most bit to the left

Change from Decimal to Base b Algorithm

Procedure base b expansion (given n: positive integer)

q=n

k=0

While q [pic]0

ak =q mod b

q =[pic]

k =k+1

output (ak-1 … a1 a0 )b

Example. As in the previous example, n=123, b=16

k=0

a0= 123 mod 16= 11=B

q= [pic]=7

k=1

a1=7 mod 16=7

q=7/16=0

k=1

finish the loop

Output: 123=(7B)16

(4) Binary and Octal

Base 2 to Base 8:

Ex. 0111 1011 (base 2)= 173 (base 8)

pick 3 bits as a group from the right hand most bit, append 0 if not

enough bits in the group. Then change those 3 bits in every group from

binary to decimal

i.e. 001 111 011 = 1 7 3(base 8)

Base 8 to Base 2:

Ex. 173(base 8) = 0111 1011 (base 2)

change each digit to 3 bits(using decimal to binary method)

i.e. 1 7 3 = 001 111 011

(5) Binary and Hexadecimal

Base 2 to Base 16:

Ex. 0111 1011 (base 2)= 7B (base 16)

pick 4 bits as a group from the right hand most bit, append 0 if not

enough bits in the group. Then change those 4 bits in every group from

binary to decimal

i.e. 0111 1011 = 7 B(base 16)

Base 16 to Base 2:

Ex. 7B(base 16) = 0111 1011 (base 2)

change each digit to 4 bits(using decimal to binary method)

i.e. 7 B = 0111 1011

(6) Octal and Hexadecimal

Base 8 to Base 16:

Ex. 173(base 8) = 7B(base 16)

173(base 8) = 001 111 011(base 2) = 7B(base 16)

Expand each digit into 3 bits and re-group 4 bits together from right hand side (i.e. Change base 8 to base 2 first, then change back to base 16.)

Base 16 to Base 8:

Ex.7B(base 16)= 173(base 8)

7B(base 16) = 0111 1011(base 2)= 173(base 8)

Expand each digit into 4 bits and re-group 3 bits together from right hand side (i.e. Change base 16 to base 2 first, then change back to base 8.)

Binary Arithmetic:

(1) addition of 157 and 107=264

10011101

+ 01101011

__________

1 00001000

^

|

Overflow if limited to 8 bits

Result: 00001000

(2) Subtraction of 157 and 107=50

10011101

- 01101011

__________

00110010

Ans: 00110010

Binary Addition Algorithm

Procedure add two integers (given a, b: positive integer,

Where a= (an-1 … a1 a0)2 and b= (bn-1 … b1 b0)2

c=0

for j=0 to n-1

d= [pic]

sj = aj + bj + c – 2d

c = d

sn = c

output (sn-1 … s1 s0)2

Example.

a=10011101, b=01101011

j=0

d=floor((1+1+0)/2)=1

s0=1+1+0-2=0

c=1

j=1

d=floor ((0+1+1)/2)=1

s1=(0+1+1)-2=0

c=1

j=2

d=floor((1+0+1)/2)=1

s2=(1+0+1)-2=0

c=1

j=3

d=floor((1+1+1)/2)=1

s3=1+1+1-2=1

c=1

…

Theorem. The number of bit additions in the Addition Algorithm is O(n).

(3) multiplication 157 and 107=16799

10011101

x 01101011

__________

10011101

10011101

100111010

100111010

10011101

_______________

100000110011111

Ans. 100000110011111

Binary Multiplication Algorithm

Procedure multiply two integers (given a, b: positive integer,

Where a= (an-1 … a1 a0)2 and b= (bn-1 … b1 b0)2

for j=0 to n-1

if bj =1 then cj =a shifted j places

else cj =0

p = 0

for j=0 to n-1

p=p+cj

output p

Theorem. The number bit shifts or the number of bit additions is O(n2).

Assignment #14

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download