c++ - 为什么此递归算法在输入2147483647上给出错误的答案？

我正在研究以下问题:



这是我想出的代码:

class Solution {
private:
    unordered_map<int, long long> count_num;
public:
    int integerReplacement(int n) {
        count_num[1] = 0;count_num[2] = 1;count_num[3] = 2;
        if(!count_num.count(n)){
            if(n%2){
                count_num[n] = min( integerReplacement((n-1)/2), integerReplacement((n+1)/2) )+2;
            }else{
                count_num[n] = integerReplacement(n/2) +1;
            }
        }
        return(count_num[n]);
    }
};

当输入为2147483647时，我的代码错误地输出了33，而不是正确的答案32。为什么我的代码在这里给出了错误的答案？

最佳答案

我怀疑这是整数溢出。列出的数字(2,147,483,647)是可以容纳到int中的最大可能值，假设您使用的是带符号的32位整数，因此，如果将其加一个，则会溢出到INT_MIN中，即−2,147,483,648 。从那里开始，您会得到错误的答案就不足为奇了，因为此值不是您期望得到的。

溢出特别是在您计算时发生

integerReplacement((n+1)/2)

因此，您需要解决这种情况才能计算(n + 1)/ 2而不会发生溢出。这是一个极端的极端情况，所以对于它的代码跳起来我并不感到惊讶。

一种执行此操作的方法是注意，如果n为奇数，则(n + 1)/ 2等于(n / 2)+1(带整数除法)。所以也许您可以将其重写为

integerReplacement((n / 2) + 1)

计算相同的值，但没有溢出。