매우 큰 정수를 뒤집을 수있는 가장 효율적인 알고리즘/코드는 무엇입니까?

Question

자바에서 큰 정수를 뒤집을 수있는 가장 효율적인 알고리즘을 얻으려고합니다. 예.

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

가장 좋은 시간 복잡성에이를 올바른 알고리즘은 무엇인가 : 우리가 지금까지 301324354432.

를 반전해야하는 경우 나는 아래의 코드가?

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

Answer 2

효과적인 방법은 아래에 표시된 것처럼 (사용자가 제안한 것과 유사하게) 수행하는 것입니다.

이렇게하면 값 비싼 문자열 변환을 피할 수 있고 숫자 만 통과하고 메모리를 사용하지 않습니다 (결과 저장 제외).

편집

더 효율적인 방법은, 분열을 피하고 작업을 모듈로 것은 :

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)를) bitshift 사용 10 곱셈을 교체 시도했지만가 보이지 않았다 성능에 영향을 미칩니다. 최고 대답 of this stackoverflow question 최대 ((John Källén에 신용)

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

이 방법은 정수 역 수를 다음과 같이 답변을 제공하는 국가가 그것을 할 수있는 완성도를 들어 (10)에 의해 빠르게 분할하는 방법을 보여줍니다 ~ 2^31 - 1). 결과는 2^31 - 1 = 2147483647 및 reverse(2147483647) = 7463847412 > 2^31 - 1과 같이 길다. x에서 모듈로 10 연산을 수행하는 가장 빠른 방법은 그것을 나누고 10을 곱한 다음 그 결과를 x에서 뺍니다.

Answer 3

Java 람다 식을 활용할 수 있습니다. 당신이해야 할 일은 문자열을 숫자로 변환하고, 람다를 사용하여 그것을 뒤집은 다음 int로 다시 변환하는 것입니다. 이 코드의 약간의 변형은 임의의 문자 수의 역전을 허용 할 수 있습니다. 여기 :

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