in Programming in C edited by
22,166 views
68 votes
68 votes

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);
}
in Programming in C edited by
by
22.2k views

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

2
2
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
2
2

5 Answers

61 votes
61 votes
Best answer
// 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*}$

edited by
by

4 Comments

@Soumya From where you learn this concept a&1 will give if LSB of a is 1 else 0
0
0
count=count+v&1;

here arithmetic operation will not get priority over bitwise(&)?
0
0
@Anurag, It's quite easy to figure out but it got fixed in my mind when I used it once for GO classroom assignment. :)

@Punit, It's a compound operator, which has a lower priority as compared to "bitwise &" . :)
3
3
34 votes
34 votes

Answer: 23

 

4 Comments

@ushamya excellent explanation 

1
1
Best explanation
1
1
Thanks alot
0
0

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 

0
0
16 votes
16 votes

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

2 Comments

Tree/Stack will be more helful in solving such questions. 23 (Y)
1
1
stack will be helpfull whwn there is recursion.But there is no recursion
4
4
8 votes
8 votes

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.*/
}

 

edited by
Answer:

Related questions