Java 和 CPP 的不同输出

Question

我正在解决 Nth root of M 问题，我用 Java 解决了它，这是解决方案：

    public int NthRoot(int n, int m)
    {
        // code here
        int ans = -1;
        if (m == 0)
            return ans;
        if (n == 1 || n == 0)
            return m;
        if (m == 1)
            return 1;
        int low = 1;
        int high = m;
        while (low < high) {
            
            int mid = (low + high) / 2;
            int pow = (int)Math.pow(mid, n);
            if (pow == m) {
                
                ans = mid;
                break;
            }
            if (pow > m) {
                
                high = mid;
            } else {
                
                low = mid + 1;
            }
        }
        
        return ans;
    }

它通过了所有的测试用例。但是，当我使用 C++ 解决它时，一些测试用例没有通过。这是 C++ 解决方案：

    int NthRoot(int n, int m)
    {
        // Code here.
        int ans = -1;
        if (m == 0)
            return ans;
        if (n == 1 || n == 0)
            return m;
        if (m == 1)
            return 1;
        int low = 1;
        int high = m;
        while (low < high) {
            
            int mid = (low + high) / 2;
            int po = (int)pow(mid, n);
            if (po == m) {
                
                ans = (int)mid;
                break;
            }
            if (po > m) {
                
                high = mid;
            } else {
                
                low = mid + 1;
            }
        }
        
        return ans;
    }

它没有通过的测试用例之一是：

6 4096
Java's output is 4 (Expected result)
C++'s output is -1 (Incorrect result)

当我用纸和笔描绘它时，我得到了与Java相同的解决方案。

但是，当我在 C++ 代码中使用 long long int 时，它工作正常——但是 Java 和 C++ 中 Int/int 的大小是一样吧？（当我在 C++ 和 Java 中打印 INT_MAX 和 Integer.MAX_VALUE 时，它输出相同的值。）

Answer 1

正如您可能已经猜到的那样，问题是由于尝试将 double 值转换为 int 值时，当该源大于 [= 的最大可表示值时12=]。更具体地说，它涉及 Java 和 C++ 在 while 循环开始附近处理转换的方式的区别：int po = (int)pow(mid, n);.

对于您的示例输入 (6 4096)，pow 函数在第一个运行循环中返回的值是 7.3787e+19，这太大了对于 int 值。在 Java 中，当您尝试将过大的值转换为整数时，结果是整数类型可表示的最大值，如 this answer 中指定（加粗我的）：

The value must be too large (a positive value of large magnitude or positive infinity), and the result of the first step is the largest representable value of type int or long.

但是，在 C++ 中，当源值超过 INT_MAX 时，行为未定义（根据此 C++11 Draft Standard）：

7.10 Floating-integral conversions [conv.fpint]

¹ A prvalue of a floating-point type can be converted to a prvalue of an integer type. The conversion truncates; that is, the fractional part is discarded. The behavior is undefined if the truncated value cannot be represented in the destination type.

然而，尽管形式上未定义，many/most compilers/platforms 将在发生这种情况时应用 'rollover'，从而导致非常大的负数值（通常，INT_MIN) 作为结果。这就是 Visual Studio 中的 MSVC 所做的，给出 -2147483648 的值，从而导致 else 块变为运行 … 并且 keep 运行ning 直到 while 循环达到其终止条件——此时 ans 将永远不会被分配任何值，除了初始 -1.

您可以通过检查 pow 调用返回的 double 并将 po 设置为 INT_MAX（如果合适）来模拟 Java 行为：

    while (low < high) {
        int mid = (low + high) / 2;
        double fpo = pow(mid, n);
        int po = (int)(fpo);
        if (fpo > INT_MAX) po = INT_MAX; // Emulate Java for overflow
        if (po == m) {
            ans = (int)mid;
            break;
        }
        if (po > m) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }

Java 和 CPP 的不同输出

Different outputs for Java and CPP

c++

java

algorithm

binary-search

7.10 Floating-integral conversions [conv.fpint]