Often big numbers become negative

Question

Since I started using eclipse for project euler, I noticed that big numbers sometime become a seemingly random negative numbers. I suppose this has something to do with passing the boudry of the type.

I'll be glad if you could explain to me how these negative numbers are generated and what is the logic behind it. Also, how can I avoid them (preferable not with BigInteger class). Danke!=)

Answer 1

This image shows what you're looking for. In your case it's obviously larger numbers, but the principle stays the same.

Examples of limits in java are:
int: −2,147,483,648 to 2,147,483,647.
long: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

In the image 0000, 0001 etc, shows the binary representation of the numbers.

EDIT: In project euler you often have to think of a way to work around the lagre numbers. The problems are designed with numbers that big so that you can't use the ordinary way of problem solving. However, if you find that you really need to use them, i suggest studying BigInteger anyway. You will find it useful in the long run, and it's not all that complicated. Here is a link with lots of understandable examples: BigInteger Example

Answer 2

In mathematics numbers are infinite. However in computers they are not. There is MAX_VALUE for each int-like type: int, short, long. For example Integer.MAX_VALUE. When you try to increase number more than this value the number becomes negative. This way the internal binary representation of numbers work.

int i = Integer.MAX_VALUE;
i++; // i becomes negative. 

Answer 3

Here's a two's complement representation for 2-bit integer: (U means Unsigned, S means Signed)

 U | bits |  S
---------------
 0 |  00  |  0 
 1 |  01  |  1 \ overflow here:
 2 |  10  | -2 /   1 + 1 = -2
 3 |  11  | -1

Arithmetic is done mostly like in the unsigned case, modulo max(U) (4 in our case).

The logic is the same for bigger types. int in Java is 32 bit. Use long for 64 bits.

Answer 4

You are probably overflowing the size of your data type, since the most significant bit is the sign bit. I don't think that Java has unsigned data types, so you may try using a larger data type such as long if you want to hold bigger numbers than int. If you are still overflowing a long though, you're pretty much stuck with BigInteger.