재귀를 이용해 이진수를 그레이 코드로 변환하는 C++ 프로그램

이진수(binary number)는 0과 1, 두 개의 비트만으로 표현되는 수입니다.

그레이 코드(Gray code)는 연속된 두 코드 값이 절대 한 비트 이상 차이 나지 않는다는 독특한 성질을 가진 특수한 형태의 이진수입니다. 즉, 인접한 두 값 사이에는 항상 정확히 한 비트만 변화합니다. 이러한 특성 덕분에 그레이 코드는 카르노 맵(K-map), 오류 정정, 디지털 통신 등 다양한 분야에서 널리 활용됩니다.

따라서 이진수를 그레이 코드로 변환하는 작업은 매우 중요합니다. 이번 글에서는 재귀(recursion)를 이용해 이진수를 그레이 코드로 변환하는 알고리즘을 알아보겠습니다.

예제

간단한 예제를 통해 변환 과정을 먼저 확인해 보겠습니다.

입력 : 1001
출력 : 1101

알고리즘

1단계 : 입력값 n에 대해 다음을 수행한다.
    1.1 : n = 0이면 gray = 0을 반환한다.
    1.2 : 마지막 두 비트가 서로 다르면,
          gray = 1 + 10 × (n/10을 인자로 1단계 재귀 호출)
    1.3 : 마지막 두 비트가 같으면,
          gray = 10 × (n/10을 인자로 1단계 재귀 호출)
2단계 : 계산된 gray 값을 출력한다.
3단계 : 종료한다.

C++ 구현 예제

#include <iostream>
using namespace std;

// 재귀적으로 이진수를 그레이 코드로 변환하는 함수
int binaryGrayConversion(int n) {
    if (!n)
        return 0;
    int a = n % 10;          // 마지막 자릿수
    int b = (n / 10) % 10;   // 마지막에서 두 번째 자릿수
    // 마지막 두 비트가 다르면 해당 자리의 그레이 비트는 1
    if ((a && !b) || (!a && b))
        return (1 + 10 * binaryGrayConversion(n / 10));
    // 마지막 두 비트가 같으면 해당 자리의 그레이 비트는 0
    return (10 * binaryGrayConversion(n / 10));
}

int main() {
    int binary_number = 100110001;
    cout << "이진수: " << binary_number << endl;
    cout << "그레이 코드 변환 결과: " << binaryGrayConversion(binary_number);
    return 0;
}

실행 결과

이진수: 100110001
그레이 코드 변환 결과: 110101001

동작 원리

그레이 코드의 각 비트는 원래 이진수에서 인접한 두 비트를 XOR한 값과 같습니다(최상위 비트는 그대로 유지됩니다). 위 재귀 함수는 숫자의 가장 오른쪽 두 자릿수를 비교하여, 두 비트가 다르면 해당 자리의 그레이 비트를 1로, 같으면 0으로 결정합니다. 이후 나머지 앞부분(n/10)에 대해 재귀 호출을 반복하고, 각 호출 결과에 10을 곱해 자릿수를 왼쪽으로 한 칸씩 밀어줍니다. 이 과정이 n이 0이 될 때까지 반복되면 전체 그레이 코드가 완성됩니다.

이 알고리즘의 시간 복잡도는 입력 이진수의 자릿수를 d라고 할 때 O(d)로, 매우 효율적입니다.