C++에서 주어진 숫자를 이진수로 표현하는 방법

이진수(binary number)는 0과 1이라는 두 개의 숫자만으로 구성된 수를 말합니다. 예를 들어 01010111과 같은 형태입니다.

하나의 숫자를 이진수 형태로 나타내는 방법은 여러 가지가 있으며, 그중 대표적인 재귀(Recursion) 기반 방법을 소개합니다.

재귀적 방법

이 방법은 재귀 호출을 활용하여 숫자를 이진수 형태로 변환하는 기법입니다. 숫자를 2로 계속 나누면서 그 나머지를 역순으로 출력하는 원리로 동작합니다.

알고리즘

1단계 : 숫자가 1보다 크면 2단계와 3단계를 수행한다.
2단계 : 해당 숫자를 스택에 저장(push)한다.
3단계 : 숫자를 2로 나눈 값을 인자로 하여 함수를 재귀적으로 호출한다.
4단계 : 스택에서 숫자를 꺼내(pop) 2로 나눈 나머지를 출력한다.

예제 코드

아래는 C++로 작성한 재귀 함수 tobinary()의 구현 예제입니다. 함수는 숫자를 2로 나누어가며 재귀 호출한 뒤, 각 단계에서 2로 나눈 나머지를 출력하여 이진수를 완성합니다.

#include<iostream>
using namespace std;
void tobinary(unsigned number){
   if (number > 1)
      tobinary(number/2);
   cout << number % 2;
}
int main(){
   int n = 6;
   cout<<"The number is "<<n<<" and its binary representation is ";
   tobinary(n);
   n = 12;
   cout<<"\nThe number is "<<n<<" and its binary representation is ";
   tobinary(n);
}

실행 결과

The number is 6 and its binary representation is 110
The number is 12 and its binary representation is 1100

동작 원리 설명

숫자 6을 예로 들면 다음과 같이 동작합니다.

먼저 6은 1보다 크므로 6/2인 3으로 재귀 호출됩니다. 3 역시 1보다 크므로 3/2인 1로 재귀 호출되며, 1은 더 이상 나누지 않고 출력을 시작합니다. 이후 호출 스택이 거꾸로 풀리면서 각 단계의 나머지(1 % 2 = 1, 3 % 2 = 1, 6 % 2 = 0)가 순서대로 출력되어 최종적으로 110이라는 이진수가 완성됩니다.

이처럼 재귀를 이용한 이진수 변환은 코드가 간결하고 직관적이라는 장점이 있으며, 시간 복잡도는 숫자의 비트 길이에 비례하는 O(log n)입니다.