使用不同数据类型的运行时 C++ 的差异

Question

好的，所以我正在为学校做一个小项目，但我无法在任何地方找到答案，为什么代码中的这个小改动使它在数字 m[=20= 时立即完成] 越来越高。看变量“k”我把它从int改成了long.

我试图在 Collat​​z 序列中找到 1 到 1000000 之间的最长序列

void lengstaRuna() {

    cout << "Hæsta tala?:";
    int m;
    cin >> m;

    int lengstaRuna = 0;
    int talaLengstuRunu = 0;
    int k;

    for(int i = 2; i < m; i++) {
        int lengd = 1;
        k = i;

        while(k != 1) {
            if(k % 2 == 0) {
                k = k/2;
            } else {
                k = k*3 +1;
            }
            lengd++;
        }

        if(lengd > lengstaRuna) {
            lengstaRuna = lengd;
            talaLengstuRunu = i;
        }
    }

    cout << "Lengsta runa: " << lengstaRuna << endl;
    cout << "Tala lengstu runu: " << talaLengstuRunu << endl;

}



void lengstaRuna() {

    cout << "Hæsta tala?:";
    int m;
    cin >> m;

    int lengstaRuna = 0;
    int talaLengstuRunu = 0;
    long k;

    for(int i = 2; i < m; i++) {
        int lengd = 1;
        k = i;

        while(k != 1) {
            if(k % 2 == 0) {
                k = k/2;
            } else {
                k = k*3 +1;
            }
            lengd++;
        }

        if(lengd > lengstaRuna) {
            lengstaRuna = lengd;
            talaLengstuRunu = i;
        }
    }

    cout << "Lengsta runa: " << lengstaRuna << endl;
    cout << "Tala lengstu runu: " << talaLengstuRunu << endl;

}

问题很简单：为什么输入米==1000000运行那么快？

Answer 1

我明白这里发生了什么。基本上，当您的输入超过某个值时，int 会溢出，因为您正在执行 k*3。

我修改了你的代码来检查这个（见下文）。直到大约 113000 的输入值，您的 'k' 必须保持的最大值为 1570824735（接近 INT_MAX 2147483647）。任何 114000 或以上的值，'k' 都会溢出，代码会进入未知领域。当然，当你使用 long 时，这个问题就不会发生。

./a.out 113000
j: 1570824735
Lengsta runa: 354
Tala lengstu runu: 106239

#include <iostream>
#include <string>
using namespace std;
void lengstaRuna(int m) {


    int lengstaRuna = 0;
    int talaLengstuRunu = 0;
    int k;
    long j = 0;

    for(int i = 2; i < m; i++) {
        int lengd = 1;
        k = i;

        while(k != 1) {
            if(k % 2 == 0) {
                k = k/2;
            } else {
                if (k*3 > j)
                    j = k*3;
                k = k*3 +1;
            }
            lengd++;
        }

        if(lengd > lengstaRuna) {
            lengstaRuna = lengd;
            talaLengstuRunu = i;
        }
    }
            cout << "j: " << j << endl;

    cout << "Lengsta runa: " << lengstaRuna << endl;
    cout << "Tala lengstu runu: " << talaLengstuRunu << endl;

}
int main (int ac, char** av) {
    std::string::size_type sz; 
lengstaRuna(std::stoi(av[1]));
}