C++中pow(2,n)-1在n=62时减法不生效问题及正确写法咨询

问题根因 #

• C++标准库的pow是浮点运算函数，返回值为double类型，而非整数类型。double仅提供53位二进制有效尾数精度，大于2^53的整数无法保证全部可被精确表示。
• 单一行代码出错的原因：n=62时pow(2,62)本身是2的整数次幂，可被double精确存储，但后续的-1操作在浮点运算域执行：2^{62的最高有效位是第62位，远高于`double`的53位精度上限，2}62减1的结果无法被double精确表示，会被自动舍入回2^62，最终赋值给long long的结果就是错误的2^{62，而非预期的2}62-1。
• 拆分两行后正常运行的原因：第一步直接将可被double精确表示的pow(2,62)转换为long long类型，64位有符号long long具备完整的63位有效整数位，可精确存储2^{62。后续的`-1`操作在**64位整数运算域**执行，没有精度损失，自然可以得到正确的2}62-1。

正确实现方式 #

不要用浮点函数pow处理整数幂运算，直接用整数位运算实现即可，全程无精度损失：

// n小于63时用有符号64位整数
long long int total = (1LL << n) - 1;

// n可能大于等于63时用无符号64位整数避免溢出
unsigned long long int total = (1ULL << n) - 1;

内容的提问来源于stack exchange，提问作者StrugglingCollegeStudent