logo标签列表

使用Java整数计算100的阶乘（100！）时，结果为0。

javaoverflowintfactorial
16

当进行以下操作时：

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);
}

我获得了这个。

3
这不是计算阶乘的最佳方法。你知道的，对吧？ - duffymo
1
即使您没有得到0，您的循环也无法计算阶乘。 - RoflcoptrException
@duffymo：是的，我只是对输出结果感到好奇。谢谢！ - Trufa
@Roflcoptr：我认为它可以，我刚用正确的结果测试了9。 - Trufa
@duffymo 当然！毕竟，如果我想要 5!，我不会去做 5*4*3*2*1。我会计算 gamma(6)！ - Cole Tobin
10个回答
26

1到100之间有50个偶数。这意味着阶乘至少可以被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

这意味着一个97位的整数在计算fact(100)的最低位时会等于0。

事实上，幂次为2的数量在fact(n)中非常接近n。对于fact(10000)，有9995个2的幂次。这是因为它近似于n次1/2幂次之和，总和接近于n。也就是说，每隔一个数是偶数n/2，每隔4个数多一次2的幂次（+n/4），每隔8个数多两次2的幂次（+n/8）等，逐步趋近于n。

1
@Trufa：尝试在每一步之后打印(BigInteger 和 int)的结果，以获得更深入的洞察。 - Paŭlo Ebermann
@PaloEbermann：我已经解决了这个问题，但对于0的结果感到好奇。谢谢！ - Trufa
希望我已经解释清楚了，为什么计算大阶乘时，你会得到许多结尾的0位，实际上fib(34).intValue() == 0。 - Peter Lawrey
@PeterLawrey：我已经理解了你的大部分回答，我还在仔细阅读和编辑中，数学对我来说不是那么快（但我会努力...） :) - Trufa
@RonK，感谢您发现了这个问题，在看到您的评论之前我已经更改了它。fib应该是斐波那契的缩写，fact是阶乘的更好的缩写。我已经写了太多次这些斐波那契/阶乘的答案了。 ;) - Peter Lawrey
22

大负数是指溢出到某些范围的值；factorial(100) 的末尾有超过32个二进制零，所以将其转换为整数会得到零。

8

为了找出原因，我们可以观察阶乘的质因数分解。

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 * ...
< p > 对于 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

因此，如果我们的计算机以三进制存储数字，并且有48位数字，fac(100) 将为 0（fac(99) 也是如此，但 fac(98) 不是 :-)

6
不错的问题 - 答案如下：33的阶乘（由于负值）是-2147483648，即0x80000000或者取64位时为0xFFFFFFFF80000000。将其与下一个数字34相乘，将会得到一个长整数0xFFFFFFE600000000，但强制转换为int类型后将得到0x00000000。
很明显，从那时起你将一直保持为0。
3

使用递归和BigIntegers的简单解决方案：

    public static BigInteger factorial(int num){
    if (num<=1)
        return BigInteger.ONE;
    else
        return factorial(num-1).multiply(BigInteger.valueOf(num));
    }

输出：

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
0
Java中的BigInteger类。BigInteger类用于进行涉及超出所有可用原始数据类型限制的非常大整数计算的数学运算。
要计算非常大的数字，我们可以使用BigInteger。
例如，如果我们想计算45的阶乘， 答案= 119622220865480194561963161495657715064383733760000000000。
 static void extraLongFactorials(int n) {
       BigInteger fact = BigInteger.ONE;
        for(int i=2; i<=n; i++){
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        System.out.println(fact);
    }

BigInteger 的主要方法包括 BigInteger.ONE、BigInteger.ZERO、BigInteger.TEN 和 BigInteger.ValueOf()。

0

（在这里找到，稍作修改以适应问题）

public static void main(String[] args) {

    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= 100; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    System.out.println(fact);
}
0
package test2;

import java.math.BigInteger;
import java.util.Scanner;

public class Factorial extends Big {

    public static void main(String args []){ 
    int x,fact=1,i ;
    Scanner sc = new Scanner(System.in);
    
    
    System.out.println("press any dight and 0 to exit");
    while (sc.nextInt()!=0)
    {
    System.out.println("Enter the values ");
    x=sc.nextInt();
    if(x<26)

    {
    for( i=1;i<=x;i++)
    {   fact = fact*i;  }
    
    System.out.println("Factorial of "+x + "is "+ fact );
    
    fact=1;
    }
    else 
    {
        System.out.println("In else big....");
    BigInteger k=fact(x);
    
    System.out.println("The factorial of "+x+"is "+k);
    System.out.println("RESULT LENGTH\n"+k.toString().length());
    }
    System.out.println("press any dight and 0 to exit");
    }
    System.out.println("thanks....");
    }
    
        
    
    
}
//----------------------------------------------------//

package test2;

import java.math.BigInteger;

public class Big {

    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);
    }

    public static BigInteger fact(long n) {
        BigInteger result = BigInteger.ONE;
        for (long i = 2; i <= n; i++)
            result = result.multiply(BigInteger.valueOf(i));
        return result;
    }
    
}
我已经从Big类扩展了这个类。 - VIJAY PRATAP SINGH
最小值和最大值为2450。 - VIJAY PRATAP SINGH
它提供了无限的阶乘程序，但最佳结果显示在2450，并且还取决于硬件。"System.out.println("RESULT LENGTH\n"+k.toString().length());" 显示结果集长度。 - VIJAY PRATAP SINGH
0
import java.util.*;
import java.math.*;
public class BigInteger_Factorial {
    public static void main(String args []){
        Scanner s = new Scanner(System.in);

        BigInteger x,i,fac = new BigInteger("1");
        x = s.nextBigInteger();

        for(i=new BigInteger("1"); i.compareTo(x)<=0; i=i.add(BigInteger.ONE)){
            fac = fac.multiply((i));
        }
        System.out.println(fac);
    }
}

输入100的输出：

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

输出图像：

Output result

-1

肯定是溢出了，你可以尝试使用双精度浮点数，64位长整型可能太小了。

是的，有的——快速计算显示超过75个零，这比长整型的64位还要多。 - Jeremiah Willcock
嗨，谢谢！这应该是一个注释，而不是一个答案。不，对于100来说还是太小了，唯一的办法就是使用BigInteger。 - Trufa
@Trufa：如果你只需要大致结果，你可以使用double，这比BigInteger要快得多。 - Paŭlo Ebermann
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接