Click here to Skip to main content
11,433,997 members (56,910 online)
Click here to Skip to main content
Technical Blog

Tagged as

Integer Overflow in Hearthstone

, 30 Jul 2014 GPL3
Rate this:
Please Sign up or sign in to vote.
Integer Overflow Illustrated 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

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.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Grant Curell

United States United States
Grant is a specialist in computer security and networking. He holds a bachelors degree in Computer Science and Engineering from the Ohio State University. Certs: CCNA, CCNP, CCDA, CCDP, Sec+, and GHIH. More info at grantcurell.com.

Comments and Discussions

 
QuestionNot a great explanation. Pin
Qwertie5-Aug-14 6:46
memberQwertie5-Aug-14 6:46 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150428.2 | Last Updated 30 Jul 2014
Article Copyright 2014 by Grant Curell
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid