Integer Overflow in Hearthstone

How Having Over 2 Billion Health Destroys the Monster

A friend recently showed me this video and asked what happened and I thought it was a perfect illustration of a classic problem in computer science – the integer overflow.

At 8:25, the monster has a health of 1073744896. The player then doubles the monster’s health one final time and… the monster destroys itself??? Why?

How Computers Represent Numbers

To understand what happened, you first have to understand how computers represent numbers. Computers represent numbers using binary (1s and 0s). Hearthstone stores the health of a monster with what’s called a signed integer.

A signed integer is a sequence of 32 1s and/or zeros). Each digit in a binary number is called a bit. In a signed integer, the most significant bit, which is the bit to the far left, stores the sign of the number IE positive or negative. This system goes by the name of 2′s complement. Now for some examples:

If I wanted to store the number 10 in a signed integer it would look like this: 00000000 00000000 00000000 00001010. You can think of this as 2^3+2^1 = 10.

Now what about -10? A computer stores -10 as 11111111 11111111 11111111 11110110. This may seem a bit confusing. Why are all the digits a 1s now? Let’s shrink things a bit. Let’s still use 2′s complement, but instead shrink it down to 8 bits. -10 would then look like this 1111 0110. You can think of this as -(2^7)+(2^6)+(2^5)+(2^4)+(2^2)+(2^1). In other words, you make that leftmost bit position a negative number and then add every subsequent corresponding 1s digit to the negative number. So -1 would just be 1111 1111. or -128+64+32+16+8+4+2+1=-1. This example is extensible in that the exact principles I just explained apply to a number 32 bits in size such as our signed integer. I realize this explanation is a bit brief, but if it doesn’t make sense this is another thing you can Google and there are some more thorough explanations.

Why Does the Monster Die?

Multiplying a number by 2 in binary is the same as shifting everything one bit to the left. In the following list, decimal is on the left and binary is on the right. I left out the leading 0s for the sake of simplicity, but each number would have a total of 32 1s and 0s. Remember in a positive number, the leftmost bit is a 0. 0=0, 1=1, 2=10, 4=100, 8=1000, 16=10000…1073741824=01000000000000000000000000000000. That last number is 32 bits in size with the leftmost bit a 0 to indicate a positive number and the second to leftmost bit a 1 to indicate a decimal number of 1073741824. You may notice that this decimal number is awfully close to the monster’s health 1073744896. 1073744896 corresponds to 01000000 00000000 00001100 00000000 in binary. So what happens when we try to double that number? Remember when we want to double a number in binary, we just shift everything to the left one. That gives us 10000000 00000000 00011000 00000000. Notice… what’s the leftmost number now? It’s a one… which in 2′s complement is a negative number. If you do the math by hand, it’s -(2^31)+(2^11)+(2^12)=-2147477504. The game sees the negative number and registers the monster as dead.