meaning of (number) & (-number)

Question

What is the meaning of (number) & (-number)? I have searched it but was unable to find the meaning

I want to use i & (-i) in for loop like:

for (i = 0; i <= n; i += i & (-i))

Answer 1

Assuming 2's complement (or that i is unsigned), -i is equal to ~i+1.

i & (~i + 1) is a trick to extract the lowest set bit of i.

It works because what +1 actually does is to set the lowest clear bit, and clear all bits lower than that. So the only bit that is set in both i and ~i+1 is the lowest set bit from i (that is, the lowest clear bit in ~i). The bits lower than that are clear in ~i+1, and the bits higher than that are non-equal between i and ~i.

Using it in a loop seems odd unless the loop body modifies i, because i = i & (-i) is an idempotent operation: doing it twice gives the same result again.

[Edit: in a comment elsewhere you point out that the code is actually i += i & (-i). So what that does for non-zero i is to clear the lowest group of set bits of i, and set the next clear bit above that, for example 101100 -> 110000. For i with no clear bit higher than the lowest set bit (including i = 0), it sets i to 0. So if it weren't for the fact that i starts at 0, each loop would increase i by at least twice as much as the previous loop, sometimes more, until eventually it exceeds n and breaks or goes to 0 and loops forever.

It would normally be inexcusable to write code like this without a comment, but depending on the domain of the problem maybe this is an "obvious" sequence of values to loop over.]

Answer 2

I thought I'd just take a moment to show how this works. This code gives you the lowest set bit's value:

int i = 0xFFFFFFFF; //Last byte is 1111(base 2), -1(base 10)
int j = -i;         //-(-1) == 1
int k = i&j;        //   1111(2) = -1(10) 
                    // & 0001(2) =  1(10)
                    // ------------------
                    //   0001(2) = 1(10). So the lowest set bit here is the 1's bit


int i = 0x80;       //Last 2 bytes are 1000 0000(base 2), 128(base 10)
int j = -i;         //-(128) == -128
int k = i&j;        //   ...0000 0000 1000 0000(2) =  128(10) 
                    // & ...1111 1111 1000 0000(2) = -128(10)
                    // ---------------------------
                    //   1000 0000(2) = 128(10). So the lowest set bit here is the 128's bit

int i = 0xFFFFFFC0; //Last 2 bytes are 1100 0000(base 2), -64(base 10)
int j = -i;         //-(-64) == 64
int k = i&j;        //   1100 0000(2) = -64(10) 
                    // & 0100 0000(2) =  64(10)
                    // ------------------
                    //   0100 0000(2) = 64(10). So the lowest set bit here is the 64's bit

It works the same for unsigned values, the result is always the lowest set bit's value.

Given your loop:

for(i=0;i<=n;i=i&(-i))  

There are no bits set (i=0) so you're going to get back a 0 for the increment step of this operation. So this loop will go on forever unless n=0 or i is modified.