java - 为什么除以两个整数的对数算法在某些特殊测试用例中失败？

Question

我尝试使用公式 a/b = e^(ln a - ln b) 来解决臭名昭著的 Divide 2 Integers 而没有使用/% * 的问题，但是对于某些测试用例 (dividend=Integer.MAX_VALUE or MIN_VALUE and divisor=1) 我的解决方案失败了。

为什么会失败？

[编辑]:我得到的那个测试用例的答案是(MAX-1 or MIN+1)。我想知道为什么会这样。

public int divide(int dividend, int divisor) {
    boolean neg = false;
    if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
        neg = true;

    long a = dividend;
    a = Math.abs(a);
    long b = divisor;
    b = Math.abs(b);

    double res = Math.pow(Math.E, Math.log(a) - Math.log(b));
    int ans = Math.floor(res);
    return neg ? -ans : ans;
}

Answer 1

这里问题的根源在于计算的中间结果。

Double 是一种浮点类型，当您使用它时，您可能会失去精度。

您在中间计算中使用了 double:

double res = Math.pow(Math.E, Math.log(a) - Math.log(b));
int ans = Math.floor(res);

例如，如果您使用 5 和 1，res = 4.999999999999，Math.floor(res) 将返回 4。

使用 Integer.MAX_VALUE 你有 2147483647(原始值)，但结果是 2147483646。原因与 5 完全相同。