shift 연산과 오버플로우

shift연산에 대해서 여러 실험을 해본 것은 

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

23250번: 하노이 탑 K

이 문제 때문이다.

 

하노이탑 문제는 대학교 수업에도 많이 나올만큼 재귀를 설명하는데 있어서 좋은 예시가 된다.

기본 하노이 코드는 다음과같은 모양을 따른다.

 

void Hanoi(ull num, ull start, ull by, ull to, ull mok)
{
	if (num == 1)
	{
		cout << start << " " << to << "\n";
	}
	else
	{
      		Hanoi(num - 1, start, to, by, mok);
		cout << start << " " << to << "\n";
        	Hanoi(num - 1, by, start, to, mok);
	}
}

하지만 이 문제와 같은 경우에 2^60 까지 시간복잡도가 커지기 때문에 입력되는 K 에 따라서 하노이의 옮기는 부분을 나눠 주어 이분탐색의 형태를 띄게 만들어 해결하는 문제이다.

 

하지만 이 문제를 풀면서 무수한 틀렸습니다를 받았다.

 

이 문제를 틀릴만한 요인으로 세가지를 뽑았는데

1. 단순한 범위 설정 오류

2. 숫자의 크기에 대한 overflow

3. 자료형의 문제

 

그중 처음은 1번에 의해 틀렸지만 

2번 3번 문제를 해결 하기위해 여러 시도를 해보았다.

 

처음 시도한것은 pow() 함수의 재설정이다.

https://www.ibm.com/docs/ko/i/7.3?topic=functions-pow-compute-power 

pow() — Compute Power

pow함수는 double형을 반환하기 때문에 이를 해결하기 위해서 pow()함수를 다시 만들어야한다.

 

최종적으로 pow함수는 다음과 같은 모습을 취했다.

ull pow(int a, int b)
{
	ull tmp = 1;

	while (true)
	{
		if (b <= 0)
			break;

		tmp = tmp << 1;

		b--;
	}

	return tmp;
}

 

 

이를 실행하기 앞서서 시도했던 방식이

shift연산을 이용한것이었다.

pow함수를 쓰는 것 대신에 

2 << K

다음과 같은 방식으로 2^K 승을 구현할 수 있다.

 

하지만, 이와 같은 방식도 "틀렸습니다." 를 내뱉는다.

이를 조사해본결과 shift연산은 좌변의 수를 기준으로 자료형으로 결정한다.

 

2^K 결과 값이 int형으로 진행된다는 점이다. 이가 MAX_INT의 범위를 벗어나면 overflow가 일어난다.

(long long)2 << K

따라서 이를 명시적 형변환을 통해 변경하면 이를 해결 할 수 있다.