时间戳

首页 > 解决方案 > 为什么使用的数据类型为“long long int”与“int”相比，运行时间存在差异？

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

问题描述

我正在编写一个涉及输入范围高达 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;
}

标签： ctypes

解决方案

您正在计算Collat​​z 猜想。n对于作为输入的某些数字， m' 可能会变得非常大。如果m大于 2 31，使用正常的 int，你会得到一个负数。更明确地说：当m>= 2 31和m< 2 32时，带符号的 32 位值将被解释为负数：计算机在仅使用 32 位时看不到这种差异。

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

第一次大于m2 31是为n=113383wherereach m。2482111348

进一步澄清：问题不在于以下循环，n而m在于以下循环。

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

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

推荐阅读