关于左移位运算超过数字范围的坑

· · 个人记录

CSP2020提高组T2，洛谷题号P7076动物园，有一个同学不管怎么做都是95分。

这个同学程序里面有如下一段：

//if(ans==64){
//  cout<<18446744073709551615ull+1-n<<endl;
//  return 0;
//}
unsigned long long ans1=(1ull<<ans)-n;
cout<<ans1<<endl;

如果ans是64的话，就会出错。但是如果用注释里面的代码特判一下ans是64的情况，就可以AC，本地windows电脑试了都没问题。

怀疑是windows系统和linux系统不一样导致的，回到家用苹果试了一下如下的程序：

#include <iostream>
using namespace std;
typedef unsigned long long ull;
int main(){
    cout<<(1ull<<64ull)-1<<endl;
    cout<<(1ull<<64)-1<<endl;
    cout<<(1ull<<63)*2-1<<endl;
    cout<<0ull-1<<endl;
    cout<<(1ull<<63ull)-1<<endl;
    cout<<(1ull<<63)-1<<endl;
    return 0;
}

输出结果是：

140732682357592
73896
18446744073709551615
18446744073709551615
9223372036854775807
9223372036854775807

结合在网上查的资料，可以大概确定几个事情。

左移位运算，如果移位的位数超过或者等于类型本身的位数，行为是未定义的，在不同系统上，结果可能不一样。比如前两个例子里面，因为unsigned long long类型的长度是64位，所以左移64位的答案，变得非常诡异。

但是左移63位，再乘以2，就会得到正确的2^{64}这个结果，当然在unsigned long long类型下，这个结果溢出为0了，不过用它减一，还是能得到unsigned long long的最大值2^{64}-1

其实用0表示2^{64}是没问题的，直接自然溢出啥事没有