Level Up - Dev: Integer Overflow Not Overflowing

An integer overflow (or wraparound) occurs when a number larger than the max integer value or smaller than the min integer value is tried to be stored in the integer's memory. You could imagine a circular number line.

Ex: If you have an integer at the max positive value and add one, then the integer will wraparound and be set to the most negative value (if using a signed int. An unsigned int will wraparound to 0). And, vise-versa.

Today, I experienced a bug where I wanted to get a (signed) integer overflow, but unfortunately the int value was just going to zero instead of going to the negative numbers. Thankfully, I knew the memory/bit representation of int and was able to figure out what was going on.

Here is some simplified code, with only one small change:

    // Test #1 - has wraparound
    int wrap = 1;
    for (int i = 0; i < 34; i++) {
        print(i + ": wrap: " + wrap);
        wrap = wrap * 3;
    }

    // Test #2 - no wraparound
    int wrap = 1;
    for (int i = 0; i < 34; i++) {
        print(i + ": wrap: " + wrap);
        wrap = wrap * 2;
    }

Here is the relevant output from running the code above:

// Test #1 - has wraparound
...
13: wrap: 1594323
14: wrap: 4782969
15: wrap: 14348907
16: wrap: 43046721
17: wrap: 129140163
18: wrap: 387420489
19: wrap: 1162261467
20: wrap: -808182895
21: wrap: 1870418611
22: wrap: 1316288537
23: wrap: -346101685
24: wrap: -1038305055
25: wrap: 1180052131
26: wrap: -754810903
27: wrap: 2030534587
28: wrap: 1796636465
29: wrap: 1094942099
30: wrap: -1010140999
31: wrap: 1264544299
32: wrap: -501334399
33: wrap: -1504003197

// Test #2 - no wraparound
...
20: wrap: 1048576
21: wrap: 2097152
22: wrap: 4194304
23: wrap: 8388608
24: wrap: 16777216
25: wrap: 33554432
26: wrap: 67108864
27: wrap: 134217728
28: wrap: 268435456
29: wrap: 536870912
30: wrap: 1073741824
31: wrap: -2147483648
32: wrap: 0

33: wrap: 0

If test #1 were to continue, then the values would keep wrapping. If test #2 were to continue, then the values would stay the same at 0.

The easiest way for me to make sense of this experiment was to know that multiplying by a power of 2 (2, 4, 8, 16, 32..) is the exact same as a bit shift in the binary computer. And, the bits that made up the int were all just getting pushed out of memory in test #2 until there were no more set bits to manipulate. In test #1, more int memory bits are being flipped in order to continue the wraparound.

I would explain this at a lower level, but there are already many great resources for "bit representation of integer".


~ Danial Goodwin ~

ps - This post was mainly for myself and written quickly. If there are any questions about this, then I'd be happy to elaborate.

---

My Android Apps | My Windows Phone Apps | My Developer Blog