我将这些大的随机操作循环进行了基准测试(只是因为我很好奇),遇到了我不明白的东西。无论我对大循环的输入如何,它总是会产生相同的结果。这是我在谈论的部分。
public int stuff;
public int result;
myJavaProgram(String[] cmdArguments)
{
stuff=1;
superLoopCalcualtion();
System.out.println(stuff+" converted to result:"+result);
stuff=12345;
superLoopCalcualtion();
System.out.println(stuff+" converted to result:"+result);
stuff=9823450;
superLoopCalcualtion();
System.out.println(stuff+" converted to result:"+result);
}
public void superLoopCalcualtion()
{
int a=stuff;
int b=a+99;
int z=0;
for (z = 0; z < 200000; z++)
{
a=a+22;
b=a*44;
a=b+1234;
}
result=a;
}
,输出是此
1 converted to result:1398361394
12345 converted to result:1398361394
9823450 converted to result:1398361394
没有办法是对的...对?
您在这里看到的是(伪装)溢出,导致有效的乘法因子为0,从而有效地结束了循环中的值变化。
溢出在动作
要查看此问题,让我们使用byte
S的简化代码示例,该示例允许循环缩短:
byte a = stuff;
for (byte z = 0; z < 8; z++) {
a = (byte) (a * 2);
}
我省略了每次迭代以十进制和二进制的数字打印数字的代码。这是stuff
的结果为1、11和127(Byte.MAX_VALUE
):
1
---
0: 1 00000001
1: 2 00000010
2: 4 00000100
3: 8 00001000
4: 16 00010000
5: 32 00100000
6: 64 01000000
7: -128 10000000
8: 0 00000000
11
---
0: 11 00001011
1: 22 00010110
2: 44 00101100
3: 88 01011000
4: -80 10110000
5: 96 01100000
6: -64 11000000
7: -128 10000000
8: 0 00000000
127
---
0: 127 01111111
1: -2 11111110
2: -4 11111100
3: -8 11111000
4: -16 11110000
5: -32 11100000
6: -64 11000000
7: -128 10000000
8: 0 00000000
要理解这一点,请考虑将二进制数乘以2乘以右侧添加0
。如果我们不断这样做,我们"推"我们的数据结构可以保留的范围左侧的数字。对于byte
,该范围是8位。因此,在将8次乘以2次之后,我们保证无论事先包含什么数字,现在都是0
s。继续没有效果,因此我们停滞不前(或陈词滥调,无论该术语是什么)。
在"可见"之外推动大量位范围称为溢出,因为二进制表示无法包含它们,并且它们……溢出。在十进制中,这会导致符号 1 的变化。如果您查看1
的示例,则该溢出仅在最后一次迭代中发生,因为数字足够小,这相当于说它的右边有很多可用空间。另一方面,127
立即溢出,因为它是byte
的最大值,也就是说,所有位都是需要的。
1 在Java中签署了所有数字。
应用于您的代码
从这里开始,这是逐步添加复杂性直到我们达到您的代码的问题,但是基本现象是相同的。
对于初学者,我们可以使用short
,int
和long
提高二进制表示能力,但这只是延迟了不可避免的。我们将分别需要12、32和64,而不是需要8次迭代。
接下来,我们可以更改乘法因子。偶数数字只是2的乘法,因此我们将达到相同的结果。请注意,对于2^n
的特殊情况,我们将始终更快地达到结果,因为我们有效地削减了迭代。但是,如果有一个奇数,我们将永不到达(十进制)0
;溢出将始终跳过它,我们将再次达到起始号码。这是stuff = 1
(字节),具有乘法因子3
,用于64(Byte.MAX_VALUE / 2 + 1
)迭代:
1
---
0: 1 00000001
1: 3 00000011
2: 9 00001001
3: 27 00011011
4: 81 01010001
5: -13 11110011
6: -39 11011001
7: -117 10001011
8: -95 10100001
9: -29 11100011
10: -87 10101001
11: -5 11111011
12: -15 11110001
13: -45 11010011
14: 121 01111001
15: 107 01101011
16: 65 01000001
17: -61 11000011
18: 73 01001001
19: -37 11011011
20: -111 10010001
21: -77 10110011
22: 25 00011001
23: 75 01001011
24: -31 11100001
25: -93 10100011
26: -23 11101001
27: -69 10111011
28: 49 00110001
29: -109 10010011
30: -71 10111001
31: 43 00101011
32: -127 10000001
33: -125 10000011
34: -119 10001001
35: -101 10011011
36: -47 11010001
37: 115 01110011
38: 89 01011001
39: 11 00001011
40: 33 00100001
41: 99 01100011
42: 41 00101001
43: 123 01111011
44: 113 01110001
45: 83 01010011
46: -7 11111001
47: -21 11101011
48: -63 11000001
49: 67 01000011
50: -55 11001001
51: 91 01011011
52: 17 00010001
53: 51 00110011
54: -103 10011001
55: -53 11001011
56: 97 01100001
57: 35 00100011
58: 105 01101001
59: 59 00111011
60: -79 10110001
61: 19 00010011
62: 57 00111001
63: -85 10101011
64: 1 00000001
我不想大量的数学,因为我觉得这是问题的范围。可以说在MAX_VALUE / 2 + 1
迭代中,您将再次到达起始数字(在此之前也有一些数字)。
关键是您的44
甚至是,因此您获得停滞的结果。
现在进行您的附加操作。在乘法之前和之后,与它们一起玩,它的作用不仅仅是通过常数更改结果。效果保持不变。考虑
for (byte z = 0; z < 10; z++) {
a = (byte) (a + 1);
a = (byte) (a * 2);
}
结果是
1
---
0: 1 00000001
1: 4 00000100
2: 10 00001010
3: 22 00010110
4: 46 00101110
5: 94 01011110
6: -66 10111110
7: 126 01111110
8: -2 11111110
9: -2 11111110
10: -2 11111110
所以我们停滞在-2
上。在十进制中,您可以通过循环公式很容易看到它:(-2 + 1) * 2 = -2
。您的"随机"在〜15次迭代后,(确定性地)在 1398361394
安置数字(确定性地)中的数字选择(使用long
S会延迟一些迭代次数)。只需通过迭代进行数学迭代,您将达到上述循环公式。
结论时间
要非常小心溢出!确保您选择的数据结构始终足以包含您正在使用的数字范围。最糟糕的情况,您的(非重要性)类型BigInteger可用于任意精度(但要慢得多)。不管上面讨论的任何参数如何,一旦溢出数学结果将是错误的(除非您故意进行溢出数学)。