C++에서 숫자의 패리티를 효율적으로 구하는 방법

C++ 프로그래밍에서 숫자의 패리티(parity)는 해당 수를 이진수로 표현했을 때 1로 설정된 비트의 개수가 짝수인지 홀수인지를 나타내는 속성입니다. 이 튜토리얼에서는 반복문 없이 비트 연산만으로 숫자의 패리티를 빠르게 구하는 프로그램을 작성해 보겠습니다.

패리티 계산 원리

모든 비트를 하나씩 검사하는 방법은 비효율적입니다. 대신 XOR(^) 연산과 오른쪽 시프트(>>) 연산을 조합하면 32비트 정수의 패리티를 단 5단계, 즉 상수 시간 O(1) 안에 구할 수 있습니다.

핵심 아이디어는 비트 범위를 절반씩 줄여 가면서 서로 XOR로 접는(folding) 것입니다. 다음 코드가 그 과정을 보여줍니다.

int b;
b = n ^ (n >> 1);
b = b ^ (b >> 2);
b = b ^ (b >> 4);
b = b ^ (b >> 8);
b = b ^ (b >> 16);

모든 연산이 끝나면 결과값의 최하위 비트(LSB)에 원래 숫자의 패리티가 담기게 됩니다. 따라서 최하위 비트가 1이면 홀수 패리티(odd parity), 0이면 짝수 패리티(even parity)입니다.

C++ 예제 코드

지금까지 설명한 내용을 바탕으로 작성한 전체 코드는 다음과 같습니다.

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

void findParity(int n) {
    int b;
    b = n ^ (n >> 1);
    b = b ^ (b >> 2);
    b = b ^ (b >> 4);
    b = b ^ (b >> 8);
    b = b ^ (b >> 16);

    if ((b & 1) == 0) {
        cout << "Even Parity" << endl;
    }
    else {
        cout << "Odd Parity" << endl;
    }
}

int main() {
    int n = 15;
    findParity(n);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Even Parity

n = 15는 이진수로 1111이며, 1로 설정된 비트가 총 4개, 즉 짝수 개이므로 짝수 패리티로 판별됩니다.

마무리

이 기법은 루프 없이 고정된 횟수의 비트 연산만으로 32비트 정수의 패리티를 구할 수 있어 성능이 중요한 환경에서 특히 유용합니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.