Article Categories
Tag Cloud
Problem category: Logic Error
Diagnosis Difficulty: Easy-Hard
Difficulty to Fix: Easy-Medium
In java (and most other programming languages) integer data is represented using binary numbers. While in theory these numbers could be of infinite bit length, this notion is impractical for most computations. So Java defines several data types with different fixed bit lengths. These are:
byte - at least 8 bits
char - at least 16 bits (technically this shouldn't be used as an integer data type, but it can be used as one)
int - at least 32 bits
long - at least 64 bits
What does the "at least" mean? Well, in almost all Java implementations (definitely in Sun/Oracle's implementation) this could be dropped. So a byte is exactly 8 bits and so on and so forth. I used "at least" because technically that's what the language specification says explicitly (actually, it states the min/max range of each data type should at least cover, but that could roughly be translated to these bit lengths if we ignore any potential overhead).
Each integer type is organized with the sign bit being the most significant bit (furthest left, MSB) and all the other bits representing the magnitude of the number (note that char's don't have the sign bit and all bits represent the magnitude of the number). *Note: Floats and doubles are represented differently, and won't run into this "wrapping problem". However, they will run into other problems concerning floating-point math.
Now how the computer represents negative numbers is using two's compliment.
Two's compliment works by inverting all the bits and adding one. So, for example:
11111111b: invert all the bits results in 00000000b, then adding one is 1b. So 11111111b=-1
Note that two's compliment is only computed for numbers with the MSB set.
What happens when you try to increment the number 01111111b (127)? It becomes 10000000b, which represents -128.
byte counter = 0; for (int i = 0; i < 0x100; i += 8) { System.out.print(counter + " "); counter += 8; }
0 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 -128 -120 -112 -104 -96 -88 -80 -72 -64 -56 -48 -40 -32 -24 -16 -8
Suggested fixes
The easiest fix is to simply use a larger data type.
Byte < char (note you'll have to worry about the no sign bit part, I'd skip this for most integer calculations) < int < long
So if you currently have a byte and it's overflowing, go to an int and so on and so forth.
What could you do if your longs are overflowing? The only other option is to go to the BigInteger class. This class is designed to handle integers using a "theoretical" infinite bit length. For the purposes of this post I won't discuss how they do this. However, even BigInteger is limited by your computer's physical memory to how large of numbers it can hold (but even with ~64 bytes, your number range would be 2^511-1, or 67039039649712985497870124991029230637396829102961 96688861780721860882015036773488400937149083451713 84501592909324302542687694140597328497321682450304 2047, which is significantly larger than a Google).
int counter = 0; for (int i = 0; i < 0x100; i += 8) { System.out.print(counter + " "); counter += 8; }