为什么我的 C++ 算法不能处理超过 62 位的整数？

Question

我在玩 C++ 并决定编写算法，使给定整数的 return 位长度。在解决了一些不相关的问题后，它终于奏效了。这是我的代码：

#include <iostream>

using namespace std;

long long int ipow(int x,int n)
{
    if (n==0)   return 1;
    if (n%2!=0) return x*ipow(x,((n-1)/2))*ipow(x,((n-1)/2));
    return      ipow(x,n/2)*ipow(x,n/2);
}

int bits(long long int n)
{
    if (n==0 || n==1) return 1;
    int i=1;
    while (n>ipow(2,i+1)-1) i++;
    return i+1;
}

int main()
{
    long long int n;
    cin>>n;
    cout<<bits(n)<<endl;
}

我用越来越大的数字对它进行了测试，发现了一个有趣的事实——程序对于大多数整数来说都非常快，甚至更大（50-60 位长），但卡在高 CPU 负载和几分钟内没有显示任何数字 "a little" 更大的内容。

我稍微修改了代码以找到突破点，发现我的程序可以处理的最后一个整数是 4611686018427387903。我在 Wolfram Alpha 上查了一下，发现它等于 2^63-1，这意味着它是最大的 62 位数字。

这就是我的问题 - 这可能很愚蠢 - 为什么是 62 位？据我了解，long long int 可以容纳 64 位变量，我的 CPU 也可以处理 64 位整数。那么为什么 64 位不是限制？

-Mateusz Duchalski

PS 我在 Windows 10 64 位 Intel Core i5-4570 Haswell CPU 上使用 Code::Blocks 和最新稳定的 MinGW 运行 ].

Answer 1

因为 1 位是符号位，所以剩下 63 "useful" 位..你的算法试图找到一个大于你输入数字的 2 的幂，所以你的最大输入数字只能是 62 位，这样你的 2 的幂可以高 1 到 63 位。

为什么我的 C++ 算法不能处理超过 62 位的整数？

Why can't my C++ algorithm handle integers more than 62 bits?

c++

algorithm

integer

long-integer