java - 反转非常大的整数的最省时的算法/代码是什么？

Question

我正在尝试获得最有效的算法来反转 Java 中的大整数。 例如。如果我们必须反转 301324354432。

到目前为止，我有以下代码:

public int reverse(int x) {
        int result = 0;
        while (x != 0)
        {
            int tail = x % 10;
            int newResult = result * 10 + tail;
            if ((newResult - tail) / 10 != result)
            { return 0; }
            result = newResult;
            x = x / 10;
        }
        return result;
    }

实现此最佳时间复杂度的正确算法是什么？

Answer 1

一种有效的方法是如下所示(类似于您的建议)。

public static long reverse(long x) {
    long y = 0;
    while(x > 0) {
        y = y * 10 + x % 10;
        x = x / 10;
    }
    return y;
}

这避免了昂贵的字符串转换，只进行一次数字传递并且不使用任何内存(存储结果除外)。

编辑

避免除法和模运算的更有效方法是:

public static long reverse(int _x) {
    long x = _x;
    long y = 0;
    while (x > 0) {
        y = x + (y - ((x * 0x1999999Al) >> 32)) * 10; //y * 10 + x - (x/10) * 10;
        x = ((x * 0x1999999Al) >> 32);
    }
    return y;
}

我还尝试使用移位运算 (x * 10 = (x << 3) + (x << 1)) 将乘法替换为 10，但它似乎并未影响性能。 最佳答案of this stackoverflow question展示了如何快速除以 10。为了完整起见，提供的答案说明可以按以下方式完成(归功于 John Källén)

int32_t div10(int32_t dividend) {
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

这种方法只允许反转整数(最多 2^31 - 1 )。结果很长，如2^31 - 1 = 2147483647和 reverse(2147483647) = 7463847412 > 2^31 - 1 . 对 x 执行模 10 运算的快速方法就是将它除以并乘以 10，然后从 x 中减去该结果.