Integer Overflows
Integers can be signed or unsigned. If they are signed, their leading bit is used to represent their sign. The leading bit is the left-most bit. Different systems represent zero or negative numbers differently, as shown below:
| Binary |
Decimal (One's Complement) |
Decimal (Two's Complement) |
Decimal (Sign Magnitude) |
| 0000 |
+0 |
0 |
+0 |
| 0001 |
+1 |
+1 |
+1 |
| 0010 |
+2 |
+2 |
+2 |
| 0011 |
+3 |
+3 |
+3 |
| 0100 |
+4 |
+4 |
+4 |
| 0101 |
+5 |
+5 |
+5 |
| 0110 |
+6 |
+6 |
+6 |
| 0111 |
+7 |
+7 |
+7 |
| 1000 |
-7 |
-8 |
-0 |
| 1001 |
-6 |
-7 |
-1 |
| 1010 |
-5 |
-6 |
-2 |
| 1011 |
-4 |
-5 |
-3 |
| 1100 |
-3 |
-4 |
-4 |
| 1101 |
-2 |
-3 |
-5 |
| 1110 |
-1 |
-2 |
-6 |
| 1111 |
-0 |
-1 |
-7 |
For example, in a system implemented using sign-magnitude, the following binary values are equal to the following decimal values:
0101 = +(1×2
0 + 0×2
1 + 1×2
2) = +(1 + 4) = +5
1010 = -(0×2
0 + 1×2
1 + 0×2
2) = -2
Notice how in the above, we do not consider the 2
3 field (the left-most binary value) except for defining the sign. Consider now our 4-bit examples above, and suppose we would like to know the maximum signed integer value for a 4-bit integer. This would occur when all of the bits are set to the value of 1 (except for the leading sign bit):
0111 = +(1×2
0 + 1×2
1 + 1×2
2) = +(1 + 2 + 4) = +7
Note how the above result can be computed:
7 = 2
(n-1) - 1 = 2
(4-1) - 1 = 2
3 - 1 = 8 - 1.
Above, n is the number of bits (in this case the number of bits is 4, since I am referring to 4-bit signed integers). This formula comes from the Geometric Series, where the sum from k = 0 to n of a series of the form ar
k = a + ar + ar
2 + ar
3 ... + ar
n = a(1-r
[n+1])÷(1-r). See an external link for a better, more visual formula from the Geometric Series.
Similarly in 32-bit systems, an integer value can take a maximum and a minimum. A signed 32-bit integer would have thirty-two bits at its disposal, with one bit to represent it being either negative or positive.
Thus, the maximum positive value a 32-bit signed integer may take is 2
31 - 1 = 2
(n-1) - 1. Compare this to an unsigned 32-bit integer, which has a maximum positive value of 2
32 - 1 (it is raised to the power of 32 because no bit is used to represent the sign).
Now, 32-bit signed integers have a minimum of 2
31. There is no -1 term, because, as per the Two's Compliment systems, only one value represents 0 (zero cannot have both a positive and a negative sign bit), so negative numbers have an extra value in this system.
An integer overflow occurs when signed integers go past their limits, which can cause unexpected program behavior. ISO (International Standardization Organization) standards allow wrapping values around in order to avoid overflows.
So what happens when an integer overflow does happen? The ISO C99 has this to say: "A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type."
Read the definition a couple of times until it makes sense, and review modular division. This basically means that, if you add two signed or unsigned integer variables and store it back into a signed or unsigned integer variable, there is a chance that you will get a wrap-around effect if the result is bigger than the maximum integer value for your integer variable (mentioned above for 32-bit integers). This means the value stored in your integer variable will be smaller than the actual result you would expect, due to modular division as set by the ISO standard.
Summary
Be careful when using integer data types. Make sure your users can't cause unexpected program behavior to occur because of the set standards. You need to be especially careful when working with integer data types, because as an example, the sum of two integers, when stored into an integer data type, can theoretically cause a wrap-around. Let's say I have a ticket application. There are two types of tickets, tickets for the water park and tickets for the amusement park. Say I give a discount to people who buy over a thousand tickets. If I use integers, add up the total number of the two types of tickets, and then compare it to see who gets the discount, and the user buys more tickets in total than can fit into an integer data type, it might accidentally cause the total number of tickets to overflow, to an amount less than a thousand tickets, even though the user may have tried purchasing billions of tickets, and he will not get the discount!
Thank you for reading this article. If you have any suggestions or need clarification please do not hesitate to start a thread on my
forum or to send me an
e-mail. There is no such thing as a stupid question, but there is such a thing as a stupid fear of asking.
