C++实现Max Pairwise Product出现integer overflow的修复方法

问题描述 #

实现Max Pairwise Product（最大两两乘积）算法时，测试输入为900000、100000时触发整数溢出异常，已将存储乘积的product、result变量声明为long long类型仍无法解决，原始实现代码如下：

#include<algorithm>
#include <iostream>
#include<vector>
using namespace std;

long long MaxPairwise(const std::vector<int>& nums){
    long long product = 0;
    int n;
    n=nums.size();
    int index1=-1;
    for(int i=0;i<n;i++){
        if(index1==-1  || nums[index1]<nums[i]){
            index1=i;
        }
       
    }
    int index2=-1;
    for(int j=0;j<n;j++){
        if(index1!=j && nums[index2]<nums[j]){
            index2=j;
        }
        
    }
    product=nums[index2]*nums[index1];
    return ((long long)(product));
}

int main()
{
    int n;
    cin>>n;
     std::vector<int> nums(n);
    for(int i=0;i<n;i++){
        std::cin>>nums[i];
    }
    long long result;
    result= MaxPairwise(nums);
    cout<<result<<'\n';
    
    return 0;
}

溢出根本诱因 #

C++的算术表达式求值时，结果类型由参与运算的操作数本身类型决定，和最终赋值的目标变量类型无关：

• 代码中nums存储的元素类型为int，nums[index1]、nums[index2]均为32位int类型，二者执行乘法运算时，会先得到int类型的中间结果
• 测试用例中两个数的乘积为900000 * 100000 = 90000000000，远超过32位有符号int的上限2147483647，这一步乘法就已经触发整数溢出，得到错误的中间值
• 后续把溢出的错误int值转换为long long赋值给product，只是把错误值转成了64位格式，无法得到正确计算结果
• 代码末尾return ((long long)(product));的强转操作同样没有意义，无法回溯修正乘法阶段已经发生的溢出

另外代码还存在一个逻辑漏洞：查找第二大值时，初始index2=-1，判断条件没有处理初始状态，第一次循环就会访问nums[-1]触发越界，属于未定义行为，同时当数组首元素为最大值时，第二大值的查找逻辑也会异常。

修复方法 #

• 调整乘法运算逻辑：在执行乘法前，先将至少一个乘数显式转换为long long类型，引导整个乘法运算以64位精度执行，从根源避免溢出
• 补全第二大值查找的边界判断，修复初始状态下的越界和逻辑错误

修复后的完整代码如下：

#include<algorithm>
#include <iostream>
#include<vector>
using namespace std;

long long MaxPairwise(const std::vector<int>& nums){
    int n = nums.size();
    int index1 = -1;
    for(int i = 0; i < n; i++){
        if(index1 == -1  || nums[index1] < nums[i]){
            index1 = i;
        }
    }
    int index2 = -1;
    for(int j = 0; j < n; j++){
        // 补充index2为-1的初始场景判断，避免越界
        if(j != index1 && (index2 == -1 || nums[index2] < nums[j])){
            index2 = j;
        }
    }
    // 先将一个乘数转为long long再做乘法，避免int阶段溢出
    long long product = (long long)nums[index1] * nums[index2];
    return product;
}

int main()
{
    int n;
    cin >> n;
    std::vector<int> nums(n);
    for(int i = 0; i < n; i++){
        std::cin >> nums[i];
    }
    long long result = MaxPairwise(nums);
    cout << result << '\n';
    
    return 0;
}

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