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

## 0 Responses to “Basics of The Integer in the Binary World”