当使用整数计算Java的阶乘100(100!)时,我得到0

Question

这样做时:

int x = 100;
int result = 1;
for (int i = 1; i < (x + 1); i++) {
    result = (result * i);
}
System.out.println(result);

这显然是因为结果对于整数来说太大了,但我习惯于为溢出得到大的负数,而不是0.

提前致谢!

---

当我切换到这个:

int x = 100;
int result = 1;

for (int i = 1; i < (x + 1); i++) {
    result = (result * i);
    System.out.println(result);
}

我得到这个.

Answer 1

有50个偶数,介于1和100之间.这意味着阶乘是2的倍数至少50倍,换句话说,作为二进制数,最后50位将是0.(实际上,更多的是偶数第二偶数是2*2的倍数等)

public static void main(String... args) {
    BigInteger fact = fact(100);
    System.out.println("fact(100) = " + fact);
    System.out.println("fact(100).longValue() = " + fact.longValue());
    System.out.println("fact(100).intValue() = " + fact.intValue());
    int powerOfTwoCount = 0;
    BigInteger two = BigInteger.valueOf(2);
    while (fact.compareTo(BigInteger.ZERO) > 0 && fact.mod(two).equals(BigInteger.ZERO)) {
        powerOfTwoCount++;
        fact = fact.divide(two);
    }
    System.out.println("fact(100) powers of two = " + powerOfTwoCount);
}

private static BigInteger fact(long n) {
    BigInteger result = BigInteger.ONE;
    for (long i = 2; i <= n; i++)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

版画

fact(100) = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
fact(100).longValue() = 0
fact(100).intValue() = 0
fact(100) powers of two = 97

这意味着对于事实的最低位(100),97位整数将为0

实际上,对于事实(n),2的幂的数量非常接近n.事实上(10000)有9995的两个权力.这是因为它大约是1/2次幂的总和,总和接近n.即,每第二个数字甚至是n/2,并且每第4个数字具有2(+ n/4)的附加功率,并且每8个具有附加功率(+ n/8)等接近n作为总和.

Answer 2

大负数是溢出到某个范围的值; factorial(100)最后有超过32个二进制零,因此将其转换为整数会产生零.

Answer 3

为了了解原因,我们可以观察到因子的素因子化.

fac( 1) = 1             = 2^0
fac( 2) = 2             = 2^1
fac( 3) = 2 * 3         = 2^1 * 3
fac( 4) = 2 * 2 * 2 * 3 = 2^3 * 3
fac( 5) =  ...          = 2^3 * 3 * 5
fac( 6) = ...           = 2^4 * 3^2 * 5
fac( 7) = ...           = 2^4 * ...
fac( 8) = ...           = 2^7 * ...
fac( 9) = ...           = 2^7 * ...
fac(10) = ...           = 2^8 * ...
fac(11) = ...           = 2^8 * ...
...
fac(29) = ...           = 2^25 * ...
fac(30) = ...           = 2^26 * ...
fac(31) = ...           = 2^26 * ...
fac(32) = ...           = 2^31 * ...
fac(33) = ...           = 2^31 * ...
fac(34) = ...           = 2^32 * ...  <===
fac(35) = ...           = 2^32 * ...
fac(36) = ...           = 2^34 * ...
...
fac(95) = ...           = 2^88 * ...
fac(96) = ...           = 2^93 * ...
fac(97) = ...           = 2^93 * ...
fac(98) = ...           = 2^94 * ...
fac(99) = ...           = 2^94 * ...
fac(100)= ...           = 2^96 * ...

该指数2是base-2视图中的尾随零的数量,因为所有其他因子都是奇数,因此1在产品的最后一个二进制数字中贡献一个.

类似的方案也适用于其他素数,因此我们可以轻松地计算分解fac(100):

fac(100) = 2^96 * 3^48 * 5^24 * 7^16 * 11^9 * 13^7 * 17^5 * 19^5 * 23^4 *
           29^3 * 31^2 * 37^2 * 41^2 * 43^2 * 47^2 *
           53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97

因此,如果我们的计算机将数字存储在基数3中,并且具有48个特里数,则为fac(100)0(fac(99)也是,但fac(98)不会:-)

Answer 4

不错的问题 - 答案是:33因子(由于负值)-2147483648是0x80000000,或者0xFFFFFFFF80000000如果采用64位.乘以34(下一个成员)将给出一个long值0xFFFFFFE600000000,当转换为int时会给你0x00000000.

显然从那时起你将保持0.