Why does foo+=foo+1 in a loop result in -1?

Question

While reviewing for an exam I noticed I had written a logical error and I believe it is because of the compound assignment += because the Increment ++ executes as intended but it only occurs when assigning the value of foo to foo +1 or

foo += foo + 1;

Here is the code.

//Break Statement
    Boolean exit = false;
    int foo = 1, bar = 60;
    while (!exit) {         
        foo+=foo+1; //Bad Code
        //foo++; //Good Code
        //foo=foo+1; // Good Code
        //foo+=1; // Good Code
        //System.out.println(foo); //Results in -1 (Infinite Loop)
        if (foo == bar) {
            break;
        }
        System.out.println("stuff");
    }

My question is why does foo+=foo+1 result in -1?

Please Note: I am new to Stackoverflow and unable to vote up your answer so know that I am thankful for any help and thank you in advance!

Answer 1

If you're talking about it being -1 at the end of the loop; it's just because int is signed and it wraps around.

int foo = 1;
while (foo >= 0) {
    foo += foo + 1;
}
System.out.println(foo);

Will output -1. You can trace through it:

foo += 1 + 1 ---> 3
foo += 3 + 1 ---> 7
foo += 7 + 1 ---> 15
foo += 15 + 1 ---> 31
foo += 31 + 1 ---> 63
foo += 63 + 1 ---> 127
foo += 127 + 1 ---> 255
foo += 255 + 1 ---> 511
foo += 511 + 1 ---> 1023
foo += 1023 + 1 ---> 2047
foo += 2047 + 1 ---> 4095
foo += 4095 + 1 ---> 8191
foo += 8191 + 1 ---> 16383
foo += 16383 + 1 ---> 32767
foo += 32767 + 1 ---> 65535
foo += 65535 + 1 ---> 131071
foo += 131071 + 1 ---> 262143
foo += 262143 + 1 ---> 524287
foo += 524287 + 1 ---> 1048575
foo += 1048575 + 1 ---> 2097151
foo += 2097151 + 1 ---> 4194303
foo += 4194303 + 1 ---> 8388607
foo += 8388607 + 1 ---> 16777215
foo += 16777215 + 1 ---> 33554431
foo += 33554431 + 1 ---> 67108863
foo += 67108863 + 1 ---> 134217727
foo += 134217727 + 1 ---> 268435455
foo += 268435455 + 1 ---> 536870911
foo += 536870911 + 1 ---> 1073741823
foo += 1073741823 + 1 ---> 2147483647
foo += 2147483647 + 1 ---> -1

The math just works out that way. Each iteration results in a value that is 1 less than a power of 2. I guess if you worked out the algebra you could show this. So it makes sense that it would hit -1, which, in a 32-bit signed int, is 2³²-1.

Then as tom and Tomáš Zíma astutely point out, it gets stuck because -1 + -1 + 1 is still just -1.

Also note, as tom discovered in comments below, that you'll hit -1 no matter what number you start with. This is because foo += foo + 1 is the same as foo = 2 * foo + 1, which is really just foo = (foo << 1) | 1 (left shift [results in low bit 0] then turn on low bit - same as adding 1 when the number is even). So no matter what you start with, after at most 32 (or however many bits there are) iterations, you will eventually have shifted your starting value all the way off the left side and replaced it with all 1's (which, in a two's complement signed int, is the value -1). E.g. with a signed 8 bit number:

abcdefgh         starting foo, 8 unknown bits
bcdefgh0         add to itself (or multiply by two, or left shift)
bcdefgh1         add one
...
cdefgh11         again
defgh111         and again
efgh1111         and again
fgh11111         and again
gh111111         and again
h1111111         and again
11111111         and again, now it's -1
... and for completeness:
11111110         left shift -1
11111111         add 1, it's back to -1

Incidentally, no matter what number you start with, you'll never hit 60 (or any even number, for that matter). You can show this just with some quick algebra: If 60 = 2 * foo + 1, then the previous foo = 59 / 2 which is already not an integer; so you'll never ever have an integer foo such that 60 = 2 * foo + 1.

Answer 2

foo += foo + 1

is parsed as

foo = (foo) + (foo + 1)

not foo = (foo + 1)

Meaning you get

1: 3 (+ 1 + 2)
2: 7 (+3 + 4)
3: 15 (+7 +8)
4: 31 (+15 +16)
5: 63 (+32 +33)

etc

So you'll never have foo == 60 and an infinite loop instead.

eta: seems I just learnt something myself. The int rolls over and hits -1. Thanks @Jason C