c - 为什么使用的数据类型为 'long long int' 与 'int' 时运行时间存在差异？

Question

我正在编写一个程序，涉及输入范围高达 100 万个，当我使用数据类型“int”来处理我的值时，运行时间非常非常长，程序从未完全执行本身，所以我没有能够记下运行时间。 之前的代码；

#include<stdio.h>
int main()
{       
    int n,m,i,maxt=0,maxn;

    for(n=2;n<=1000000;n++){
        m=n;
        i=0;
        for(i=0;m!=1;i++){
            if(m%2==0)
                m=m/2;
            else
                m=(3*m+1);
        }

        if(i>maxt){
            maxt=i;
            maxn=n;
        }
    }

    printf("%d%d",maxn,maxt);

    return 0;
}

但是在处理代码时，我将数据类型从“int”更改为“long long int”，令人惊讶的是运行时间大幅减少(毫秒)，任何人都可以解释这背后的原因是什么？ 之后的代码；

#include<stdio.h>
int main()
{       
    long long int n,m,i,maxt=0,maxn;

    for(n=2;n<=1000000;n++){
        m=n;
        i=0;
        for(i=0;m!=1;i++){
            if(m%2==0)
                m=m/2;
            else
                m=(3*m+1);
        }

        if(i>maxt){
            maxt=i;
            maxn=n;
        }
    }

    printf("%lld%lld",maxn,maxt);

    return 0;
}

Answer 1

您正在计算 Collatz conjecture 。对于某些数字 n 作为输入，m 可能会变得非常大。如果 m 大于 2³¹，对于普通 int，您会得到一个负数。更明确地说:当 m >= 2³¹ 且 m < 2³² 时，为带符号的 32 位值将被解释为负数:计算机在仅使用 32 位时看不到这种差异。

m 的负数会陷入无限循环，永远不会达到 m == 1 结束条件。因此，需要64位的int类型。在维基百科页面上，显示了负数之间的 3 个不同的循环，例如 m=-1 变为 m=-2 ，再次变为 m=-1 处于永无止境的循环中。

m 第一次大于 2³¹ 是 n=113383，其中 m 达到 2482111348。

进一步澄清:问题不在于 n，而是在于以下循环中的 m。

    m=n;
    for(i=0;m!=1;i++){
        if(m%2==0)
            m=m/2;
        else
            m=(3*m+1);
    }

对于每个n，此循环会执行多次。 m 首先获取n 的值，例如 113383。在这种情况下，经过 120 步，m 达到 2482111348，这个值太大了它不再适合 32 位有符号整数。在大多数现代处理器上，2482111348 的表示形式与 -1812855948 相同。现在，循环继续以负值继续。一段时间后，它陷入无限循环，始终重复相同的 18 个数字 -17、-50、-25、...、-34、-17。并且永远不会达到停止 for 循环所需的条件 m==1。