2진수가 담긴 문자열이 주어졌을 때, 재귀(recursion) 기법을 사용하여 이에 해당하는 10진수 값을 구하는 것이 이 글의 목표입니다.
2진수를 10진수로 변환하는 원리
2진수는 다음과 같은 방법으로 10진수로 변환할 수 있습니다. 최하위 비트(LSB)부터 최상위 비트(MSB)까지 각 자릿수를 순회하면서, 각 자릿수에 2i(단, 0 ≤ i ≤ 자릿수 개수)를 곱하고 그 모든 결과를 합산하는 것입니다.
입력 및 출력 예시
예제 1
입력 − binStr[] = "110010"
출력 − 주어진 2진수에 해당하는 10진수: 50
설명 − 110010을 10진수로 변환하면 다음과 같습니다.
= 0×20 + 1×21 + 0×22 + 0×23 + 1×24 + 1×25
= 0 + 2 + 0 + 0 + 16 + 32
= 50
예제 2
입력 − binStr[] = "0011"
출력 − 주어진 2진수에 해당하는 10진수: 3
설명 − 0011을 10진수로 변환하면 다음과 같습니다.
= 1×20 + 1×21 + 0×22 + 0×23
= 1 + 2 + 0 + 0
= 3
프로그램의 접근 방식
여기서는 재귀 함수 bintoDecimal(strBin, length)를 사용합니다. 이 함수는 2진수 문자열과 그 길이를 입력으로 받아, 각 문자를 10진수 값으로 변환한 후 2i를 곱하고 이전 결과들에 더하는 방식으로 동작합니다.
- 2진수가 담긴 입력 문자열 strBin[]을 받습니다.
strlen(strBin)을 사용하여 문자열의 길이를 계산합니다.- 함수 bintoDecimal(strBin, length)는 입력값을 받아 재귀적 접근 방식으로 계산된 결과를 반환합니다.
- 현재 위치가 마지막 문자, 즉 LSB라면 해당 문자의 10진수 값을 그대로 반환합니다. (20 = 1을 곱하는 것과 같기 때문입니다.)
- 그렇지 않은 경우
temp = binary[i] - '0'으로 설정하여 해당 문자의 10진수 값을 구합니다. temp << len-i-1연산을 통해 temp에 2len-i-1을 곱합니다.temp = temp + bintoDecimal(binary, len, i+1)로 나머지 자릿수들의 계산 결과를 temp에 더합니다.- 재귀 호출이 끝나면 최종적으로 temp를 반환합니다.
- main 함수에서 계산된 10진수를 출력합니다.
참고: 코드에서 사용된 왼쪽 시프트 연산자(<<)는 temp << n 형태로 사용될 경우 temp에 2n을 곱하는 것과 동일한 효과를 냅니다. 따라서 별도의 거듭제곱 함수 없이 효율적으로 2의 거듭제곱을 계산할 수 있습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int bintoDecimal(char binary[],int len, int i=0){
if (i == len-1)
return (binary[i] - '0');
int temp=binary[i]-'0';
temp=temp<<len-i-1;
temp=temp+bintoDecimal(binary,len,i+1);
return (temp);
}
int main(){
char strBin[] = "11010";
int length=strlen(strBin);
cout <<"Equivalent Decimal of given binary: "<<bintoDecimal(strBin,length) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Equivalent Decimal of given binary: 26