Basics of The Integer in the Binary World

Talking about overflows, Tom in my previous post mentioned -(-x) != x problem. Precisely, -(2^31) * -1 != 2^31 . What happened?

To understand this, we must understand how integers work in the reality and the binary world.

In reality, integers form a countably infinite set [1]. They have no upper or lower limits. So, in our mind, we can visualize it this way :

The line expands forever to the left and forever to the right.

In the binary world, this is another story. For an integer, we have only 4 bytes ( 32 bits ). By nature, an integer can only represent as many as 2^32 = 4294967296 values. Which means, integers in computers cannot represent the countably infinite nature of integers as in reality. Once the limits are exceeded, it wraps around. Like a wheel :

As you can see, if you subtract 1 from -2147483648 (-2^31), the integer in binary world no longer behaves in what we believe.

(-2^31) – 1
= -214783648 – 1
= +2147483647

Notice that overflowing by subtracting 1 from -(2^31) does not yield (2^31) but (2^31-1). Why? Because 0 is also a value in integer, and thus requires one representation as well. Now there are only (2^32-1) choices left, and so the positive value of -(2^31) is now missing.

That is what Tom is talking about. Since the positive of -(2^31) cannot be represented, -(-(2^31)) = -(2^31).

This goes the same for :

-(2^31) * -1 = -(2^31)
-(2^31) / -1 = -(2^31)

The following code compiling in VC++ demonstrates :

#include <cstdio>
#include <climits>

int main()
{
	printf("%12s\t%12s\t%12s\t%12s\t%12s\n","x","-x","x*-1","x/-1","x-1");
	for ( int i=0; i<10; ++i )
	{
		int x = INT_MIN+i;
		printf("%12d\t%12d\t%12d\t%12d\t%12d\n",x,-x,x*-1,x/-1,x-1);
	}
	return 0;
}

The output of the program is :

           x              -x            x*-1            x/-1             x-1
 -2147483648     -2147483648     -2147483648     -2147483648      2147483647
 -2147483647      2147483647      2147483647      2147483647     -2147483648
 -2147483646      2147483646      2147483646      2147483646     -2147483647
 -2147483645      2147483645      2147483645      2147483645     -2147483646
 -2147483644      2147483644      2147483644      2147483644     -2147483645
 -2147483643      2147483643      2147483643      2147483643     -2147483644
 -2147483642      2147483642      2147483642      2147483642     -2147483643
 -2147483641      2147483641      2147483641      2147483641     -2147483642
 -2147483640      2147483640      2147483640      2147483640     -2147483641
 -2147483639      2147483639      2147483639      2147483639     -2147483640

Look carefully at the 1st line. -2147483648 is -(2^31), our number of interest.

This is the basics of integer overflow problems, and I hope you have learned more about how integers work.

—

References :

[1] http://en.wikipedia.org/wiki/Integers