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; }

## I'm Brian! No I'm Brian! I'm Brian and so's my wife!

This is an introductory post, setting the scene for things to come. Over the foreseeable future I'm going to embark on a minor project, whilst posting updates here for anyone who may be interested. ...

AGunner October 23rd, 2014 01:44 PM