GATE CSE 2018 | Question: 32

Question

Consider the following C code. Assume that unsigned long int type length is $64$ bits.

unsigned long int fun(unsigned long int n) {
        unsigned long int i, j=0, sum = 0;
        for( i=n; i>1; i=i/2) j++;
        for( ; j>1; j=j/2) sum++;
        return sum;
}

The value returned when we call fun with the input $2^{40}$ is:

• A. $4$
• B. $5$
• C. $6$
• D. $40$

Comments

short and long should provide different lengths of integers. short is no longer than int, int is no longer than long. Their sizes are machine-dependent.

---

I too found the answer as 5 but on my machine it gives 2 for some reason.

---

because length of int may varies with different machines

Answer 1

unsigned long int fun(unsigned long int n) {
        unsigned long int i, j=0, sum = 0;
        for( i=n; i>1; i=i/2) j++;
        for( ; j>1; j=j/2) sum++;
        return sum;
}

First for loop will make $j = 40$

Next for loop will divide $j$ value (which is $40$ now) by $2$ each time until $j \leq1.$

j loop starts:
j = 40 and sum =1,
j = 20 and sum=2,
j = 10 and sum=3,
j = 5  and sum=4,
j = 2  and sum=5,
j=1 break

So, Sum$=5$

Correct Answer: $B$

Comments

Actually, j will become 41 after the first loop but it won’t affect the answer

#include <stdio.h>

unsigned long int fun(unsigned long int n)

{

unsigned long int i, j=0, sum = 0;
for( i=n; i>1; i=i/2) j++;
int k=j;
for( ; j>1; j=j/2) sum++;
return k;

}

int main()

{

    unsigned long int i=2;
    for(int k=0 ; k<40 ; k++,i=i*2);
    int sum=fun(i);
    printf("%d",sum);

    return 0;

}

Here k in fun() stores the value of j after the first loop and I have returned its value which is 41.

---

yes just simply apply log base 2 to j you will get the answer

---

for( i=n; i>1; i=i/2) 
    j++;

iteration	1	2	3	4	...	...	...	k	k+1
i	$\frac{n}{2^{0}}$	$\frac{n}{2^{1}}$	$\frac{n}{2^{2}}$	$\frac{n}{2^{3}}$	...	...	...	$\frac{n}{2^{k-1}}$	$\frac{n}{2^{k}}$

 

Here, I assumed that loop runs for k time. (j value)

$\frac{n}{2^{k}}$ = 1

n = ${2^{k}}$

${2^{40}}$ = ${2^{k}}$       (given n =  ${2^{40}}$)

k = 40    (j value will be 40 only.)

below program also proves this

 

Answer 2

unsigned integer is 64 bits long. hmmmm $2^{40}$ won't cause overflow concerns.

 for( i=n; i>1; i=i/2) j++;

This loop will run for k iteration( which pass test condition), what this k is?

$\frac{n}{2^k}=1$ gives $k=log_2n$.

So, for n=$2^{40}$ times, my k=40 and value of j will be 40(j will be incremented by 1 "k times" ).

 for( ; j>1; j=j/2) sum++;

till $\frac{j}{2^r}>1$ this loop will continue to run and $r$ is the number of iterations.

this will run for $\lfloor log_240 \rfloor=5$ times.

$40->20->10->5->2$ for these values of j loop will run

hence sum=5.

Answer (B)

Comments

Second j loop will also run log times so log40 should give us  6 here shouldn't the answer be 6 here but as j is greater  than one here therefore 5 should be the answer  here

---

Time complexity of this algorithm is $\log_{2}$n + $\log_{2}$​(​​​​​​​$\log_{2}$​​​​​​​n) = ​​​​​​​$\log_{2}$​​​​​​​n

@Ayush Upadhyaya sir, correct????

Answer 3

ans would be 5.
explaination - 1st notice - the two for loops are separate that is 2nd loop in not inner loop of 1st loop.
now in the 1st loop--
  j = 0 | i = 2^40
  j = 1 | i = 2^39
  j = 2 | i = 2^38
.... and so on until
  j = 39 | i = 2^1

  j = 40 | i = 2^0
at the end  of 1st for loop j = 40, so mathematically the for loop is finding  floor of (log2(n))

now in 2nd for loop, similarly it is finding floor of (log2(j)) that is floor( log2(40))  =  5

Answer 4

Since 2^40  is the input, so first loop will make j = 40.
Next for loop will divide j value (which is 40) by 2, each time until j>1.
j loop starts:
j=40 & sum=1
j=20 & sum=2
j=10 & sum=3
j=5 & sum=4
j=2 & sum=5
j=1 & break
So, sum = 5.