Redirected
retagged by
15,860 views
33 votes
33 votes

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:

  1. $4$
  2. $5$
  3. $6$
  4. $40$
retagged by

5 Answers

Best answer
47 votes
47 votes
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$

edited by
21 votes
21 votes

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)

1 votes
1 votes
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
1 votes
1 votes
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.
Answer:

Related questions

42 votes
42 votes
9 answers
2
23 votes
23 votes
5 answers
3