What does i+=(i&-i) do? Is it portable?

Question

Let i be a signed integer type. Consider

i += (i&-i);
i -= (i&-i);

where initially i>0.

1. What do these do? Is there an equivalent code using arithmetic only?
2. Is this dependent on a specific bit representation of negative integers?

Source: setter's code of an online coding puzzle (w/o any explanation/comments).

Answer 1

The expression i & -i is based on Two's Complement being used to represent negative integers. Simply put, it returns a value k where each bit except the least significant non-zero bit of i is set to 0, but that particular bit keeps its own value. (i.e. 1)

As long as the expression you provided executes in a system where Two's Complement is being used to represent negative integers, it would be portable. So, the answer to your second question would be that the expression is dependent on the representation of negative integers.

To answer your first question, since arithmetic expressions are dependent on the data types and their representations, I do not think that there is a solely arithmetic expression that would be equivalent to the expression i & -i. In essence, the code below would be equivalent in functionality to that expression. (assuming that i is of type int) Notice, though, that I had to make use of a loop to produce the same functionality, and not just arithmetics.

int tmp = 0, k = 0;
while(tmp < 32)
{
    if(i & (1 << tmp))
    {
        k = i & (1 << tmp);
        break;
    }
    tmp++;
}
i += k;

Answer 2

On a Two's Complement architecture, with 4 bits signed integers:

|  i |  bin | comp | -i | i&-i | dec |
+----+------+------+----+------+-----+
|  0 | 0000 | 0000 | -0 | 0000 |   0 |
|  1 | 0001 | 1111 | -1 | 0001 |   1 |
|  2 | 0010 | 1110 | -2 | 0010 |   2 |
|  3 | 0011 | 1101 | -3 | 0001 |   1 |
|  4 | 0100 | 1100 | -4 | 0100 |   4 |
|  5 | 0101 | 1011 | -5 | 0001 |   1 |
|  6 | 0110 | 1010 | -6 | 0010 |   2 |
|  7 | 0111 | 1001 | -7 | 0001 |   1 |
| -8 | 1000 | 1000 | -8 | 1000 |   8 |
| -7 | 1001 | 0111 |  7 | 0001 |   1 |
| -6 | 1010 | 0110 |  6 | 0010 |   2 |
| -5 | 1011 | 0101 |  5 | 0001 |   1 |
| -4 | 1100 | 0100 |  4 | 0100 |   4 |
| -3 | 1101 | 0011 |  3 | 0001 |   1 |
| -2 | 1110 | 0010 |  2 | 0010 |   2 |
| -1 | 1111 | 0001 |  1 | 0001 |   1 |

Remarks:

1. You can conjecture that i&-i only has one bit set (it's a power of 2) and it matches the least significant bit set of i.
2. i + (i&-i) has the interesting property to be one bit closer to the next power of two.
3. i += (i&-i) sets the least significant unset bit of i.

So, doing i += (i&-i); will eventually make you jump to the next power of two:

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 1 |    1 |   2 |     | 5 |    1 |   6 |
| 2 |    2 |   4 |     | 6 |    2 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 3 |    1 |   4 |     | 7 |    1 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

UB: overflow of signed integer exhibits undefined behavior.