7.3k 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);
}

edited | 7.3k 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?
+2
+= is an compound operator. Has lesser precedence than &.

// 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 (57.2k 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

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?

+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$
+1
@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 &" . :)

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.8k 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

by Junior (529 points)
0

@ushamya excellent explanation

0
Best explanation

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.6k points)
edited

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

by Active (4.4k points)