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 完全相同。