Programming Fundamentals/Integer Overflow

Overview

Integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of bits – either larger than the maximum or lower than the minimum representable value.

The most common result of an overflow is that the least significant representable bits of the result are stored; the result is said to wrap around the maximum (i.e. modulo power of two). An overflow condition may give results leading to unintended behavior. In particular, if the possibility has not been anticipated, overflow can compromise a program’s reliability and security.

Discussion

There are times when character and integer data types are lumped together because they both act the same (often called the integer family). It would be better to say they act differently than floating-point data types. The integer family values jump from one value to another. There is nothing between 6 and 7 nor between ‘A’ and ‘B’. It could be asked why not make all your numbers floating-point data types? The reason is twofold. First, some things in the real world are not fractional. A dog, even with only 3 legs, is still one dog not three-fourths of a dog. Second, the integer data type is often used to control program flow by counting (counting loops). The integer family has a circular wrap-around feature. Using a two-byte integer, the next number bigger than 32767 is negative 32768 (character acts the same way going from 255 to 0. We could also reverse that to be the next smaller number than negative 32768 is positive 32767. This can be shown by using a normal math line, limiting the domain and then connecting the two ends to form a circle.

This circular nature of the integer family works for both integer and character data types. In theory, it should work for the Boolean data type as well; but in most programming languages it does not for various technical reasons.

“In mathematics, modular arithmetic (sometimes called clock arithmetic) is a system of arithmetic for integers where numbers “wrap around” after they reach a certain value — the modulus. …

A familiar use of modular arithmetic is its use in the 12-hour clock the arithmetic of time-keeping in which the day is divided into two 12 hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Regular addition would suggest that the later time should be 7 + 8 = 15, but this is not the answer because clock time “wraps around” every 12 hours; there is no “15 o’clock”. Likewise, if the clock starts at 12:00 (noon) and 21 hours elapse, then the time will be 9:00 the next day, rather than 33:00. Since the hour number starts over when it reaches 12, this is arithmetic modulo 12.

Time-keeping on a clock gives an example of modular arithmetic.” (Modular arithmetic from Wikipedia)

The use of the modulus operator in integer division is tied to the concepts used in modular arithmetic.

Implications When Executing Loops

If a programmer sets up a counting loop incorrectly, usually one of three things happen:

• Infinite loop – usually caused by missing update attribute.
• Loop never executes – usually, the text expression is wrong with the direction of the less than or greater than relationship needing to be switched.
• Loop executes more times than desired – update not properly handled. Usually, the direction of counting (increment or decrement) needs to be switched.

Let’s give an example of the loop executing for what appears to be infinity (the third item on our list).

for int x = 0, x < 10, x--
    Output x

The above code accidentally decrements and the value of x goes in a negative way towards -2147483648 (the largest negative value in a normal four-byte signed integer data type). It might take a while (thus it might appear to be in an infinite loop) for it to reach the negative 2 billion-plus value, before finally decrementing to positive 2147483647. Which would, incidentally, stop the loop execution.

Key Terms

circular nature

Connecting the negative and positive ends of the domain of an integer family data type.

loop control

Making sure the attributes of a loop are properly handled.

modular arithmetic

A system of arithmetic for integers where numbers “wrap around”.

References

• cnx.org: Programming Fundamentals – A Modular Structured Approach using C++

Programming Fundamentals