Let x be an integer greater than or equal to 0. We let the symbol compositefunct

Question

Let x be an integer greater than or equal to 0. We let the symbol compositefunction be concatenation, 1 compositefunction 1 = 11 as strings for example. Note, every integer x greaterthanorequalto 0 can be written as x = b_k 2^k + b_k-1 2^k-1 +.... + b_12^1 + b_0 2^0 where b_i elementof {0, 1}. We say x's binary expression is the string b_k b_k-1 compositefunction b_1 b_0 procedure bitDecomp(x) if(x = 0) then return 0: if(x is odd) then return bitDecomp((x - 1)/2) compositefunction 1: if(x is even) then return bitDecomp(x/2) compositefunction 0: a) Consider the problem instance x = 101. What does the algorithm return? Explain with your own words the purpose of the algorithm

Explanation / Answer

a) in the given alorithm the algorithm is simply is a recursive algorithm which results in computation of binary
equivalent of the given integer x.
we have in the given question x=101
now lets do it according to the algorithm

bitDecomp(101)
step 1
if(x==0) false
if(x is odd) true so it will call bitDecomp(101-1/2) . 1 i.e bitDecomp(50).1

step 2
now bitDecomp(50) is called
if(50==0) false
if(50 is odd) false
if(50 is even) true so it will return bitDecomp(50/2).0.1

step3
now bitDecomp(25) is called
if(25==0) false
if(25) is odd true so it will return bitDecomp(24/2).1.0.1

step4
now bitDecomp(12 is called)
if(12==0) false
if(12 is odd) false
if(12 is even) true so it will return (12/2).0.1.0.1

step5
now bitDecomp(6) is called
if(6==0) false
if(6 is odd) false
if(6 is even) true so it will return bitDecomp(6/2).0.0.1.0.1

step 6
now bitDecomp(3) is called
if(3==0) false
if(3 is odd) true so it will return bitDecomp(2/2).1.0.0.1.0.1

step 7
now bitDecomp(1) is called
if(1==0) false
if(1 is odd) true so it will return bitDecomp(0/2).1.1.0.0.1.0.1

step 8
now nitDecomp(0) is called
if(0==0) true so 0 is returned so the final value that is returned is 0.1.1.0.0.1.0.1 which is the binary equivalent
of 101.

this is what the algorithm is doing.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.