C++로 숫자의 패리티(Parity) 구하기: 비트 연산을 활용한 효율적인 방법

이 튜토리얼에서는 C++를 사용하여 주어진 숫자의 패리티(parity)를 찾는 프로그램을 다룹니다.

패리티란 숫자를 이진수로 표현했을 때 1의 개수가 홀수인지 짝수인지를 나타내는 값입니다. 예를 들어, 이진수에서 1의 개수가 홀수이면 '홀수 패리티', 짝수이면 '짝수 패리티'라고 합니다.

패리티 계산 알고리즘

가장 효율적인 방법은 비트 연산을 활용하는 것입니다. n & (n - 1) 연산은 n의 가장 오른쪽에 있는 1비트를 제거하는 성질을 가지고 있습니다. 이 연산을 반복적으로 수행하면서 패리티 값을 뒤집으면, 전체 1비트의 개수가 홀수인지 짝수인지 쉽게 판별할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
#define bool int
using namespace std;

// 주어진 숫자의 패리티를 구하는 함수
bool getParity(unsigned int n) {
    bool parity = 0;
    while (n) {
        parity = !parity;      // 1비트를 발견할 때마다 패리티 값 반전
        n = n & (n - 1);       // 가장 오른쪽의 1비트 제거
    }
    return parity;
}

int main() {
    unsigned int n = 7;
    cout << "Parity of no " << n << ": " << (getParity(n) ? "Odd" : "Even");
    getchar();
    return 0;
}

실행 결과

Parity of no 7: Odd

동작 원리 설명

숫자 7은 이진수로 111이며, 1비트가 3개입니다. 위 코드는 다음과 같이 동작합니다.

1. 111 → 110 (1비트 하나 제거, 패리티 반전)
2. 110 → 100 (1비트 하나 제거, 패리티 반전)
3. 100 → 000 (1비트 하나 제거, 패리티 반전)

반복문이 세 번 실행되어 패리티 값이 최종적으로 1이 되며, 이는 1의 개수가 홀수임을 의미합니다. 따라서 결과는 'Odd'가 출력됩니다.

시간 복잡도

이 방법의 시간 복잡도는 O(k)입니다. 여기서 k는 숫자에 포함된 1비트의 개수입니다. 모든 비트를 하나씩 검사하는 O(log n) 방식보다 1비트의 수만큼만 반복하므로 더 효율적입니다. 이러한 특성 덕분에 에러 검출 코드나 데이터 무결성 확인 등 패리티가 자주 사용되는 분야에서 널리 활용됩니다.