By shanto_bangladesh, history, 4 months ago,

After solving this problem, I looked to some of other's code. In several codes, I found something like this (not exactly this, it's a simplified version of that):

int n = 10;
for(int i = 1; i<=n; i+=i& - i;)
{
cout << i << " ";
}



Output: 1 2 4 8

I also tried for different values of n and the program outputs powers of 2 less than or equal to n.

But how is it working? What's exactly meant by i+=i&-i ?

Thanks for your patience and insight.

• 0

 » 4 months ago, # | ← Rev. 3 →   +1 i & (-i) is a bit trick for computing the least significant bit of i. That said, if we are only concerned with powers of 2, i & (-i) is redundant because i & (-i) = i (powers of 2 has only 1 bit set).If you are wondering why i & (-i) computes the least significant bit, you should learn about how two's complement works.
•  » » 4 months ago, # ^ |   0 Wouldn't i & 0x1 do the same? It also isn't susceptible to integer overflow.
•  » » » 4 months ago, # ^ |   0 No that just computes the value of the 0th bit. And how is i & (-i) susceptible to integer overflow?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Oh, I see now that i & (-i) gets the least significant non-zero bit.As for the overflow, consider the case i == INT_MIN.
•  » » » » » 4 months ago, # ^ |   +5 Which I guess is irrelevant when i cannot be INT_MIN