Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Increment forever and you get -2147483648?

For a clever and complicated reason that I don't really want to explain (because it involves making a timer in an extremely ugly and hacky way), I wrote some C# code sort of like this:

int i = 0;
while (i >= 0) i++; //Should increment forever
Console.Write(i);

I expected the program to hang forever or crash or something, but, to my surprise, after waiting for about 20 seconds or so, I get this ouput:

-2147483648

Well, programming has taught me many things, but I still cannot grasp why continually incrementing a number causes it to eventually be negative...what's going on here?

like image 949
Peter Olson Avatar asked May 31 '11 22:05

Peter Olson


2 Answers

In C#, the built-in integers are represented by a sequence of bit values of a predefined length. For the basic int datatype that length is 32 bits. Since 32 bits can only represent 4,294,967,296 different possible values (since that is 2^32), clearly your code will not loop forever with continually increasing values.

Since int can hold both positive and negative numbers, the sign of the number must be encoded somehow. This is done with first bit. If the first bit is 1, then the number is negative.

Here are the int values laid out on a number-line in hexadecimal and decimal:

 Hexadecimal        Decimal
 -----------    -----------
 0x80000000     -2147483648
 0x80000001     -2147483647
 0x80000002     -2147483646
    ...              ...
 0xFFFFFFFE              -2
 0xFFFFFFFF              -1
 0x00000000               0
 0x00000001               1
 0x00000002               2
     ...             ...
 0x7FFFFFFE      2147483646
 0x7FFFFFFF      2147483647

As you can see from this chart, the bits that represent the smallest possible value are what you would get by adding one to the largest possible value, while ignoring the interpretation of the sign bit. When a signed number is added in this way, it is called "integer overflow". Whether or not an integer overflow is allowed or treated as an error is configurable with the checked and unchecked statements in C#. The default is unchecked, which is why no error occured, but you got that crazy small number in your program.

This representation is called 2's Complement.

like image 61
Jeffrey L Whitledge Avatar answered Oct 03 '22 02:10

Jeffrey L Whitledge


The value is overflowing the positive range of 32 bit integer storage going to 0xFFFFFFFF which is -2147483648 in decimal. This means you overflow at 31 bit integers.

It's been pointed out else where that if you use an unsigned int you'll get different behaviour as the 32nd bit isn't being used to store the sign of of the number.

like image 35
ChrisF Avatar answered Oct 03 '22 01:10

ChrisF