[코딩테스트] 정수 자료형의 범위와 연산 순서

백준 15894번 : 수학은 체육과목 입니다

https://www.acmicpc.net/problem/15894

 

 

 

이 문제도 이전 꼬마정민 문제와 같이 정수 자료형의 범위와 관련된 문제였다.

하지만 거기에서 추가적인 내용이 있어서 적어본다.

백준 11382 꼬마 정민

[코딩 테스트] 정수 자료형의 범위

 

 

---

문제 분석

우선 문제를 보면 문제 자체는 굉장히 단순하다.

그냥 맨 마지막 줄의 사각형의 개수에 * 4 를 하면 정답이다.

입력값으로 맨 마지막 줄의 사각형의 개수를 주기 때문에 거기에 *4만 하면 되는 것이다.

 

그런데 왜 틀렸냐...

 

우선 문제에서 입력값의 범위를 제시해준다.

 

이전에 내가 한번 틀렸기 때문에 int 값의 범위가 대략 2 * 10^9 정도 된다는 사실을 기억하고 있었기 때문에

입력받은 값을 int타입의 변수에 저장하고

 

결과값은 입력값에 *4를 할 경우에 int의 범위를 넘어갈 수 있으므로 long으로 선언 후 값을 받아줬다.

 

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		long perimeter = 4 * n;
		
		System.out.println(perimeter);
	}
}

 

위와 같이 작성한 것이다.

 

이렇게 쓰고 음음 좋아. 이번에는 저번처럼 안틀리고 무난히 넘어가겠군 했는데...

 

바로 틀려버림...

---

오답 원인 찾기

내가 int타입 변수의 범위를 잘못 기억하고 있었나?

찾아봤지만 

 

내가 기억하고 있는 범위가 맞았다.

 

그러면 뭐가 문제일까...

int타입 값을 연산 후 long타입의 변수에 넣을 때 문제가 생기는 걸까?

long 타입을 int에 넣을 때 문제가 생기는 것처럼 비슷한 문제인걸까?

 

이런 생각이 들어서 우선 입력값을 long으로 수정했더니

 

엥? 정말 이게 문제가 생긴다고??

 

근데 더 작은 범위인 int가 long에 대입되는데 문제가 생길 이유가 전혀 없다는 생각이 들었다.

 

그러다가 문득 머리를 스치는 생각이 하나 있었는데..

long perimeter = 4 * n;

 

이 줄은 하나의 연산 같지만, 사실 연산이 2개가 연속으로 이루어지는 부분이다.

 

사실 이건 여기에서 중요한건 아니지만 생각난김에 연산자 우선순위를 한번 정리하고 가보자

연산자 적용 우선순위

(1) 최우선 연산자 : (), {}, [],...
(2) 단항 연산자 : +(양수), -(음수), not
(3) 산술 연산자 : +, -, *, /, //, %, **
(4) 쉬프트 연산자 : >>, >>,....
(5) 관계 연산자 : >, <, <=, >=,...

(6) 비트 연산자 : |, &, ^
(7) 논리 연산자 : and, or, not
(8) 삼항 연산자 
(9) 대입 연산자(=)

 

위와같이 나는 최단산쉬 관비논삼대 이렇게 외웠다.

 

 

어쨋든 그러면 다시 아까 코드에서 대입연산과 산술연산이 실행되는데

이부분이 내가 혹시? 싶었던 부분이다.

 

산술연산을 먼저 실행하고 대입연산이 실행되기 전.

이때 연산된 수는 어떤 자료형으로 존재하는가?

생각해보면 그때까지는 int타입밖에는 연산에 관여한 자료형이 없다.

 

그렇다면 입력값의 최대값인 1,000,000,000을 받아왔을 때 *4를 하면 int타입의 범위를 넘어서게 되는데 혹시 이때 문제가 생기는 것이 아닐까?? 이런 생각이 들어서 한번 코드에 값을 넣어보았다.

---

원인 발견

 

결과로 -294,967,296이 나왔다.

 

---

컴퓨터에서 음수의 표현

어떤 숫자가 컴퓨터에 저장될때는 모두 이진수로 저장된다는 것은 모두 알 것이다.

여기에서 그러면 음수는 어떻게 표현되는 것일까?

 

사실 컴퓨터는 0과 1밖에 인식하지 못하기 때문에 음수를 표현할 수는 없다.

그래서 어떤 양수에 절대값이 동일한 음수를 더하면 0이 되는 성질을 이용해 음수를 표현했다고 한다.

 

컴퓨터에서 음수가 없는데 어떻게 더하기만해서 0이 되는걸까?

범위를 벗어나는 수를 만드는 것이다.

 

 

 

내가 4개의 비트를 읽을 것이라고 범위를 정했다고 해보자.

1111은 그중에서 최대값일 것이다.

 

그런데 여기에 만약에 0001을 더한다면 어떻게 될까?

원래라면 10000이 되어야하지만 나는 4개의 비트만 읽을 것이라고 범위를 정했으므로

나에게 해당 수는 0000이 되는 것이다.

두 수를 더했는데 0이 된 것이다.

 

어떤 정수에 다른 정수를 더했는데 그 값이 0이 된다면 두 수는 서로 부호가 반대이며, 절댓값이 같은 수라는 의미라고 했다.

그렇다면 누가 음수이고 누가 양수인가?

 

이걸 정하기 위해서 맨 앞에 부호를 나타내는 부호비트를 넣은 것이라고 생각하면 된다.

이때 0을 양수, 1을 음수라고 하기로 한 것이다.

 

4비트 범위에서 수를 센다면 0011은 양수, 1010은 음수 이런식으로 볼 수 있다.

 

 

 

그럼 어떤 양수의 절대값이 동일한 음수를 찾으려면 어떻게 할까?

 

0011을 예로 들어본다면, 0011에 어떤 수를 더했을 때, 범위를 벗어나는 수 하나를 제외하고 모두 0이되게 만들면된다.

우선 모든 비트가 1인 수를 만들어보자.

0011에 1100을 더하면 1111로 모든 비트가 1인 수가 될 것이다. 여기에 1만 더하면 1|0000 으로 범위가 짤리면서 0이 된다.

 

이런 순서로 모든 수의 양수를 쉽게 구할 수 있다.

우선 더해서 모든 비트가 1이 되는 수를 구한 뒤, 1을 더하면 절대값이 동일한 음수가 나온다.

 

한번만 더 예시를 통해 보겠다.

8개의 비트를 사용한다고 해보자

0010 1101 이라는 양수가 있을 때, 모든 비트를 반전하면

1101 0010 이 되고, 이 둘을 더했을 때 모든 비트가 1이 된다.

1111 11111 => 여기에 1을 더하면 1 | 0000 0000 이렇게 1이 범위 밖으로 튕겨져 나가며, 범위내의 모든 비트가 0이 된다.

 

---

다시 돌아와서

왜 결과가 -294,967,296이 나온것일까 확인해보자

 

나는 1,000,000,000에 4를 곱했다.

4,000,000,000을 표현하려고 했던 것이다.

하지만 위에서 얘기했듯이 int 타입의 최대값은 대략 2,000,000,000 정도이다.

이 수를 넘어서는 값을 int 타입에 저장하려고 한 것인데,

비트로 한번 보자

 

 

위와 같이 표현된다.

int는 4byte로 총 32비트로 표현이 된다.

 

여기에서 맨 앞의 비트를 보면 1로 표현이 된 것을 볼 수 있는데, 이것을 컴퓨터는 음수로 판단한 것이다.

그렇다면 어떤 수의 음수일까

위에 공부한 방식대로 계산해보자

저기에 표현된 모든 비트들을 반전하고 1을 더하면 절대값은 동일하고 부호가 다른 수가 나온다.

 

4,000,000,000 은 아래와 같다.

1

1

1

0

1

1

1

0

0

1

1

0

1

0

1

1

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

 

위 모든비트를 반전하면

0

0

0

1

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

0

1

1

1

1

1

1

1

1

1

1

1

 

여기에 1을 더하면

0

0

0

1

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

0

0

0

0

0

0

0

0

0

 

 

이제 이걸 십진수로 변경하면

 

짜잔~~ 익숙한 숫자가 나왔다

 

4,000,000,000을 int 타입으로 표현하려고 하면, 294,967,296의 음수값이 나온다는 것이다.

 

---

결론

long 타입에 대입하기 전, int 타입만 존재하는 연산에서 int 타입 변수의 범위를 벗어나면 이와같은 오류가 발생하므로,

해당 변수에 저장되는 값의 범위만 고려할 것이 아니라, 해당 변수가 들어가는 연산 자체의 범위를 고려해서 타입을 설정해야 했던 것이다.

 

이런 이유로 위 나의 코드가 실패했던 것이고, 입력값을 long으로 받아야 정답처리가 된 이유이다.

 

근데 부호비트를 빼고 모든 값을 양수로만 받으면서 범위를 더 넓게 쓰는 unsigned 자료형이 있는데, 자바에는 없다!!