시작하며

Leetcode 190. Reverse Bits 문제를 풀면서 Java에서의 int to binary , binary to int 처리와 관련하여 궁금한 부분이 생겨서 정리하게 되었습니다.

 

Integer.parseInt(String s, int radix)

 

자바에서는 Integer 클래스의 parseInt() 메서드로 2진수를 10진수로 쉽게 변환할 수 있습니다.

파라미터로 [param1] String 타입의 binary와 [param2] int 타입의 진수 값(= radix, 몇 진수인지)를 넣어주면 됩니다.

  • param1(String s) : "11111111111111111111111111111101”
  • param2(int radix) : 2

 

unsigned 타입을 지원하지 않는 Java

 

하지만 사용 시 주의해야 할 점이 있습니다.

int n = Integer.parseInt("11111111111111111111111111111101", 2);

 

위와 같은 코드를 작성하게 되면 NumberFormatException 에러가 발생합니다.

java.lang.NumberFormatException: For input string: "10111111111111111111111111111111" under radix 2 
at line 67, java.base/java.lang.NumberFormatException.forInputString

 

이유는 Java에서 기본적으로 unsigned 타입을 지원하지 않기 때문입니다.

(Java의 primitive 타입은 단순하게 signed 타입만 지원합니다.)

 

 

Integer.parseInt() 메서드의 일부를 살펴보면

boolean negative = false;
int i = 0, len = s.length();
int limit = -Integer.MAX_VALUE; // -2,147,483,647

if (len > 0) {
    char firstChar = s.charAt(0);
    if (firstChar < '0') { // Possible leading "+" or "-"
        if (firstChar == '-') {
            negative = true;
            limit = Integer.MIN_VALUE; // -2,147,483,648
        } else if (firstChar != '+') {
            throw NumberFormatException.forInputString(s, radix);
        }

        if (len == 1) { // Cannot have lone "+" or "-"
            throw NumberFormatException.forInputString(s, radix);
        }
        i++;
    }
    int multmin = limit / radix;
    int result = 0;
    while (i < len) {
        // Accumulating negatively avoids surprises near MAX_VALUE
        int digit = Character.digit(s.charAt(i++), radix);
        if (digit < 0 || result < multmin) {
            throw NumberFormatException.forInputString(s, radix);
        }
        result *= radix;
        if (result < limit + digit) {
            throw NumberFormatException.forInputString(s, radix);
        }
        result -= digit;
    }
    return negative ? result : -result;
} else {
    throw NumberFormatException.forInputString(s, radix);
}
  • 내부 로직에 따라 "11111111111111111111111111111101" binary string이 while문 안에서 signed int 값의 범위를 벗어나게 되어 예외가 발생하게 됩니다.
  • 구체적으로
    • while 루프 내에서 숫자를 누적(= 음수 누적)하여 계산하는데,
    • 곱셈과 뺄셈을 하기 전에 미리 overflow 검사를 하여 signed int 범위를 초과할 경우 NumberFormatException을 던지고 있습니다.
    • overflow 검사는 [곱셈]의 경우 [result < multmin] 조건으로, [뺄셈]의 경우 [result < limit + digit] 조건으로 수행하는데 풀어서 설명하면 각 조건의 의미는 다음과 같습니다.
    • [곱셈] result < multmin
      • multmin = limit / radix; 이므로 결국 result < limit / radix 
      • 양 변에 radix를 곱하면 result * radix < limit
      • 즉, 곱한 값(result * radix)이 limit을 넘어서면 NumberFormatException 예외 발생
    • [뺄셈] result < limit + digit 
      • 양 변에 digit을 빼면 result - digit < limit
      • 즉, 뺀 값(reulst - digit)이 limit을 넘어서면 NumberFormatException 예외 발생
  • signed int 와 unsigned int의 범위는 아래와 같습니다.
    • signed int 범위 : -2,147,483,648 ~ 2,147,483,647
    • unsigned int 범위 : 0 ~ 4,294,967,295
  • 결론적으로, binary string "11111111111111111111111111111101"는 "4294967293"를 향하여 값이 변환(누적)되었고, 해당 값은 signed int로는 표현할 수 없는(= signed int 범위에서 벗어나는) 값이어서 예외가 발생한 것입니다.

디버깅 화면. 32번째 계산에서 범위를 벗어나 예외 처리됩니다.

 

 

 

Java에는 unsigned int가 없는데 해당 binary string을 어떻게 처리할까? : parseUnsignedInt()

 

Java 8 버전 이후에서는 "11111111111111111111111111111101"와 같이 signed int 범위를 벗어나는 binary 값을 처리할 수 있도록  unsigned Integer API를 제공합니다.

parseUnsignedInt() 메서드를 사용하면 해당 binary string도 정상적으로 parsing이 됩니다. 하지만 막상 parsing된 값을 출력해보면 (2의 보수 계산을 통한) signed int 값이 출력되는데요.

int n = Integer.parseUnsignedInt("11111111111111111111111111111101", 2);
System.out.println(n); // -3

 

추가적으로 toUnsignedString() 메서드를 사용하면 unsigned int에 해당하는 값을 String 타입으로 출력할 수 있습니다.

int n = Integer.parseUnsignedInt("11111111111111111111111111111101", 2);
String unsignedString = Integer.toUnsignedString(n); 
System.out.println(unsignedString); // 4294967293

 

얼핏 봐서는 parseUnsignedInt() 메서드를 통해 unsigned int 범위에 해당하는 값이 임시적으로 signed int 값(=-3)으로 저장이 되고, 임시적으로 저장되었던 signed int 값이 toUnsignedString() 메서드를 통해 (String 타입의) unsigned int 값(=4294967293)으로 출력되는 것처럼 보입니다.

 

 

왜 이렇게 동작하는지는 parseUnsignedInt() 메서드 내부를 살펴보면 알 수 있습니다.

public static int parseUnsignedInt(String s, int radix)
          throws NumberFormatException {
  if (s == null)  {
      throw new NumberFormatException("Cannot parse null string");
  }

  int len = s.length();
  if (len > 0) {
      char firstChar = s.charAt(0);
      if (firstChar == '-') {
          throw new
              NumberFormatException(String.format("Illegal leading minus sign " +
                                                 "on unsigned string %s.", s));
      } else {
          if (len <= 5 || // Integer.MAX_VALUE in Character.MAX_RADIX is 6 digits
              (radix == 10 && len <= 9) ) { // Integer.MAX_VALUE in base 10 is 10 digits
              return parseInt(s, radix);
          } else {
              long ell = Long.parseLong(s, radix);
              if ((ell & 0xffff_ffff_0000_0000L) == 0) {
                  return (int) ell;
              } else {
                  throw new
                      NumberFormatException(String.format("String value %s exceeds " +
                                                          "range of unsigned int.", s));
              }
          }
      }
  } else {
      throw NumberFormatException.forInputString(s, radix);
  }
}

 

첫 번째로 null 체크를 하고,

두 번째로 첫 문자가 '-'인지(음수인지) 체크합니다. 음수는 unsigned int가 될 수 없기 때문입니다.

그 다음에는 입력 string 길이에 따라 분기처리를 하는데요. 5자리 이하 짧은 문자열이면 parseInt() 메서드로 처리하고, 그 이상(= 꽤 큰 값)이면 parseLong() 메서드로 처리하여 결과를 long 타입의 변수(ell)에 저장합니다.

parseLong() 메서드는 parseInt() 메서드와 동작 방식이 유사하지만 limit 값은 훨씬 크기 때문에, 위에서 parseInt() 메서드가 예외처리 했던 "signed int로는 표현할 수 없는, signed int 범위에서 벗어나는 값(=4294967293)"을 충분히 표현하고 처리할 수 있습니다. 

 

if ((ell & 0xffff_ffff_0000_0000L) == 0) { ... }

 

그렇게 처리된 long 타입(ell)의 값을 '상위 32비트만 1로 설정한 64비트 마스크'를 사용해, 해당 값의 상위 32비트가 모두 0인지 확인하는 작업을 거칩니다.

  • & 는 '비트 AND 연산자' 입니다. 두 비트가 모두 1일때만 1을 반환합니다. 그렇지 않으면 0을 반환합니다.
  • 0xFFFFFFFF00000000L(16진수 마스크)는 2진수로 표현하면 11111111_11111111_11111111_11111111_00000000_00000000_00000000_00000000 가 됩니다.
  • 즉 ell의 상위 32비트가 모두 0이어야만 해당 조건을 만족하게 됩니다.

이 검증 과정을 통과해야만, long 타입에 임시 저장된 unsigned int 범위의 값(= 4294967293)이 다시 안전하게 int 타입으로 형변환(= -3)될 수 있는 것입니다.

 

정리하자면, 이 과정은 상당히 클 것으로 예상되는 값(="11111111111111111111111111111101")을 long 타입으로 파싱(= 4294967293)한 뒤, 다시 int로 형변환(=-3)하는 과정으로 볼 수 있습니다.

 

디버깅 화면. long ell 값은 '4294967293' 이고 (int) ell 값은 '-3' 입니다.

 

 

마지막으로 toUnsignedString() 메서드 내부도 살펴보면

public static String toUnsignedString(int i) {
    return Long.toString(toUnsignedLong(i));
}

public static long toUnsignedLong(int x) {
    return ((long) x) & 0xffffffffL;
}

 

toUnsignedString() 메서드는 내부적으로 toUnsignedLong() 메서드의 반환값을 String으로 변환하여 리턴하고 있습니다.

toUnsignedLong() 메서드는 앞서 본 내용과 유사하게 '0xffffffffL' 마스크를 사용하여 값을 변환하고 있습니다.

  • '0xffffffffL'는 이진수로 표현하면 00000000_00000000_00000000_00000000_11111111_11111111_11111111_11111111 이 됩니다
    • 0xffffffff = 32개의 비트가 전부 1인 수
    • 맨 뒤에 L이 붙어서 long 리터럴이 됨 (64비트)
    • 즉, '0x00000000FFFFFFFF' (64비트)
  • 이 마스크는 signed int(특히 '음의 정수')를 unsigned int로 변환하는데 유용하게 사용됩니다. 예를 들어
  • x = -1 일 때
    • [입력 값] -1 은 
      • (32비트에서) '0xFFFFFFFF' 이고 
      • (64비트에서) long 부호 확장을 통해 '0xFFFFFFFFFFFFFFFF'가 됩니다.
    • [마스크] 0xffffffffL 는
      • (64비트) '0x00000000FFFFFFFF' 입니다.
    • 즉, 0xFFFFFFFFFFFFFFFF & 0x00000000FFFFFFFF = 0x00000000FFFFFFFF = '4294967295L' 입니다
  • x = -2 일 때
    • [입력 값] -2 는
      • (32비트에서) '0xFFFFFFFE' 이고
      • (64비트에서) long 부호 확장을 통해 '0xFFFFFFFFFFFFFFFE'가 됩니다.
    • [마스크] 0xffffffffL 는
      • (64비트) '0x00000000FFFFFFFF' 입니다.
    • 즉, 0xFFFFFFFFFFFFFFFE & 0x00000000FFFFFFFF = 0x00000000FFFFFFFE = '4294967294L' 입니다.

정리하자면, 이 과정은 int 값(특히 signed int, 음의 정수)을 unsigned int 로 표현하여 long 타입으로 변환하는 과정 (그리고 long 타입 값을 String으로 변환하는 과정)으로 볼 수 있습니다.

 

 

정리하며

Integer.parseInt() 메서드는 binary string 을 32비트 signed int로 해석하여 parsing을 진행합니다. Java는 기본적으로 signed 타입만 제공하기 때문입니다. 따라서 parsing을 진행하면서 해당 binary가 signed int 의 범위를 벗어나는 것으로 판단되면 예외를 발생시킵니다.

 

이때 사용할 수 있는 것이 Integer.parseUnsignedInt() 메서드입니다. 해당 메서드는 동일한 binary string을 unsigned int로 해석하여 부호 없는 32비트 정수 범위 값(0 ~ 4,294,967,295)로 변환해줍니다. 내부적으로는 Long.parseLong()을 통해 64비트 long으로 parsing하고, 그 값의 상위 32비트가 0일 경우 int로 형변환하여 반환하는 것입니다.

 

 

참고

 

+ Recent posts

티스토리툴바