2진수를 10진수로 변환하기
10진수를 이용하여 표현된 2진 상수의 값을 계산하는 템플릿을 만들어보자.
우선 일반 함수 재귀를 이용하여 만들어 보자.
일반 함수로 구현
int Binary(int num) {
if (num == 0)
return 0;
return Binary(num / 10) << 1 | (num % 10);
}아래 코드(더보기)를 실행하며 진행을 관찰해보면 어떻게 동작하는지를 알 수 있다.
▼▼▼
int Binary(int num, int tab = 1) {
if (num == 0) {
std::cout << "num = 0 (재귀 종료)" << std::endl << std::endl;
return 0;
}
std::cout << "num = " << num << std::endl;
for (size_t i = 0; i < tab*2; i++) std::cout << "\t";
std::cout << "재귀 " << tab << " ";
int sum1 = Binary(num / 10, tab + 1) << 1;
for (size_t i = 0; i < (tab-1)*2; i++) std::cout << "\t";
std::cout << "(" << num << " / 10) << 1 = " << sum1 << std::endl;
int sum2 = num % 10;
for (size_t i = 0; i < (tab - 1) * 2; i++) std::cout << "\t";
std::cout << num << "% 10 = " << sum2 << std::endl;
for (size_t i = 0; i < (tab - 1) * 2; i++) std::cout << "\t";
std::cout << sum1 << " | " << sum2 << " = " << (sum1 | sum2) << std::endl;
for (size_t i = 0; i < (tab - 1) * 2; i++) std::cout << "\t";
std::cout << "재귀 탈출" << std::endl << std::endl;
return sum1 | sum2;
}
int main(){
int res = Binary(11101);
std::cout << res;
}
재귀 프레임을 탈출하는 과정에서 일어나는 변화를 잘 관찰해보면 답을 알 수 있다.
▲▲▲
템플릿 코드
template<unsigned long num>
struct binary
{
static unsigned const value =
binary<num / 10>::value << 1 | num % 10;
};
// Specialization for zero
template<>
struct binary<0>
{
static unsigned const value = 0;
};
int main()
{
int res = binary<11101>::value; // 29
}
템플릿 코드에서 주의해서 봐야할 부분은 다음과 같다.
value = binary<num / 10>::value <<1 | num % 10;그 중에서도 표현식 뒷부분의 num % 10 을 눈여겨 봐야한다.
아래 그림은 10진수 11을 2진수 1011로 변환하는 과정이다.
과정을 나열해보면 다음과 같다.
- 주어진 수를 2로 나눈다.
- 몫과 나머지를 구한다.
- 몫이 1이 될때까지 반복한다.
- 각 나머지들을 역순으로 나열하여 2진수를 만든다.
11을 2로 나누면 몫은 5이고 이때 나머지는 1 이다. 이 때 나머지는 2진수의 첫째자리이다.
5를 2로 나누면 몫은 2이고 이때 나머지는 1 이다. 이 때 나머지는 2진수의 둘째자리이다.
2를 2로 나누면 몫은 1이고 이때 나머지는 0 이다. 이 때 나머지는 2진수의 셋째자리이다.
몫이 2보다 작아졌으므로 이것은 2진수의 가장 높은 자리가 된다.
구한 값들을 위 그림의 화살표 방향으로 나열하면 1011 이 된다.
이것이 10진수 11을 이진수로 변환한 값이다.
위의 과정의 역순으로 진행하면 2진수를 10진수로 변환하는 과정이 된다.
템플릿이 재귀하며 계산되는 과정을 살펴보자
1) 최초 템플릿 호출 코드에서 29에 해당하는 11101을 전달 binary<11101>::value
int res = binary<11101>::value; // 29
2) binary<11101>::value 에 대한 최초의 템플릿 추론 시작
// num = 11101
value = binary<num / 10>::value << 1 | num % 10;위 코드에서 binary<11101 / 10>::value << 1 부분에 대한 추론이 필요.
11101 / 10 = 1110 이되므로 binary<1110>::value << 1 에 대한 추론 시작.
3) binary<1110>::value << 1 에 대한 템플릿 재귀 추론
// num = 1110
value = binary<num / 10>::value << 1 | num % 10;위 코드에서 binary<1110 / 10>::value << 1 부분에 대한 추론이 필요.
1110 / 10 = 111 이되므로 binary<1110>::value << 1 에 대한 추론 시작.
4) binary<111>::value << 1 에 대한 템플릿 재귀 추론
// num = 111
value = binary<num / 10>::value << 1 | num % 10;위 코드에서 binary<111 / 10>::value << 1 부분에 대한 추론이 필요.
111 / 10 = 11 이되므로 binary<11>::value << 1 에 대한 추론 시작.
5) binary<11>::value << 1 에 대한 템플릿 재귀 추론
// num = 11
value = binary<num / 10>::value << 1 | num % 10;위 코드에서 binary<11 / 10>::value << 1 부분에 대한 추론이 필요.
11 / 10 = 1 이되므로 binary<1>::value << 1 에 대한 추론 시작.
6) binary<1>::value << 1 에 대한 템플릿 재귀 추론
// num = 1
value = binary<num / 10>::value << 1 | num % 10;위 코드에서 binary<1 / 10>::value << 1 부분에 대한 추론이 필요.
1 / 10 = 0 이되므로 binary<0>::value << 1 에 대한 추론 시작.
7) binary<0>::value << 1 에 대한 템플릿 재귀 추론
// num = 0
value = binary<num / 10>::value << 1 | num % 10;위 코드에서 binary<0 / 10>::value << 1 부분에 대한 추론이 필요.
1 / 10 = 0 이되므로 binary<0>::value에 대한 추론 결과는
아래의 템플릿이 선택되면서 0을 반환하고, 재귀 프레임은 더 이상 늘어나지 않는다.
template<>
struct binary<0>
{
static unsigned const value = 0;
};그리고 0<<1 | 0 % 10 의 결과인 0을 상위 호출 프레임에 반환한다.(현재 재귀 프레임 탈출)
8) binary<1>::value << 1 | num % 10 에 대한 템플릿 재귀 추론
// num = 1
value = binary<num / 10>::value << 1 | num % 10;binary<num / 10>::value << 1 | num % 10 부분에서
binary<1 / 10>::value << 1 에 대한 결과는 0임을 확인하였다.
이제 나머지 num % 10 부분에 대한 결과만 확인하면 된다.
num이 1이므로 1 % 10 = 1 이 된다.
따라서 0 | 1 의 결과는 1이된다.
이 결과를 상위 호출 프레임에 반환한다.
9) binary<11>::value << 1 | num % 10 에 대한 템플릿 재귀 추론
// num = 11
value = binary<num / 10>::value << 1 | num % 10;binary<num / 10>::value << 1 | num % 10 부분에서
binary<11 / 10>::value는 1이므로 1 << 1 = 2 가 된다.
이제 나머지 num % 10 부분에 대한 결과만 확인하면 된다.
num이 11이므로 11 % 10 = 1 이 된다.
따라서 2 | 1 의 결과는 3이된다. ( 이진수 연산으로 표현 -> 10 | 01 = 11 )
이 결과를 상위 호출 프레임에 반환한다.
10) binary<111>::value << 1 | num % 10 에 대한 템플릿 재귀 추론
// num = 111
value = binary<num / 10>::value << 1 | num % 10;binary<num / 10>::value << 1 | num % 10 부분에서
binary<111 / 10>::value는 3이므로 3 << 1 = 6 이 된다.
이제 나머지 num % 10 부분에 대한 결과만 확인하면 된다.
num이 111이므로 111 % 10 = 1 이 된다.
따라서 6 | 1 의 결과는 3이된다. ( 이진수 연산으로 표현 -> 110 | 001 = 111 )
이 결과를 상위 호출 프레임에 반환한다.
11) binary<1110>::value << 1 | num % 10 에 대한 템플릿 재귀 추론
// num = 1110
value = binary<num / 10>::value << 1 | num % 10;binary<num / 10>::value << 1 | num % 10 부분에서
binary<1110 / 10>::value는 7이므로 7 << 1 = 14 가 된다.
이제 나머지 num % 10 부분에 대한 결과만 확인하면 된다.
num이 1110이므로 1110 % 10 = 0 이 된다.
따라서 14 | 0 의 결과는 14이된다. ( 이진수 연산으로 표현 -> 1110 | 0000 = 1110 )
이 결과를 상위 호출 프레임에 반환한다.
12) binary<11101>::value << 1 | num % 10 에 대한 템플릿 재귀 추론
// num = 11101
value = binary<num / 10>::value << 1 | num % 10;binary<num / 10>::value << 1 | num % 10 부분에서
binary<11101 / 10>::value는 14 이므로 14 << 1 = 28 이 된다.
이제 나머지 num % 10 부분에 대한 결과만 확인하면 된다.
num이 11101이므로 11101 % 10 = 1 이 된다.
따라서 28 | 1 의 결과는 29 가 된다. ( 이진수 연산으로 표현 -> 11100 | 00001 = 11101 )
이 결과를 상위 호출 프레임에 반환하면
int res = 29; 가 된다.
이 모든 과정이 컴파일 타임에 완료되므로
프로그램 실행 시 런타임에서는 아무런 계산비용이 발생하지 않게 된다.
재귀 과정 요약
| 최초 호출 프레임 binary<11101 / 10>::value << 1 | 11101 % 10; 29에 해당하는 11101을 num으로 전달하여 호출 1번째 재귀 binary<1110 / 10>::value << 1 | 1110 % 10; num / 10 = 1110 로 재귀. 2번째 재귀 binary<111>::value << 1 | 111 % 10; num / 10 = 111 로 재귀. 3번째재귀 binary<11>::value << 1 | 11 % 10; num / 10 = 11 로 재귀. 4번째재귀 binary<1>::value << 1 | 1 % 10; num / 10 = 1 로 재귀. 5번째재귀 binary<0>::value << 1 | 0 % 10; binary<0>::value = 0 이므로 재귀를 탈출하여 4번째 재귀로 이동 4번째 재귀 (1/10) << 1 | 1 % 10 = 1 이 되며, 재귀를 탈출하여3번째 재귀로 이동 3번째 재귀 1 << 1 | 11 % 10 = 3이 되며, 재귀를 탈출하여2번째 재귀로 이동 2번째 재귀 3 << 1 | 111 % 10 = 7이 되며, 재귀를 탈출하여1번째 재귀로 이동 1번째 재귀 7 << 1 | 1110 % 10 = 14가 되며,재귀를 탈출하여 최초 호출 프레임으로 이동 최초 호출 프레임 14 << 1 | 11101 % 10 = 29가 되며, 템플릿 추론 종료. |
간단히 정리하면 다음과 같다.
- 재귀 추론 탈출 조건인 num / 10 == 0을 만족하여 템플릿 binary<0>을 만날 때까지 재귀가 중첩된다.
- 재귀 탈출 조건을 만나면 ( num / 10 ) << 1 | num % 10 의 결과를 상위 호출 프레임으로 전달해준다.
- 템플릿 추론 프레임들이 하나씩 해제되면서
최초 호출 프레임에 도달하면 ( num / 10 ) << 1 | num % 10 의 결과를 최종적으로 계산한다.