GATE CS 2018 Q.42 (CS Q.32): Functions, Recursion, Scope and Storage Classes

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

Official answer and solution

Official answer: B
From: Official GATE 2018 answer key

Solution

Determine the number of loop iterations as successive base-2 logarithms of the input.

Analyze the first loop:

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

With $n = 2^{40}$ , $i$ starts at $2^{40}$ and halves each iteration until $i = 1$ .
The sequence of values of $i$ before halting is $2^{40}, 2^{39}, \dots, 2^1$ , executing exactly 40 iterations. Thus, $j = 40$ .

Analyze the second loop:

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

Trace starting with $j = 40$ and $\text{sum} = 0$ :

Iteration 1: $j = 40 > 1 \implies \text{sum} = 1$ , $j = 40/2 = 20$
Iteration 2: $j = 20 > 1 \implies \text{sum} = 2$ , $j = 20/2 = 10$
Iteration 3: $j = 10 > 1 \implies \text{sum} = 3$ , $j = 10/2 = 5$
Iteration 4: $j = 5 > 1 \implies \text{sum} = 4$ , $j = 5/2 = 2$
Iteration 5: $j = 2 > 1 \implies \text{sum} = 5$ , $j = 2/2 = 1$
At $j = 1$ , condition $j > 1$ fails and the loop halts.

The function returns $\text{sum} = 5$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 42 of 65, printed as CS Q.32
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source