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

Question

我正在玩C++并决定编写将返回给定整数的位长度的算法.在解决了一些不相关的问题后,它终于奏效了.这是我的代码:

#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小"更大.

我修改了一点代码以找到断点并发现我的程序可以处理的最后一个整数是4611686018427387903.我在Wolfram Alpha上查找它并发现它等于2 ^ 63-1,这意味着它是最大的62位数.

里斯我的问题 - 它可能是愚蠢的 - 为什么62位？据我所知,long long int可以容纳64位变量,我的CPU也可以处理64位整数.那么为什么不是64位的限制呢？

-Mateusz Duchalski

PS我正在使用Code :: Blocks与最新稳定的MinGW在Windows 10 64位上运行,由Intel Core i5-4570 Haswell CPU驱动.

Answer 1

因为1位是符号位,所以留下63个"有用"位..并且你的算法试图找到大于输入数的2的幂,所以你的最大输入数字只能是62位,所以你的2的幂可以高1到63位.