[C++] 진수 변환

진수 변환

개요

　프로그래밍에는 여러 가지 다양한 알고리즘이 존재하며, 그중 십진수를 이진수로 바꾸는 알고리즘은 매우 중요한 개념이다. 이진수 변환은 많은 프로그래밍 문제에서 요구되는 기술로서, 백준 1094 막대기 문제나 프로그래머스의 다음 큰 숫자 문제와 같이 이진수에 관한 연산이 필요한 경우가 대표적이다. 이 게시글에서는 C++을 사용하여 십진수를 이진수로 변환하는 방법을 자세히 알아보도록 하겠다.

---

원리

　일반적으로 10진수를 2진수로 변환하는 과정은 다음과 같다. 십진수 n을 2로 나눈 나머지를 구하고, 이 값은 이진수의 가장 낮은 자릿수가 된다. n을 2로 나눈 몫을 새로운 n으로 설정한다. n이 0이 될 때까지 이 과정을 반복한다.

 

 

　이 원리는 이진수가 2의 지수 형태로 표현되는 것에서 기인한다. 예를 들어, 이진수 101은 2^2 * 1 + 2^1 * 0 + 2^0 * 1 = 5가 된다. 이렇게 보면, 각 비트는 특정 2의 지수를 나타내며, 그 지수가 켜져 있는지, 아니면 꺼져 있는지를 나타내게 된다. 따라서 10진수를 2진수로 바꾸려면 10진수를 2로 나누고 나머지를 확인하는 과정을 반복함으로써 각 비트가 켜져 있는지, 꺼져 있는지를 결정하는 것이다.

 

　조금 더 수학적으로 접근하면, 각 숫자를 쓰는 자리에 자릿값을 미리 정하여 그 자리에 쓰이는 수자와 그 자리에 정해진 자릿값을 곱하는 위치적 기수법을 이용할 수 있다. 어떤 수 N이 있다고 가정해 보자. 이를 십진수와 이진수로 표현하면 다음과 같다.

 

 

　이 원리에 따라 만약 어떤 수 N이 있다고 해보면, 다음과 같이 표현할 수 있을 것이다.

 

 

　따라서 이진수에서 십진수로 바꿀 때는 단순히 이 수열을 이용해, 즉 2의 거듭제곱을 이용해 쉽게 구할 수 있다. 반대로 십진수를 이진수로 변환할 때는 이진수의 각 자릿수를 나타내는 2의 거듭제곱의 계수를 찾아야 한다. 따라서 2로 나눠주면 되는 것이다.

---

구현

bitset 라이브러리 활용

　이제 원리를 파악했으니, C++에서 어떻게 변환 과정을 거치는지 확인해 보자. 먼저 라이브러리를 활용해 63을 이진수로 바꿔보고, 이진수 1011을 십진수로 바꿔보자.

 

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
	bitset<32> decimal_to_binary(10);
	bitset<32> binary_to_decimal("1011");
	unsigned num = static_cast<unsigned>(binary_to_decimal.to_ulong());

	cout << "10 to binary: " << decimal_to_binary << "\n";
	cout << "1011 to decimal: " << num << "\n";
}

 

　여기서 만약 유효 비트를 제외한 나머지 비트를 지우고 싶으면, 비트셋을 문자열로 변환한 후 문자열을 처리하는 방법으로 이를 수행할 수 있다. 여기서 bitset<32>는 32비트를 의미한다.

 

#include <iostream>
#include <string>
#include <bitset>
using namespace std;

int main()
{
	bitset<32> decimal_to_binary(10);
	bitset<32> binary_to_decimal("1011");
	unsigned num = static_cast<unsigned>(binary_to_decimal.to_ulong());
	string binary_string = decimal_to_binary.to_string();
	
	size_t first_found = binary_string.find('1');
	if (first_found != string::npos)
		binary_string = binary_string.substr(first_found);

	cout << "10 to binary: " << binary_string << "\n";
	cout << "1011 to decimal: " << num << "\n";
}

 

　비트셋을 문자열로 변환한 후, 처음으로 발견한 1의 위치에서 나머지 문자열까지 자르면 쉽게 해결할 수 있다.

 

직접 구현

　이번에는 앞서 설명한 원리에 입각해 10진수와 2진수를 변환시켜 보자. 먼저 10진수 정수 n을 입력받았을 때 이진수를 출력하는 get_binary() 함수다.

 

#include <iostream>
#include <string>
using namespace std;

int get_binary(int n)
{
    string binary = "";

    while (n != 0)
    {
        binary += to_string(n % 2);
        n /= 2;
    }

    reverse(binary.begin(), binary.end());

    return stoi(binary);
}

　정수 n을 입력받았을 때, 이진수 문자열 binary에 2로 나눈 나머지를 추가하고 있다. 여기서 나누는 순서가 거꾸로 되어 있으므로 reverse() 함수를 이용해 문자열의 순서를 바꿔준 후, 정수로 변환하여 값을 반환하였다.

 

int get_decimal(string n)
{
    int decimal = 0;
    int factor = n.size();

    for (const auto& ch : n)
        decimal += (ch - '0') * pow(2, --factor);

    return decimal;
}

　문자열 n을 입력받았을 때, 정수 decimal에 자릿수 * 2의 거듭제곱의 형태로 값을 더하였다.

 

int get_decimal(string n)
{
    int decimal = 0;

    for (const auto& ch : n)
    {
        decimal <<= 1;
        
        if (ch == '1') 
            decimal += 1;
    }

    return decimal;
}

　이진수를 십진수로 변환하는 다른 방법이다. 비트 연산자를 이용해 문자열의 각 문자를 왼쪽에서 오른쪽으로 순회하면서 결과 변수를 왼쪽으로 시프트 하였다. 그런 다음 현재 문자가 '1'이라면 결과 변수에 1을 더하는 방식으로 2의 거듭제곱을 곱하는 대신 비트 시프트를 사용하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
using namespace std;

int get_binary(int n)
{
    string binary = "";

    while (n != 0)
    {
        binary += to_string(n % 2);
        n /= 2;
    }

    reverse(binary.begin(), binary.end());

    return stoi(binary);
}

int get_decimal(string n)
{
    int decimal = 0;

    for (const auto& ch : n)
    {
        decimal <<= 1;

        if (ch == '1') 
            decimal += 1;
    }

    return decimal;
}

int main()
{
	int decimal = 10;
	string binary = "1011";

    cout << "10 to binary: " << get_binary(10) << "\n";
    cout << "1011 to decimal: " << get_decimal(binary);
}

---

요약

진수 변환
- bitset 라이브러리와 string 라이브러리를 활용하여 십진수와 이진수 간 변환을 할 수 있다.