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

HINT: total(v) returns count of 1's in binary form of v.

---

As the priority of & is less than +, so v must added to v first then & will be compute.d.

Am I right?

---

@Ekta07_GATE  

+= is an compound operator. Has lesser precedence than &.

---

 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

---

AM I THE ONLY ONE WHO THINKS THE ANSWER SHOULD BE 7??

 

I RAN IT THROUGH CHAT GPT AND IT ALSO GAVE 7

---

After Executing this code i am getting errors:

main.c:4:22: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘+’ token
    4 |     static int count + = v & 1;
      |                      ^
main.c:4:24: error: expected expression before ‘=’ token
    4 |     static int count + = v & 1;
      |                        ^
main.c:5:9: error: expected expression before ‘=’ token
    5 |     v>> = 1;
      |         ^
main.c:7:12: error: ‘count’ undeclared (first use in this function)
    7 |     return count;

so is this question right can someone explain me?

---

Ignore such errors in these questions..

---

@harhith Remove these unnecessary spaces between operators

Answer 1

// inside total()

while(v) {
        count += v&1;   \\ check the lowest bit of v
        v >>= 1;        \\ or v = v >> 1 : right shift the bit pattern of v
}

This piece of code will count the no of set bits in $v$. 

---

In the main function, i values goes from $5$ to $1$, So there will be $5$ calls to total().

Each call to total(i) counts the no of set bits in i. But the count is a static variable,

So, total(i) = Total no of set bits in all $i \leq 5$. 

---

$\begin{align*} & \text{x} = \sum_{i=1}^{5}\left [ \text{ total}\left ( i \right ) \right ] = \color{blue}{2+3+5+6+7} = \color{red}{\bf 23}\\ \end{align*}$

Comments

Count +=v&1 means count = count +(v&1) which is not equal to
count = count +v&1

---

@dd really appreciate the effort for this. 

---

note for everyone, it's not plus operator + only, bcoz then it will have more priority. rather it is assignment operator +=, which later becomes + and therefore it has lower priority.

Answer 2

Answer: 23

 

Comments

the precedance of bitwise and operator is lower than airthematic + then why he firstly did bitwise and operation while  counting the count?

@Hira Thakur sir can you please clarify it 

---

@Ray Tomlinson 

count += v&1; is 'assigment addition' hence less precedence then 'bitwise and',

precedence of assigment operators is less then bitwise operators

So,first bitwise and with 1 then addition assigment of count.

---

superb

Answer 3

Ans:23

total function count no. of 1's in input,but also remember previous inputs.

5--0101

4--0100

3--0011

2--0010

1-0000

TOTAL(5)-->COUNT=2

TOTAL(4)-->2+1=3,COUNT=3

TOTAL(3)-->3+2=5,COUNT=5

TOTAL(2)-->5+1=6,COUNT=6

TOTAL(1)-->6+1=7,COUNT=7

in the main it add all the values of outer loop--->2+3+5+6+7=23

Comments

Tree/Stack will be more helful in solving such questions. 23 (Y)

---

stack will be helpfull whwn there is recursion.But there is no recursion

Answer 4

The code with the full explanation is given below.

int total(int v)
{
  static int count=0; /* initialized ONLY ONCE because of the 'static' keyword */ 
                      /* it can be never be initialized again. */
                      /* So the value of count will be cumulative. */
  while(v)
  {
      count += v&1; /* v&1 returns the Least Significant Bit (LSB) */
                    /* of the binary representation of v.*/
                    /* So v&1 has the value either 0 or 1 */
      
      v >>=1;   /* v is shifted to right meaning that v = v/2 */
  }
  /* So the value of count will be the number of 1's */ 
  /* in the binary representation of v*/
  return count;
}

/*So the value of total(5)=2 because 5 is 101 in binary which has two 1's. */
/*Similarly the value of total(4)=1 because 4 is 100 in binary which one 1. */
/*But calling total(5) and total(4) one after another, total(4)=2+1=3 because */
/*the count variable in the function is cumulative.  */

void main()
{
    static int x=0;
    int i=5;
    for(; i>0; i--)
    {
        x = x +total(i); /* x = total(5)+total(4)+total(3)+total(2)+total(1) */
                         /* x = 2 + 3 + 5 + 6 + 7 */
                         /* x = 23  */
    }
    printf("%d\n", x);  /*It will give the output as 23.*/
}

 

Answer 5

$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 .

Answer 6

 

i	Binary	# of 1s	total(i) returns
5	101	2	2
4	100	1	3
3	011	2	5
2	010	1	6
1	001	1	7

 

Explanation:

total(i) counts bits in i and adds to a static counter.

 Each call returns the cumulative bit count so far.
 

x = 2 + 3 + 5 + 6 + 7 = 23