如何用C++实现印度国王棋盘麦粒倍增问题的计算并避免大数溢出？

印度国王棋盘麦粒倍增问题中，第n格放置2^(n-1)粒麦子，64格总数为2^64-1（即18446744073709551615）。在C++中避免大数溢出的核心方法是选择合适的数据类型或实现高精度运算。

方法一：使用无符号64位整型

unsigned long long 的最大值为 2^64-1，恰好能容纳总和。但累加过程中若使用有符号 long long 会在最后一格溢出，因此必须全程使用无符号类型。

#include <iostream>
int main() {
    unsigned long long total = 0;
    unsigned long long grains = 1;
    for (int i = 0; i < 64; ++i) {
        total += grains;
        grains *= 2;
    }
    std::cout << "总麦粒数: " << total << std::endl;
    return 0;
}

方法二：字符串模拟大数加法

若格子数超过64或需要更高精度，需用字符串或数组按位模拟加法与乘法，从根本上消除硬件位数限制导致的溢出。

判断依据

• 目标最大值是否小于等于 UINT64_MAX：若是，用 unsigned long long；否则用大数类。
• 中间变量是否可能越界：每次翻倍前检查当前值是否已超过类型上限的一半。

适用条件

• 方法一适用于标准64格棋盘且编译器支持C++11及以上标准。
• 方法二适用于任意格数的扩展计算场景。

常见误区

1. 使用 int 或 long：在多数平台上仅32位，第31格即溢出。
2. 使用有符号 long long：第64格翻倍时发生未定义行为（有符号溢出）。
3. 忽略累加和的溢出：单格数值未溢出，但总和可能超出类型上限。