java - 为什么 Collat​​z 猜想程序不适用于 Java 中的大整数

Question

这是我为在 Java 上模拟 Collat​​z 猜想而编写的一个程序：

import java.util.*;
public class Collatz {
public static void main(String args[]){
    Scanner raj= new Scanner(System.in);
    int n;
    int k=0;
    System.out.print("n? ");
    n = raj.nextInt();
    while(n > 1){
        if(n%2 ==1){
            n=3*n+1;
            System.out.println(n);
            k++;
        }
        if(n%2==0){
            n=n/2;
            System.out.println(n);
            k++;
        }

    }
    System.out.print("It took " + k + " iterations!");
}

}

当我输入 n=6 时，我得到

3 10 5 16 8 4 2 1 需要 8 次迭代！

但是当我输入 n= 63728127 时，我得到

191184382 95592191 286776574 1433388287 430164862 215082431 645247294 322623647 967870942

什么地方出了错？为什么？我该如何解决？谢谢！

Answer 1

这是整数溢出的经典案例。原始整数在 Java 中的范围有限。如果必须处理大整数，解决方案是始终使用BigInteger之类的东西。

顺便说一句，如果 Java 像几乎所有其他现代语言一样支持运算符重载，事情就会容易得多。

import java.util.*;
import java.math.BigInteger;


public class Collatz {
    public static void main(String args[]){
        Scanner raj= new Scanner(System.in);
        int k=0;
        System.out.print("n? ");

        BigInteger n = BigInteger.valueOf(raj.nextLong());

        while(n.compareTo(BigInteger.ONE) > 0){
            if(n.testBit(0)){
                n = n.multiply(BigInteger.valueOf(3));
                n = n.add(BigInteger.ONE);
                System.out.println(n);
                k++;
            }
            else {
                n = n.divide(BigInteger.valueOf(2));
                System.out.println(n);
                k++;
            }
        }
        System.out.print("It took " + k + " iterations!");
    }
}