Can't understand what this C program is doing?

Question

When I was preparing for some interview I got the following

count=0;
for(i=1;i<=n;i++)
{
    i=(i)&(i-1);    //line 4
    count++;
}
return count;
//--------

i=21,22 same count. For what other values of i we get same count?

I was not able to understand what line 4 is doing. Can anyone please help me and give me the output of the program.....

Found the above question(9) in the link http://placement.freshersworld.com/placement-papers/Mentor-Graphics/Placement-Paper-Aptitude-General-32412

`&` is a bitwise operator .. here is a example : http://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm — sukhvir, Nov 04 '13 at 06:47
Your code, as presented, will simply loop forever, resulting in overflow of `count`. On each iteration `i` will get reset from `1` to `0` and then incremented back to `1`. So, what is "i=21,22 same count" supposed to mean? That just does not make any sense. — AnT stands with Russia, Nov 04 '13 at 06:48
@AndreyT Finally somebody who makes sense! And that's not even an answer! All the answers tell what loop body does, nobody cared to look at how loop actually works. — zubergu, Nov 04 '13 at 07:14
@zubergu: I just focussed on the OP's obvious confusion over the bitwise operator, but both Owen and my answer also state that this loop won't ever terminate. I admit, mine only did after I looked over the code a second time, and edited it to reflect on that.... — Elias Van Ootegem, Nov 04 '13 at 07:18
[Counting number of bits: How does this line work ? n=n&(n-1);](https://stackoverflow.com/q/15370250/995714), [Why is "i & (i ^ (i - 1))" equivalent to "i & (-i)"](https://stackoverflow.com/q/24772669/995714) — phuclv, Jun 05 '22 at 08:48

Owen · Answer 1 · 2013-11-04T07:09:56.177

3

i & (i-1) returns 0 if i is a power of 2 or if i is 0, non zero otherwise.

On inspection, i will be set to zero, count incremented, then i will become 1 again, then 0, and so on.

I'm not sure that this loop will terminate .

edited Nov 04 '13 at 07:09

answered Nov 04 '13 at 06:47

Owen

1,726
10
15

3

A little SO tip: Instead of deleting one answer and adding a new one, just edit the existing answer instead. – Some programmer dude Nov 04 '13 at 06:49
+1: You're right, this loop can't ever terminate. I've added that to my answer aswell, hope you don't mind :) – Elias Van Ootegem Nov 04 '13 at 07:17
Since it sets `i` to the result of the and, it will clear a single bit each iteration, thus counting the set bits in `i`. – Chris Dodd Nov 04 '13 at 07:50
1

@ChrisDodd: Not quite, it counts the number of set bits in both `i` and `i -1`, given that the loop starts with `i=1`, there is but 1 bit set, and no bits in `i-1`, assigning `0` to i, then `i` is incremented (so it's back to the initial value of 1), and the whole process starts again, into infinity. you could just write `while(true && ++i) i=0;`, much to the same effect – Elias Van Ootegem Nov 04 '13 at 08:17

Elias Van Ootegem · Accepted Answer · 2013-11-04T09:05:40.990

Warning
After looking over your code a second time, I must say, it may compile just fine, but you are going to encounter a deadlock, I do think:

for (i=1;i<=n;++i)
{
    i = (i)&(i-1);
    cont++;
}

What will happen? When i is 1:

i = 1&0;//is what line 4 boils down to

So i will be 0, if the loop started, then n will be at least 1, so the loop condition still is true:

i<=n => 0 <= n ==> true

So i is incremented by 1 (i++), and the whole thing starts again. Line four, once again, evaluates to:

i = 1&0;//assigns 0 again to i

And you're back to square one. This program will never terminate, it'll simply repeat the same operation over and over and over...

Well, & is the bitwise AND operator. It When used, as in your snippet with 2 integers, it returns the bits that are "switched on" or set to 1 in both numbers. In plain English: the expression evaluates to a new set of bits, which were set in both operands. Take, for example, when i is 2:

00000010 //2
00000001 // i - 1
--------
00000000

In this case, non of the bits are set to 1 in both cases. As indeed this will be the fact for all powers of two, because the powers of 2 look like this in binary:

00000010
00000100
00001000

And a power of 2 minus 1 looks like this:

00001000//power of 2
00000111

In all other cases, there will, at least be 1 bit that is set to 1 in both cases:

00000110
00000101
--------
00000100

Easy.

For a more complete overview, and detailed explanation of bitwise operators in C, you can always refer to the wiki on bitwise operators in C

Chris Dodd · Answer 3 · 2013-11-04T17:51:42.657

1

The line

i = i & (i-1)

clears the lowest set bit of i. So a loop like

while (i) {
    i = i & (i-1);
    count++; }

counts the number of set bits in i. Note that this really only works if i has an unsigned type. If i is signed and negative, it causes undefined behavior.

The link you give is probably a misremembered question (left off the while (i)) asking about a loop like this.

The comment "i=21,22 same count" is a hint that 21(10101) and 22(10110) have the same number of set bits.

I must admit that when I read your question the first time, I actually saw the while(i) loop as the lines i=(i)&(i-1); count++; really only make sense in that context, and its such a common "trick question" idiom.

edited Nov 04 '13 at 17:51

answered Nov 04 '13 at 06:49

Chris Dodd

119,907
13
134
226

No, it doesn't clear the lowest set bit - it tests for power of 2. – Paul R Nov 04 '13 at 06:55
@PaulR: It does in fact clear the lowest set bit. If `i` was a power of two, it had only one set bit, so is now 0. Otherwise, it will have one fewer set bit. This is a common idiom for iterating through the set bits of a word, either to count them (as in this case) or to do something else. – Chris Dodd Nov 04 '13 at 07:48
1

@ChrisDodd: to say that the bitwise `&` operator clears the lowest bit, which is how the OP might read your answer, is just plain wrong: `1&3` evaluates to `1`, so it's _"clearing"_ the highest set bit. Just tell it like it is: the bitwise and returns those bits that are set in both operands. End of story. – Elias Van Ootegem Nov 04 '13 at 09:03
My bad - it actually does both - I've only ever used this idiom for testing for powers of 2. Down-vote converted to up-vote. (I'm not sure about the undefined behaviour though?) – Paul R Nov 04 '13 at 10:00
1

@ChrisDodd: Please edit your answer, to disambiguate what you actually mean when you say _"clears the lowest bit"_. It does, in this specific case (when the right operand == left operand -1), but the bitwise and doesn't _actually_ clear the lowest bit of the left operand, unless the right operand == loperand -1. The way you phrase it now might be confusing to the OP – Elias Van Ootegem Nov 04 '13 at 10:23
@EliasVanOotegem: It means exactly what it says -- the assignment `i = i & (i-1)` clears the lowest set bit of `i`. That involves an `&` but its not just an `&` -- there's also a `-` and an `=`. The question is "what does this line do?", not "what does the `&` operator do?" – Chris Dodd Nov 04 '13 at 17:36
@PaulR: If `i` is negative on a 2s complement machine, then when it gets to the most negative int value, it will subtract one and underflow, which is undefined behavior. On MOST machines and compilers it will wrap around, so will work fine, but its still undefined behavior. – Chris Dodd Nov 04 '13 at 17:43
@ChrisDodd: *undefined* or *implementation-defined* ? I would have thought the latter ? – Paul R Nov 04 '13 at 17:55

score 0 · Answer 4 · edited Nov 04 '13 at 08:20

& is a bit-wise AND operator.It computes as follows:

for eg: i=8

i & (i-1)  is (1000) AND (0111) results 0000.

if you run the program it gets into infinite loop since

i=1 and (i) & (i-1) gives 0

every time i becomes 1

so, modify the code as follows and I hope you will get the answer:

for(i=1;i<=n;i++)
{
    count=(i)&(i-1);
    printf(" i= %d  count= %d",i,count);
}

The result is as follows:

i= 1 count= 0
i= 2  count= 0
i= 3  count= 2
i= 4  count= 0
i= 5  count= 4
i= 6  count= 4
i= 7  count= 6
i= 8  count= 0
i= 9  count= 8
i= 10  count= 8
i= 11  count= 10
i= 12  count= 8
i= 13  count= 12
i= 14  count= 12
i= 15  count= 14
i= 16  count= 0
i= 17  count= 16
i= 18  count= 16
i= 19  count= 18
i= 20  count= 16
i= 21  count= 20
i= 22  count= 20
i= 23  count= 22
i= 24  count= 16
i= 25  count= 24

Can't understand what this C program is doing?

4 Answers4

Linked