IAE Academy

GATE 2018 CS Q.32: solution and answer

GATE 2018 · CSQ.32 · 2 marks · MCQ

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 is

  1. (A)

    4

  2. (B)

    5

  3. (C)

    6

  4. (D)

    40

See the question in the paper
GATE 2018 CS question 32Tap to open full size

Answer and solution

ANSWER

The value returned by fun(2^40) is 5, so the correct option is (B).

Official answer: BSource: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. First loop: i starts at n = 2^40 and is repeatedly halved by integer division while i > 1. The body runs for i = 2^40, 2^39, ..., 2^1 (40 values), incrementing j each time, so after the loop j = 40.

  2. Second loop: j starts at 40 and is repeatedly halved by integer division while j > 1, incrementing sum each time: j=40→20 (sum=1), 20→10 (sum=2), 10→5 (sum=3), 5→2 (sum=4, since 5/2=2 by integer division), 2→1 (sum=5).

  3. When j becomes 1, the condition j > 1 fails and the loop terminates with sum = 5.

  4. The function returns sum = 5, which is option (B).

KEY IDEA

Trace the two loops separately: the first loop counts how many times can be halved (integer division) before reaching 1, i.e. ; the second loop then counts how many times itself can be halved before reaching , i.e. . So the code computes .

WATCH OUT FOR

Confusing the count in the first loop: some solvers miscount the number of halvings needed to go from 2^40 down to ≤1, off by one, giving j = 39 or 41 instead of 40; others then also miscount the number of halvings of j in the second loop.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 7 C basics questions, with notes

More C basics questions