Integer Overflow in Programming: What It Is, With One Example

Integer overflow is what happens when a calculation makes a whole number too big, or too small, for the space a program set aside to store it. The number does not grow to fit. Depending on the language and its settings, the extra part gets dropped, the program stops with an error, or the result is simply wrong. This guide explains integer overflow in plain words, then walks you through one real multiplication from the code of Tank City Reboot, a small tank game, so you can see exactly which bits are kept.

What is integer overflow? A plain definition

A computer stores most whole numbers in a fixed number of bits. Common sizes are 8, 16, 32 and 64 bits. Each size can hold only so many different values. When you add, subtract or multiply and the true answer falls outside that range, you get an integer overflow.

The Wikipedia article on integer overflow uses a car odometer as a mechanical version of the same thing. Every digit sits at 9. One more mile and the digits roll over to 0. The car really did drive those miles. The display just ran out of digits.

Computer numbers work the same way, only in base 2. If you want a refresher on how 0s and 1s make up a number, read what is a bit in a computer. That post shows that one byte, 8 bits, tops out at 255. It also notes that an extra life at 20,000 points needs more than one byte to count.

How big is a 32-bit int?

In C#, the type int is a 32-bit integer. According to Wikipedia, a signed 32-bit integer runs from -2,147,483,648 to 2,147,483,647. "Signed" means it can be negative. An unsigned 32-bit integer gives up negatives and runs from 0 to 4,294,967,295.

That is just over two billion in each direction. It sounds like a lot. But one multiplication of two medium-sized numbers can blow past it. You will see one do exactly that in a moment.

• 8 bits: 256 different values, so 0 to 255 unsigned.
• 32 bits: 4,294,967,296 different values.
• 64 bits: far more, but still a fixed limit.

What C# does when a number overflows

Tank City Reboot is written in C#, so it is worth knowing the C# rule. The Microsoft C# arithmetic operators reference says the outcome depends on whether the code runs in a checked or an unchecked context.

• Checked: at run time, the program throws an OverflowException, which is an error you can catch.
• Unchecked: the result is truncated by discarding any high-order bits that don't fit in the destination type.

Microsoft also says arithmetic runs unchecked by default. So unless you ask for checking, C# keeps the low bits and drops the rest. Microsoft gives a tiny example: adding 3 to the largest int prints -2147483646. The number ran off the top and came back in at the bottom. People call this wraparound.

"High-order bits" are the bits on the left, the ones worth the most. "Low-order bits" are the ones on the right. Hold on to that idea, because it explains the example below.

A worked example from the game's code

Tank City Reboot has encrypted zones, patches of the field drawn as a speckled fog. The speckle is not random. From the code (main ece237b, Art.cs), each fog pixel is coloured by this line:

int h = ((px >> 1) * 73856093) ^ ((py >> 1) * 19349663); o = (h & 3) != 0 ? Pal.Fog : Pal.FogLo;

Here px and py are the pixel's position. The field is 208 pixels wide, so they run from 0 to 207. The >> 1 halves them, so px >> 1 runs from 0 to 103. This line is a small hash function: it mixes two numbers into one that looks scattered.

Now take a pixel near the right edge, where px >> 1 is 103, on the top row, where py >> 1 is 0. Follow along:

1. Multiply: 103 times 73,856,093 is 7,607,177,579.
2. Compare: the int limit is 2,147,483,647. The true answer is more than three times too big.
3. Write it in binary. It needs 33 bits, one more than an int has.
4. Drop the extra left bit. That is the same as subtracting 4,294,967,296 once, which leaves 3,312,210,283.
5. Read those 32 bits as a signed int. The leftmost kept bit is 1, which marks a negative number, so the value is -982,757,013.
6. The other side is 0 times 19,349,663, which is 0. Combining with 0 using ^ changes nothing, so h is -982,757,013.

The true product needs 33 bits. C# drops the leftmost one, but the last two bits, 11, are the same before and after.

You can check the wrapped number yourself. In a browser console, type Math.imul(103, 73856093). It does 32-bit multiplication and returns -982757013.

Why the last two bits survive

The game never uses the whole value of h. It only asks for h & 3, which keeps the last two bits and throws the rest away. If bitwise AND is new to you, see what are bitwise operators.

Wraparound only removes bits on the left. It never touches bits on the right. The true answer 7,607,177,579 ends in binary 11. The wrapped answer -982,757,013 also ends in 11. So h & 3 is 3 either way. Since 3 is not 0, that pixel gets the Pal.Fog colour.

That is the key idea. The overflow happens, but the code only reads the part the overflow cannot change. The code shows the fog pattern comes out the same as it would with unlimited bits.

Where the overflow starts

Not every pixel overflows. You can find the first one with simple arithmetic:

• 29 times 73,856,093 is 2,141,826,697. That fits under 2,147,483,647.
• 30 times 73,856,093 is 2,215,682,790. That does not fit, so it wraps.

So for px >> 1 from 30 up to 103, the first product wraps. The second product is different. The largest it gets is 103 times 19,349,663, which is 1,993,015,289. That fits, so the py side of this line never overflows at all.

When overflow causes real trouble

In the fog line, wrapping is harmless. That is not always the case. The Wikipedia article on integer overflow states that an unhandled arithmetic overflow in the engine steering software was the primary cause of the crash of the 1996 maiden flight of the Ariane 5 rocket. It also describes the year 2038 problem as an upcoming integer overflow in the Unix time count of seconds since 1970.

The common thread is a value that grows past its limit when nobody planned for it. A few habits help you avoid that:

• Ask how large a value can really get, then pick a type with room to spare.
• In C#, wrap risky math in checked so an overflow raises an error instead of a quiet wrong answer.
• When you only need the low bits, as in a hash, wrapping can be fine. Say so in a comment.

Tank City Reboot teaches the idea behind names like this one. It is a game, not a course, and playing never needs an account.

Frequently asked questions

Is integer overflow always a bug?

No. In hash code like the fog line, only the low bits matter, so wrapping changes nothing that is used. It becomes a bug when the program needs the full, correct value.

What is the largest value a 32-bit int can hold?

A signed 32-bit int holds up to 2,147,483,647. An unsigned one holds up to 4,294,967,295.

Does C# check for overflow by default?

No. Microsoft's reference says arithmetic runs in an unchecked context by default, which keeps the low bits and drops the rest. Use the checked keyword to get an OverflowException instead.

Why does dropping high bits keep the last two bits the same?

Dropping a high bit subtracts a multiple of 4,294,967,296, which is itself a multiple of 4. Subtracting a multiple of 4 never changes the remainder after dividing by 4, and that remainder is exactly the last two bits.

Get started

Open Tank City Reboot in your browser and drive into an encrypted zone. Every speckle you see came from the multiplication you just worked through.