What is the most time efficient algorithm/code to reverse a very large integer?

Question

I am trying to get the most efficient algorithm to reverse a large integer in Java. E.g. if we have to reverse 301324354432.

Till now I have the below code:

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;
    }

What is the correct algorithm to achieve this at best time complexity?

O-notation isn't really helpful here, because if you're talking about int, then n ≤ 11 (and that includes the minus sign). For longs, n ≤ 64. For all practical purposes, you can think of this as O(1). (Yes, it does technically vary on the number of digits -- but there's still a constant upper bound, since there's a constant upper bound on the number of digits. And what's more, that upper bound is small enough that it's actually meaningful.) — yshavit, Jul 20 '16 at 18:26
How about this : `new StringBuilder( String.valueOf(x) ).reverse().toString() ` ? — SomeDude, Jul 20 '16 at 18:34
Your code is already fine, and quite a lot better (more efficient) than most of the answers you're getting involving string manipulation. — Paul Hankin, Jul 21 '16 at 01:35
I ran a benchmark -- reversing all the ints up to 100 million. George's variant of your code that removes the inner check for overflow runs in 1.3sec, your code in 2sec, and the StringBuffer solution in 6s. I couldn't get the collectors/lambda solution to compile (I think there's something wrong with my java8 installation), but I expect it'll be even slower. — Paul Hankin, Jul 21 '16 at 01:58
Yeah you are right. I already had this solution with me, but I was looking for a more efficient algo than the one @George has posted. maybe using bitwise operators, if any? — sagnikdas, Jul 21 '16 at 11:16
@sagnikDas I updated my answer and replaced division and modulo using multiplication, bitshifts and subtraction/addition. The resulting code is about twice as fast on my laptop. — George, Jul 21 '16 at 12:29
You should be more specific. You're reversing the digits in the base-10 representation of an integer. "Reverse an integer" can also mean, among other things, reversing the order of bits, which is a much different thing. — Jim Mischel, Jul 21 '16 at 14:20

score 3 · Answer 1 · edited May 23 '17 at 12:08

An efficient way is to do it as shown below (similar to what you suggested).

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

This avoids expensive string conversions, does only one pass through the digits and does not use any memory (except for storing the result).

EDIT

A more efficient way, avoiding division and modulo operations is:

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;
}

I also tried replacing multiplication by 10 using bitshift operations (x * 10 = (x << 3) + (x << 1)) but it didn't seem to affect performance. The top answer of this stackoverflow question shows how to divide fast by 10. For completeness, the answer provided states that it can be done as follows (credit to John Källén)

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

This approach only allows to reverse an integer number (up to 2^31 - 1). The result is a long, as 2^31 - 1 = 2147483647 and reverse(2147483647) = 7463847412 > 2^31 - 1. A fast way to perform a modulo 10 operation on x is to divide and multiply it by 10, and then subtract that result from x.

This is awesome. But can you please elaborate what is 0x1999999A? I couldn't figure this. What if, I want to divide x by 5 for some other problem statement; What will be this value? — sagnikdas, Jul 21 '16 at 19:35
As stated in the linked question, 0x1999999A is approximately equal to 1/10 * 2^32. Multiplying the value by that and then dividing by 2^32 gives the desired output. — George, Jul 21 '16 at 21:38

score 1 · Answer 2 · answered Jul 20 '16 at 18:24

1

    public int reverse(int x) {
        int result = 0;

        StringBuffer sb = new StringBuffer(0);
        sb.append(x);

        result = Integer.parseInt(sb.reverse().toString());


        return result;
    }

answered Jul 20 '16 at 18:24

Grayson

591
1
4
17

score 0 · Answer 3 · answered Jul 20 '16 at 19:01

You can take advantage of Java lambda expression. All you have to do is convert the number to String, use lambda to reverse it and then convert back to int. A little variation of this code can allow the reversal of any number of characters. Here:

public static int reversal(int x) {
      String tmp =  String.valueOf( x );
      String result = Pattern.compile(" +").splitAsStream( tmp ).map(word->new StringBuilder(word).reverse())
      .collect(Collectors.joining(" "));
      return Integer.parseInt( result );
}

What is the most time efficient algorithm/code to reverse a very large integer?

3 Answers3