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 It took 8 iterations!

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

191184382 95592191 286776574 143388287 430164862 215082431 645247294 322623647 967870942 483935471 1451806414 725903207 -2117257674 -1058628837 It took 14 iterations!

出了什么问题？为什么？我该如何解决？谢谢!

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