The Gateway to Computer Science Excellence
+35 votes
6.7k views

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 by Veteran (117k points)
edited by | 6.7k views
0
HINT: total(v) returns count of 1's in binary form of v.
0
As the priority of & is less than +, so v must added to v first then & will be compute.d.

Am I right?
+1

@  

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

4 Answers

+42 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*}$

by Veteran (57k points)
edited by
0

in first call from main() to   total(5)  ...

in total(5)  v is 5    ,count is 0  , , while v is not 0  : v&1 (101 & 001)gives 001 i.e 1 .. thn what  v >>=1 mean??? 

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

+1

@Debashish sir. I am Not able to understand last part. 

this one . :(

+3

value of each total() call is returned by a "count" variable. And the blue values are the count values for each total() call ( $5$ times in this case ). "count" is static in nature, i.e. value of "count" gets accumulated when no of total() call is more than $1$

+1
Got it. thank you. :)
0
Can we have use more than 4-bits to represent i ?
0
@Debashish

Sir would the answer be same if x were not static?
0
Answer 23 is right.

total(5) = (5+2+1)=8

total(4) = (4+2+1) = 7

total(3) = (3+1) = 4

total(2) = (2+1) = 3

total(1) =    (1)  = 1

i.e. = (8+7+4+3+1) = 23
0

what is the meaning of line:   

 count += v&1;
0

@EnggPk106

count = count + vBitwise-AND

0
Why total() is returning the value with addition of previous total() value as well?

Everytime we will call total(), count should not be set to 0 again?

Someone Please clarify :(
+1

@sarika, Because count is a static variable so it will retain its value between different function calls. 

0
Got it ! Thanks a lot @Soumya29
0
thanks...
0
After the call total(5), count becomes 8. Right? Then, since count is static, total(4) should return 15, isn't it? (for v:4::count = 8 + 4, v:2:: count = 12 + 2, v:1::count = 14 + 1 and finally count returns 15). Please explain. And, how does bitwise and work? a&1 = a for any integer 'a', am i correct?
+2
@Aravindh, $a \And1$ will give 1 if $LSB$ of  $a$ is 1 else 0.
Suppose $a = 5 = 101(in \ binary)$
When you do $ 5 \And 1 = 101\And1=1 $
0
@soumya29 I get it now. Thanks. Earlier I was mistakenly assuming that 1 = 11111.... in binary (obviously I was wrong). That's where the confusion was stemming from. I understand the solution now.
0
@Soumya From where you learn this concept a&1 will give if LSB of a is 1 else 0
0
count=count+v&1;

here arithmetic operation will not get priority over bitwise(&)?
+1
@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 &" . :)
+12 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

by Active (4.7k points)
0
Tree/Stack will be more helful in solving such questions. 23 (Y)
+4
stack will be helpfull whwn there is recursion.But there is no recursion
+12 votes

Answer: 23

 

by Junior (513 points)
0

@ushamya excellent explanation 

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

 

by Active (3.2k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,479 answers
195,422 comments
100,558 users