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.
Showing posts with label min. Show all posts
Showing posts with label min. Show all posts
2013-05-17
The Scientific 7-Minute Workout
Have you all heard about the scientific 7 minute workout yet?
On LifeHacker
In The New York Times
Here's a link to a timer to make things even easier for you: http://7-min.com/
~ Simply Advanced ~
Subscribe to:
Posts (Atom)