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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- marketing management pdf lecture notes
- strategic management lecture notes pdf
- strategic management lecture notes
- philosophy 101 lecture notes
- philosophy lecture notes
- philosophy of education lecture notes
- financial management lecture notes
- financial management lecture notes pdf
- business management lecture notes
- introduction to philosophy lecture notes
- business management lecture notes pdf
- introduction to management lecture notes