java - ^32 限制和模方法

Question

在 Java 中，整数必须介于 2^31 - 1 到 -2^31 之间

所以如果 int x = 2 * 1500000000

逻辑答案将是 300000000 但因为它的值有限制，因此将其向前推进并使用 2^32 mod 3000000000 它将是 -1294967296 但因为它向前推进，数字将变为负数，因为正数字段已溢出。我说这是真的吗？

此外，我还搜索并阅读了调制部分，例如在时钟中 15 mod 12 == 3 因为它是除法的余数，但它很适合作为时钟的示例，因为 12 在这里是一个常数。

那么2^32是所有整数调制计算溢出的常数吗？

Answer 1

为了简单起见，我将使用 8 位整数。

在二进制中，8 位范围从 00000000b 到 11111111b。

00000000b = 0d
11111111b = 255d

那么计算机如何给整数加符号呢？这是two's complement .

对于无符号整数，我们通过以下方式将 11111111b 从二进制转换为十进制:

  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

那么有符号整数11111111b怎么样？这是一个简单的方法:

  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

一般来说，有符号数的最高有效位是符号标志。

要将负十进制数转换为二进制补码:

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

8位有符号整数的范围是从-2^7到2^7-1。

现在什么是溢出？让我们看看:

  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)

因此，如果我们将最大的 8 位有符号整数加 1，结果就是最小的 8 位有符号整数。 +ve++ve -> -ve 是一个溢出错误。

减法怎么样？ 45-16？ (+ve + -ve -> +ve)

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

45-64 怎么样？ (+ve + -ve -> -ve)

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

-64-64 怎么样？ (-ve + -ve -> -ve)

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

-64-65怎么样？

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

所以 -ve + -ve -> +ve 是一个下溢错误。

32 位整数的情况类似，只是可用位数更多。

对于您的问题2*1500000000，如果我们将它们视为32位无符号整数，则结果为3000000000，其二进制表示为:

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

但是如果我们将其视为 32 位有符号整数:

  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

<小时/>

添加:无符号整数溢出

无符号整数的溢出非常相似:

  11111111b
= 255d

  11111111b + 1
= 00000000b
= 0d

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

这就是为什么对于 32 位无符号整数，它始终是 mod 2^32。

顺便说一句，这不仅适用于 Java，也适用于大多数编程语言，例如 C/C++。其他一些编程语言可能会自动处理溢出并将类型更改为更高精度或浮点，例如 PHP/JavaScript。