java - 修复递归求幂方法？

Question

我目前正在研究一种使用递归进行求幂计算的方法。这是我到目前为止所拥有的:

public static long exponentiation(long x, int n) {

    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return x;
        // i know this doesn't work since im returning long
    } else if (n < 0) {
        return  (1 / exponentiation(x, -n));
    } else {
        //do if exponent is even
        if (n % 2 == 0) {
            return (exponentiation(x * x, n / 2));
        } else {
            // do if exponent is odd
            return x * exponentiation(x, n - 1);
        }
    }
}

我有两个问题。第一个问题是我不能做负指数，这不是一个主要问题，因为我不需要做负指数。第二个问题是某些计算给了我错误的答案。例如 2^63 给了我正确的值，但它给了我一个负数。 2^64 及以上就给我 0。我有办法解决这个问题吗？我知道我可以将 long 切换为 double 并且我的方法将完美运行。然而，我的教授要求我们使用long。感谢您的帮助!

Answer 1

long 可以表示的最大值是 2^63 -1。所以如果你计算 2^63，它比 long 可以容纳和环绕的东西还要大。长整型使用 twos-complement 表示.

仅仅将 long 更改为 double 并不完全有效。它改变了方法的语义。 float 的精度有限。使用 64 位 float ，您仍然只能表示与 64 位整数相同数量的数字。它们只是分布不同。 long 可以表示 -2^63 和 2^63-1 之间的每个整数。 double 也可以表示数字的分数，但在数字很大时，它甚至无法表示每个数字。

例如，在 1000000000000000000000000000000000000000000000000000 之后可以表示的下一个 double 是 100000000000000030000000000000000000000000000000000 - 所以你是任务是一个巨大的30000000000000000000000000000000000，你无法用 double 来表示。

您正在尝试修复一些您不应该费心去修复的东西。使用 long，您的方法可能返回一个固定的最大返回值。您的方法应该清楚地说明如果溢出会发生什么，并且您可能想要处理此类溢出(例如使用 Math#multiplyExactly )，但如果 long 是您应该返回的返回值，那么那就是你应该使用什么。