Category: Subjects

Decimal to Hexadecimal | Base 10 to base 16

Number System

Number System Conversions-

 

Before you go through this article, make sure that you have gone through the previous article on Basics of Number System.

 

In number system,

  • It is very important to have a good knowledge of how to convert numbers from one base to another base.
  • Here, we will learn how to convert any given number from base 10 to base 16.

 

 

Decimal to Hexadecimal Conversion-

 

A given number can be converted from base 10 to any other base using division method and multiplication method.

 

Following two cases are possible-

 

Case-01: For Numbers Carrying No Fractional Part-

 

  • Division Method is used to convert such numbers from base 10 to another base.
  • The division is performed with the required base.

 

Steps To Convert From Base 10 to Base 16-

 

  • Divide the given number (in base 10) with 16 until the result finally left is less than 16.
  • Traverse the remainders from bottom to top to get the required number in base 16.

 

Case-02: For Numbers Carrying A Fractional Part-

 

To convert such numbers from base 10 to another base, real part and fractional part are treated separately.

 

For Real Part-

 

The steps involved in converting the real part from base 10 to another base are same as above.

 

For Fractional Part-

 

  • Multiplication Method is used to convert fractional part from base 10 to another base.
  • The multiplication is performed with the required base.

 

Steps To Convert From Base 10 To Base 16-

 

  • Multiply the given fraction (in base 10) with 16.
  • Write the real part and fractional part of the result so obtained separately.
  • Multiply the fractional part with 16.
  • Write the real part and fractional part of the result so obtained separately.
  • Repeat this procedure until the fractional part remains 0.
  • If fractional part does not terminate to 0, find the result up to as many places as required.

 

Required Number in Base 16

= Series of real part of multiplication results obtained in the above steps from top to bottom

 

Also Read- Conversion to Base 10

 

PRACTICE PROBLEMS BASED ON DECIMAL TO HEXADECIMAL CONVERSION-

 

Problems-

 

Convert the following numbers from base 10 to base 16-

  1. (2020)10
  2. (2020.65625)10
  3. (172)10
  4. (172.983)10

 

Solution-

 

1. (2020)10

 

(2020)10 → (?)16

 

Using division method, we have-

 

 

From here, (2020)10 = (7E4)16

 

2. (2020.65625)10

 

(2020.65625)10 → ( ? )8

 

Here, we treat the real part and fractional part separately-

 

For Real Part-

 

  • The real part is (2020)10
  • We convert the real part from base 10 to base 16 using division method same as above.

 

So, (2020)10 = (7E4)16

 

For Fractional Part-

 

  • The fractional part is (0.65625)10
  • We convert the fractional part from base 10 to base 16 using multiplication method.

 

Using multiplication method, we have-

 

Real part Fractional Part
0.65625 x 16 10 = A 0.5
0.5 x 16 8 0.0

 

Explanation

 

Step-01:

 

  • Multiply 0.65625 with 16. Result = 10.5.
  • Write 10 (= A in hexadecimal) in real part and 0.5 in fractional part.

 

Step-02:

 

  • Multiply 0.5 with 16. Result = 8.0.
  • Write 8 in real part and 0.0 in fractional part.

 

Since fractional part becomes 0, so we stop.

 

  • The fractional part terminates to 0 after 2 iterations.
  • Traverse the real part column from top to bottom to obtain the required number in base 16.

 

From here, (0.65625)10 = (0.A8)8

 

Combining the result of real and fractional parts, we have-

(2020.65625)10 = (7E4.A8)16

 

3. (172)10

 

(172)10 → ( ? )16

 

Using division method, we have-

 

 

From here, (172)10 = (AC)16

 

4. (172.983)10

 

(172.983)10 → ( ? )16

 

Here, we treat the real part and fractional part separately-

 

For Real Part-

 

  • The real part is (172)10
  • We convert the real part from base 10 to base 16 using division method same as above.

 

So, (172)10 = (AC)16

 

For Fractional Part-

 

  • The fractional part is (0.983)10
  • We convert the fractional part from base 10 to base 16 using multiplication method.

 

Using multiplication method, we have-

 

Real part Fractional Part
0.983 x 16 15 = F 0.728
0.728 x 16 11 = B 0.648
0.648 x 16 10 = A 0.368
0.368 x 16 5 0.888

 

  • The fractional part does not terminates to 0 after several iterations.
  • So, let us find the value up to 4 decimal places.
  • Traverse the real part column from top to bottom to obtain the required number in base 16.

 

From here, (0.983)10 = (0.FBA5)8

 

Combining the result of real and fractional parts, we have-

(172.983)10 = (AC.FBA5)16

 

Also Read- Decimal to Octal Conversion

 

To gain better understanding about Decimal to Hexadecimal Conversion,

Watch this Video Lecture

 

Next Article- Converting Any Base To Any Base

 

Get more notes and other study material of Number System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Decimal to Octal Conversion | Base 10 to Base 8

Number System

Number System Conversions-

 

Before you go through this article, make sure that you have gone through the previous article on Basics of Number System.

 

In number system,

  • It is very important to have a good knowledge of how to convert numbers from one base to another base.
  • Here, we will learn how to convert any given number from base 10 to base 8.

 

 

Decimal to Octal Conversion-

 

A given number can be converted from base 10 to any other base using division method and multiplication method.

 

Following two cases are possible-

 

Case-01: For Numbers Carrying No Fractional Part-

 

  • Division Method is used to convert such numbers from base 10 to another base.
  • The division is performed with the required base.

 

Steps To Convert From Base 10 to Base 8-

 

  • Divide the given number (in base 10) with 8 until the result finally left is less than 8.
  • Traverse the remainders from bottom to top to get the required number in base 8.

 

Case-02: For Numbers Carrying A Fractional Part-

 

To convert such numbers from base 10 to another base, real part and fractional part are treated separately.

 

For Real Part-

 

The steps involved in converting the real part from base 10 to another base are same as above.

 

For Fractional Part-

 

  • Multiplication Method is used to convert fractional part from base 10 to another base.
  • The multiplication is performed with the required base.

 

Steps To Convert From Base 10 To Base 8-

 

  • Multiply the given fraction (in base 10) with 8.
  • Write the real part and fractional part of the result so obtained separately.
  • Multiply the fractional part with 8.
  • Write the real part and fractional part of the result so obtained separately.
  • Repeat this procedure until the fractional part remains 0.
  • If fractional part does not terminate to 0, find the result up to as many places as required.

 

Required Number in Base 8

= Series of real part of multiplication results obtained in the above steps from top to bottom

 

Also Read- Conversion to Base 10

 

PRACTICE PROBLEMS BASED ON DECIMAL TO OCTAL CONVERSION-

 

Problems-

 

Convert the following numbers from base 10 to base 8-

  1. (1032)10
  2. (1032.6875)10
  3. (172)10
  4. (172.878)10

 

Solution-

 

1. (1032)10

 

(1032)10 → (?)8

 

Using division method, we have-

 

 

From here, (1032)10 = (2010)8

 

2. (1032.6875)10

 

(1032.6875)10 → ( ? )8

 

Here, we treat the real part and fractional part separately-

 

For Real Part-

 

  • The real part is (1032)10
  • We convert the real part from base 10 to base 8 using division method same as above.

 

So, (1032)10 = (2010)8

 

For Fractional Part-

 

  • The fractional part is (0.6875)10
  • We convert the fractional part from base 10 to base 8 using multiplication method.

 

Using multiplication method, we have-

 

Real part Fractional Part
0.6875 x 8 5 0.5
0.5 x 8 4 0.0

 

Explanation

 

Step-01:

 

  • Multiply 0.6875 with 8. Result = 5.5.
  • Write 5 in real part and 0.5 in fractional part.

 

Step-02:

 

  • Multiply 0.5 with 8. Result = 4.0.
  • Write 4 in real part and 0.0 in fractional part.

 

Since fractional part becomes 0, so we stop.

 

  • The fractional part terminates to 0 after 2 iterations.
  • Traverse the real part column from top to bottom to obtain the required number in base 8.

 

From here, (0.6875)10 = (0.54)8

 

Combining the result of real and fractional parts, we have-

(1032.6875)10 = (2010.54)8

 

3. (172)10

 

(172)10 → ( ? )8

 

Using division method, we have-

 

 

From here, (172)10 = (254)8

 

4. (172.878)10

 

(172.878)10 → ( ? )8

 

Here, we treat the real part and fractional part separately-

 

For Real Part-

 

  • The real part is (172)10
  • We convert the real part from base 10 to base 8 using division method same as above.

 

So, (172)10 = (254)8

 

For Fractional Part-

 

  • The fractional part is (0.878)10
  • We convert the fractional part from base 10 to base 8 using multiplication method.

 

Using multiplication method, we have-

 

Real part Fractional Part
0.878 x 8 7 0.024
0.024 x 8 0 0.192
0.192 x 8 1 0.536
0.536 x 8 4 0.288

 

  • The fractional part does not terminates to 0 after several iterations.
  • So, let us find the value up to 4 decimal places.
  • Traverse the real part column from top to bottom to obtain the required number in base 8.

 

From here, (0.878)10 = (0.7014)8

 

Combining the result of real and fractional parts, we have-

(172.878)10 = (254.7014)8

 

Also Read- Decimal to Binary Conversion

 

To gain better understanding about Decimal to Octal Conversion,

Watch this Video Lecture

 

Next Article- Decimal to Hexadecimal Conversion

 

Get more notes and other study material of Number System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Decimal to Binary Conversion | Base 10 to base 2

Number System

Number System Conversions-

 

Before you go through this article, make sure that you have gone through the previous article on Basics of Number System.

 

In number system,

  • It is very important to have a good knowledge of how to convert numbers from one base to another base.
  • Here, we will learn how to convert any given number from base 10 to base 2.

 

 

Decimal to Binary Conversion-

 

A given number can be converted from base 10 to any other base using division method and multiplication method.

 

Learn how much goods and services should cost from painting a car or reupholstering a car windshield

to hiring wedding planner or a cook at The Pricer.

 

Following two cases are possible-

 

Case-01: For Numbers Carrying No Fractional Part-

 

  • Division Method is used to convert such numbers from base 10 to another base.
  • The division is performed with the required base.

 

Steps To Convert From Base 10 to Base 2-

 

  • Divide the given number (in base 10) with 2 until the result finally left is less than 2.
  • Traverse the remainders from bottom to top to get the required number in base 2.

 

Case-02: For Numbers Carrying A Fractional Part-

 

To convert such numbers from base 10 to another base, real part and fractional part are treated separately.

 

For Real Part-

 

The steps involved in converting the real part from base 10 to another base are same as above.

 

For Fractional Part-

 

  • Multiplication Method is used to convert fractional part from base 10 to another base.
  • The multiplication is performed with the required base.

 

Steps To Convert From Base 10 To Base 2-

 

  • Multiply the given fraction (in base 10) with 2.
  • Write the real part and fractional part of the result so obtained separately.
  • Multiply the fractional part with 2.
  • Write the real part and fractional part of the result so obtained separately.
  • Repeat this procedure until the fractional part remains 0.
  • If fractional part does not terminate to 0, find the result up to as many places as required.

 

Required Number in Base 2

= Series of real part of multiplication results obtained in the above steps from top to bottom

 

Also Read- Conversion to Base 10

 

PRACTICE PROBLEMS BASED ON DECIMAL TO BINARY CONVERSION-

 

Problems-

 

Convert the following numbers from base 10 to base 2-

  1. (18)10
  2. (18.625)10
  3. (172)10
  4. (172.878)10

 

Solution-

 

1. (18)10

 

(18)10 → ( ? )2

 

Using division method, we have-

 

 

From here, (18)10 = (10010)2

 

2. (18.625)10

 

(18.625)10 → ( ? )2

 

Here, we treat the real part and fractional part separately-

 

For Real Part-

 

  • The real part is (18)10
  • We convert the real part from base 10 to base 2 using division method same as above.

 

So, (18)10 = (10010)2

 

For Fractional Part-

 

  • The fractional part is (0.625)10
  • We convert the fractional part from base 10 to base 2 using multiplication method.

 

Using multiplication method, we have-

 

Real part Fractional Part
0.625 x 2 1 0.25
0.25 x 2 0 0.50
0.50 x 2 1 0

 

Explanation

 

Step-01:

 

  • Multiply 0.625 with 2. Result = 1.25.
  • Write 1 in real part and 0.25 in fractional part.

 

Step-02:

 

  • Multiply 0.25 with 2. Result = 0.50.
  • Write 0 in real part and 0.50 in fractional part.

 

Step-03:

 

  • Multiply 0.50 with 2. Result = 1.0.
  • Write 1 in real part and 0.0 in fractional part.

 

Since fractional part becomes 0, so we stop.

 

  • The fractional part terminates to 0 after 3 iterations.
  • Traverse the real part column from top to bottom to obtain the required number in base 2.

 

From here, (0.625)10 = (0.101)2

 

Combining the results of real part and fractional part, we have-

(18.625)10 = (10010.101)2

 

3. (172)10

 

(172)10 → ( ? )2

 

Using division method, we have-

 

 

From here, (172)10 = (10101100)2

 

4. (172.878)10

 

(172.878)10 → ( ? )2

 

Here, we treat the real part and fractional part separately-

 

For Real Part-

 

  • The real part is (172)10
  • We convert the real part from base 10 to base 2 using division method same as above.

 

So, (172)10 = (10101100)2

 

For Fractional Part-

 

  • The fractional part is (0.878)10
  • We convert the fractional part from base 10 to base 2 using multiplication method.

 

Using multiplication method, we have-

 

Real part Fractional Part
0.878 x 2 1 0.756
0.756 x 2 1 0.512
0.512 x 2 1 0.024
0.024 x 2 0 0.048

 

  • The fractional part does not terminates to 0 after several iterations.
  • So, let us find the value up to 4 decimal places.
  • Traverse the real part column from top to bottom to obtain the required number in base 2.

 

From here, (0.878)10 = (0.1110)2

 

Combining the results of real part and fractional part, we have-

(172.878)10 = (10101100.1110)2

 

To gain better understanding about Decimal to Binary Conversion,

Watch this Video Lecture

 

Next Article- Decimal to Octal Conversion

 

Get more notes and other study material of Number System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Miscellaneous Problems in Compiler Design

Compiler Design

Three Address Code | DAGs | Basic Blocks & Flow Graphs-

 

Before you go through this article, make sure that you have gone through the previous articles on-

 

In this article, we will solve Miscellaneous Problems based on these Concepts.

 

PRACTICE PROBLEMS BASED ON ABOVE CONCEPTS-

 

Problem-01:

 

Generate three address code for the following code-

 

c = 0

do

{

if (a < b) then

x++;

else

x–;

c++;

} while (c < 5)

 

Solution-

 

Three address code for the given code is-

  1. c = 0
  2. if (a < b) goto (4)
  3. goto (7)
  4. T1 = x + 1
  5. x = T1
  6. goto (9)
  7. T2 = x – 1
  8. x = T2
  9. T3 = c + 1
  10. c = T3
  11. if (c < 5) goto (2)

 

Problem-02:

 

Generate three address code for the following code-

 

while (A < C and B > D) do

if A = 1 then C = C + 1

else

while A <= D

do A = A + B

 

Solution-

 

Three address code for the given code is-

  1. if (A < C) goto (3)
  2. goto (15)
  3. if (B > D) goto (5)
  4. goto (15)
  5. if (A = 1) goto (7)
  6. goto (10)
  7. T1 = c + 1
  8. c = T1
  9. goto (1)
  10. if (A <= D) goto (12)
  11. goto (1)
  12. T2 = A + B
  13. A = T2
  14. goto (10)

 

Problem-03:

 

Generate three address code for the following code-

 

switch (ch)

{

case 1 : c = a + b;

break;

case 2 : c = a – b;

break;

}

 

Solution-

 

Three address code for the given code is-

 

if ch = 1 goto L1

if ch = 2 goto L2

L1:

T1 = a + b

c = T1

goto Last

L2:

T1 = a – b

c = T2

goto Last

Last:

 

Problem-04:

 

Construct a DAG for the following three address code-

  1. a = b + c
  2. t1 = a x a
  3. b = t1 + a
  4. c = t1 x b
  5. t2 = c + b
  6. a = t2 + t2

 

Solution-

 

Directed acyclic graph for the given three address code is-

 

 

Problem-05:

 

Consider the following code-

 

prod = 0 ;

i = 1 ;

do

{

prod = prod + a[ i ] x b[ i ] ;

i = i + 1 ;

} while (i <= 10) ;

 

  1. Compute the three address code.
  2. Compute the basic blocks and draw the flow graph.

 

Solution-

 

Part-01:

 

Three address code for the given code is-

 

prod = 0

i = 1

T1 = 4 x i

T2 = a[T1]

T3 = 4 x i

T4 = b[T3]

T5 = T2 x T4

T6 = T5 + prod

prod = T6

T7 = i + 1

i = T7

if (i <= 10) goto (3)

 

Part-02:

 

Step-01:

 

We identify the leader statements as-

  • prod = 0 is a leader because first statement is a leader.
  • T1 = 4 x i is a leader because target of conditional or unconditional goto is a leader.

 

Step-02:

 

The above generated three address code can be partitioned into 2 basic blocks as-

 

 

Step-03:

 

The flow graph is-

 

 

To gain better understanding about these Miscellaneous Problems,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

Next Article- Code Optimization

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Relation between Left Recursion & Left Factoring

Compiler Design

Relationship Between Left Recursion, Left Factoring & Ambiguity-

 

There is no relationship between Left Recursion, Left Factoring and Ambiguity of Grammar.

 

  • All the three concepts are independent and has nothing to do with each other.
  • The presence or absence of left recursion does not impact left factoring and ambiguity anyhow.
  • The presence or absence of left factoring does not impact left recursion and ambiguity anyhow.
  • The presence or absence of ambiguity does not impact left recursion and left factoring anyhow.

 

The following examples support this fact-

 

Example-01: Ambiguous Grammar With Left Factoring-

 

Consider the following grammar-

S → aS / a / ∈

 

Clearly, this grammar has left factoring.

Now, let us draw parse trees for the string w = a-

 

 

Clearly,

  • Two different parse trees exist for the string w = a.
  • Therefore, the grammar is ambiguous.

 

Example-02: Unambiguous Grammar With Left Factoring-

 

Consider the following grammar-

S → aA / aB

A → a

B → b

 

Clearly, this grammar has left factoring.

The language generated by this grammar consists of only two strings L(G) = { aa , ab}.

Now, let us draw parse trees for these strings-

 

 

Clearly,

  • A unique parse tree exists for both the strings.
  • Therefore, the grammar is unambiguous.

 

Example-03: Ambiguous Grammar With Left Recursion-

 

Consider the following grammar-

S → SS / ∈

 

Clearly, this grammar has left recursion.

Now, let us draw parse trees for the string w = ∈-

 

 

Clearly,

  • Infinite parse trees exist for the string w = ∈.
  • Therefore, the grammar is ambiguous.

 

Example-04: Unambiguous Grammar With Left Recursion-

 

Consider the following grammar-

S → Sa / ∈

 

Clearly, this grammar has left recursion.

A unique parse tree exists for all the strings that can be generated from the grammar.

Therefore, the grammar is unambiguous.

 

Example-05: Ambiguous Grammar Without Left Recursion & Without Left Factoring-

 

Consider the following grammar-

S → aA / Ba

A → a

B → a

 

Clearly, this grammar has neither left recursion nor left factoring.

Now, let us draw parse trees for the string w = aa-

 

 

Clearly,

  • Two different parse trees exist for the string w = aa.
  • Therefore, the grammar is ambiguous.

 

Example-06: Unambiguous Grammar With Both Left Recursion & Left Factoring-

 

Consider the following grammar-

S → Sa / ɛ / bB / bD

B → b

D → d

 

Clearly, this grammar has both left recursion and left factoring.

A unique parse tree exists for all the strings that can be generated from the grammar.

Therefore, the grammar is unambiguous.

 

To gain better understanding about relationship between left recursion, left factoring and ambiguity-

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Calculating First and Follow

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.