^32 limitation and modulo methods

Question

In Java, Integers must be between 2^31 - 1 through -2^31

so if int x = 2 * 1500000000

The logical answer will be 300000000 but because it has a limit on its value, it is thus brought forward and using 2^32 mod 3000000000 it will be -1294967296 but because it is brought forward the number will become negative because the positive field is overflown. Am i right to say that this is true?

Also, I have search and read up on the modulation part, for e.g. in a clock 15 mod 12 == 3 because it is the remainder of the division however it is good as an example for a clock because 12 is a constant here.

So is 2^32 is the constant of all modulation computation of integers for overflow?

Answer 1

I am going to use 8-bit integers for simplicity.

In binary, 8 bit ranges from 00000000b to 11111111b.

00000000b = 0d
11111111b = 255d

So how do computer add signs to an integer? It's two's complement.

For unsigned integer, we convert 11111111b from binary to denary by this way:

  11111111b
= 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0
= 1*128 + 1*64  + 1*32  + 1*16  + 1*8   + 1*4   + 1*2   + 1*1
= 255d

So how about signed integer 11111111b? Here is a simple way:

  v----------(sign flag 1=negative)
  11111111b
= 1*(-2^7) + 1*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0
= 1*(-128) + 1*64  + 1*32  + 1*16  + 1*8   + 1*4   + 1*2   + 1*1
= -1d

In general, the most significant bit of a signed number is the sign flag.

To convert negative denary number to two's complement:

 -18d
 ========
 without sign     0001 0010
 one's complement 1110 1101 (inverted)
*two's complement 1110 1110 (one's complement + 1)

The range of a 8-bit signed integer is from -2^7 to 2^7-1.

Now what is overflow? Let's see:

  01111111b
= 127d

  01111111b + 1
= 10000000b
= 1*(-2^7) + 0*2^6 + 0*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 0*2^0
= 1*(-128) + 0*64  + 0*32  + 0*16  + 0*8   + 0*4   + 0*2   + 0*1
= -128d

  127d + 1d
  =========
  0111 1111 (127d)  +
 +0000 0001 (1d)    +
 ----------
  1000 0000 (-128d) - (overflow)

So if we add 1 to the largest 8-bit signed integer, the result is the smallest 8-bit signed integer. +ve + +ve -> -ve is an overflow error.

How about subtractions? 45-16? (+ve + -ve -> +ve)

  45d - 16d
  =========
  0010 1101 (45d)   +
 +1111 0000 (-16d)  -
 ----------
1 0001 1101 (29d)   +
^---------------------(discard)

How about 45-64? (+ve + -ve -> -ve)

  45d - 64d
  =========
  0010 1101 (45d)   +
 +1100 0000 (-64d)  -
 ----------
  1110 1101 (-19d)  -

How about -64-64? (-ve + -ve -> -ve)

  -64d - 65d
  =========
  1100 0000 (-64d)  -
 +1100 0000 (-64d)  -
 ----------
1 1000 0000 (-128d) +
^---------------------(discard)

How about -64-65?

  -64d - 65d
  =========
  1100 0000 (-64d)  -
 +1011 1111 (-65d)  -
 ----------
1 0111 1111 (127d)  + (underflow)
^---------------------(discard)

So -ve + -ve -> +ve is an underflow error.

The situation is similar for 32-bit integers, just more bits available.

For your question 2*1500000000, if we treat them as 32-bit unsigned integer, the result is 3000000000 and its binary representation is:

  1011 0010 1101 0000 0101 1110 0000 0000
= 1*2^31 + 0*2^30 + ...
= 1*2147483648 + 0*1073741824 + ...
= 3000000000d

But if we treat it as a 32-bit signed integer:

  v------(Let's recall this is the sign flag)
  1011 0010 1101 0000 0101 1110 0000 0000
= 1*(-2^31) + 0*2^30 + ...
= 1*(-2147483648) + 0*1073741824 + ...
= -1294967296d

---

ADDED: Overflow of unsigned integer

The overflow of unsigned integer is quite similar:

  11111111b
= 255d

  11111111b + 1
= 00000000b
= 0d

  255d + 1d
  =========
  1111 1111 (255d)  +
 +0000 0001 (1d)    +
 ----------
1 0000 0000 (0d)    - (overflow)
^---------------------(discard)

That's why for 32-bit unsigned integers it is always mod 2^32.

And BTW, this is not only for Java, but for most programming languages like C/C++. Some other programming languages may automatically handle overflow and change type to a higher precision or to floating point, like PHP/JavaScript.

Answer 2

You should be modding by 2^32, not 2^31, and then you should be taking into account the signed arithmetic: numbers higher than 2^31 get 2^32 subtracted from them.

Anyway, 2 * 1500000000 = 3000000000 is less than 2^32, but greater than 2^31, so it gets 2^32 subtracted to get -1294967296.