Java：为什么大整数相乘会导致负数结果？

Question

我在使用Java计算整数乘法时发现了一些奇怪的行为。 我正在做一些编码练习，并遇到以下类型的fizz buzz问题。要求：给定一个整数，编写一个函数，查找小于给定整数的每个3的倍数的乘积，但不包括任何5的倍数。例如，给定17，我们希望返回12 * 9 * 6 * 3（=1944）。我编写了以下代码：

public int findProduct(int limit) { 
    int product = 1;
    for(int n = 3; n < limit; n = n + 3) {
        if (n % 5 != 0) {
            product = product * n;
        }
    }
    return product;
}

这在处理小数时是有效的。但是，经过测试发现，一旦超过33，返回值就会出现严重偏差。例如，如果我使用限制36调用函数，则返回-1.466221696E9。这使我感到困惑。我正在乘以正整数，结果却变成了负数。

然而，我发现如果声明一个双精度浮点类型，它似乎总是返回正确的结果。

public double findProduct(int limit) { 
    double product = 1;
    for(int n = 3; n < limit; n = n + 3) {
        if (n % 5 != 0) {
            product = product * n;
        }
    }
    return product;
}

我的问题是：为什么整数会出现这种情况，而双精度类型有何不同使其能够正确执行？

- C. Peck

---

超过 Double.MAX_VALUE，所以最左边的位是 '1'，这就是为什么值是负数。 - Mahamudul Hasan

Answer 1

让我们通过以Integer为例来进行解释。 Integer.MAX_VALUE可以表示为01111111111111111111111111111111，这是一个包括符号位在内的32位长的字符串。现在，如果您将1添加到上述字符串，将得到10000000000000000000000000000000，这与Integer.MIN_VALUE相同。这就是所谓的Integer溢出。

System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));
// 1111111111111111111111111111111

根据Integer#toBinaryString：

无符号整数值是参数加上 2³² 如果参数为负数；否则它等于参数。将此值转换为二进制（基数 2）的 ASCII 数字字符串，没有额外的前导 0。

这就是为什么您看不到符号位，但 Integer.MAX_VALUE 的真实值是 01111111111111111111111111111111。现在看一下这段代码：

System.out.println(Integer.toBinaryString(Integer.MAX_VALUE + 1));
// 10000000000000000000000000000000
System.out.println(Integer.toBinaryString(Integer.MIN_VALUE));
// 10000000000000000000000000000000

两个数字的输出结果相同。Java 不能防止 Integer 溢出，开发人员应该注意解决这个问题。那么可能的解决方案是什么？您可以使用其他数据类型，例如 long 或 BigInteger。以下是您可能感兴趣的最大值：

System.out.println(Integer.MAX_VALUE); // 2147483647
System.out.println(Long.MAX_VALUE); // 9223372036854775807
System.out.println(Double.MAX_VALUE); // 1.7976931348623157E308
System.out.println(Float.MAX_VALUE); // 3.4028235E38

一旦 Integer 达到 MAX_VALUE，它将开始溢出并导致负值。

- Aniket Sahrawat

---

哦。嗯。如果超过那个限制会发生什么？它会循环到最小的数字吗？那就能解释我为什么得到了一个负数的结果。 - C. Peck

@C.Peck 你可以在这里获取更多信息：https://dev59.com/OZLea4cB1Zd3GeqP7t2y#34704078 - Aniket Sahrawat

这并没有解释为什么相乘大数会得到负数。 - Wijay Sharma

Answer 2

这被称为整数溢出。基本上，您的数字变得太大，超出了存储解决方案的数据类型的范围。当这种情况发生时，由于二进制补码，数字会变成负数。双精度是一种更大的数据类型，但如果您的数字足够大，它也会变成负数。

请参阅有关二进制补码和整数溢出的文章。它们会详细解释。 编辑：来自维基百科文章的简化解释。我仍然建议您阅读此内容。 假设我们有一个3位架构（000到111）。在二进制补码中，我们说前导位确定数字是正数/负数。如果它是负数，则以下数字会以正数相加形式添加到负数中。 以下是一个简单的计数示例：

+---------+--------+
| Decimal | Binary |
+---------+--------+
|       0 |    000 |
|       1 |    001 |
|       2 |    010 |
|       3 |    011 |
|      -4 |    100 | <----- note this isn't negative 0, or +4.
|      -3 |    101 | <----- note this isn't -1, or +5
|      -2 |    110 | <----- note this isn't +6
|      -1 |    111 |<----- note this isn't -3, or +7
|       0 |    000 |
+---------+--------+

“模式重复...”

对于更大的系统，应用相同的规则（32位或64位）。数字将在2^(n-1)处绕回，其中n表示数字有多少位（例如，在上面显示的3位系统中，它在2^(3-1)=2^2=4处绕回）。请注意，使用二进制补码意味着正空间的范围缩小了一半。对于一个3位无符号整数，通常你可以从0计数到7，现在只能在-4和3之间计数（仍然是8个数字总数）。

现在尝试乘以两个正数： +2 * +3 = ?

通常这是+6，或110。但在二进制补码中，这实际上是-2。

- jsonV

---

请问您能否解释一下“由于二进制补码，数字会变成负数”的意思？ - Wijay Sharma

我编辑了我的解释，包括一个小计数系统的示例，希望该解释足够详尽。 - jsonV

Answer 3

如果您想完全避免整数溢出问题，请尝试使用BigInteger：
https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
这允许任意长度的整数。
（实际上，从查看BigInteger的源代码来看，似乎存在一个最大大小，即存储BigInteger的int[]的大小为：）

Integer.MAX_VALUE / Integer.SIZE + 1

最初的回答：比任何人合理需要的都要大得多！

- Bill Naylor

---

又是一个不错的回答，惊喜的是，你现在可以发表评论了。除此之外，快速提醒一下：注重质量，而非数量；-) - GhostCat

Answer 4

超出 Double.MAX_VALUE 范围，因此结果为负数。

例如：

对于四位二进制数据。

00001 这里最左边的比特位保留为符号位，[0 表示 +，1 表示 -]，其余 4 位用于存储值。因此，00001 二进制= 十进制 +1

因此，对于 4 位，我们将能够写入最大值为 15 的十进制值。

现在，如果我想写入 16，则会溢出值范围。

因此，如果我将十进制 16 转换为二进制数据，它将是 10000，因此符号位现在为 1。最终结果将为负数。

- Mahamudul Hasan