shanto_bangladesh's blog

Powers of 2 using & . But how?
By shanto_bangladesh, history, 2 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wouldn't i & 0x1 do the same? It also isn't susceptible to integer overflow.

    → Reply