GATE CSE 2017 Set 1 | Question: 55

Question

The output of executing the following C program is _______________ .

#include<stdio.h>

int total(int v) {
    static int count = 0;
    while(v) {
        count += v&1;
        v >>= 1;
    }
    return count;
}

void main() {
    static int x=0;
    int i=5;
    for(; i>0; i--) {
        x = x + total(i);
    }
    printf("%d\n", x);
}

Comments

 count += v&1;
        v >>= 1;

 

v&1 check if the rightmost bit of v is 1.

Right shifting v by 1 ensures that each bit of v is checked if it’s 1 or not.

 

So, overall this subroutine returns the total number of 1’s in v.

---

A odd number have LSB 1 in binary

A even number have LSB 0 in binary

Right shift by x bits means we are dividing binary's decimal equivalent with 2^x

Bitwise AND with 1 gives 1 if AND WITH odd number

Bitwise AND with 1 gives 0 if AND with even number

---

https://www.youtube.com/watch?v=rPRUA3-y1GE

Answer 1

$main$

$\fbox{static x=0}$$\fbox{i=5}$

$for(;5>0;i--)$

$x=0+total(5)$

                    $\downarrow$

$\fbox{static count=0}$

$1.while(5)\{$

$count=0+101\&001$

$count=0+1$

$\fbox{static count=1}$

$v=101>>1//right\ shift$

$v=010$

$2.while(2)\{$

$count=1+010\&001$

$count=1+0$

$\fbox{static count=1}$

$v=010>>1//right\ shift$

$v=001$

$3.while(1)\{$

$count=1+001\&001$

$count=1+1$

$\fbox{static count=2}$

$v=001>>1//right\ shift$

$v=000$

$while(0)//condition\ false$

$return\ count;$

$\downarrow$

$main()$

$x=0+2$

$\fbox{static x=2}$

---

Similary do for:

$x=2+total(4)$

$\fbox{static x=5}$

$x=5+total(3)$

$\fbox{static x=10}$

$x=10+total(2)$

$\fbox{static x=16}$

$x=16+total(1)$

$\fbox{static x=23}$

$Ans: 23$

Comments

very nice answer .