숫자의 패리티 검사: 이진수 1의 개수로 홀수·짝수 패리티 판별하기

숫자의 패리티(parity)는 해당 숫자를 이진수로 나타냈을 때 포함된 1의 개수를 기준으로 결정됩니다. 1의 개수가 홀수이면 홀수 패리티(odd parity), 짝수이면 짝수 패리티(even parity)라고 부릅니다.

컴퓨터 메모리의 모든 숫자는 이진수 형태로 저장되기 때문에 비트 시프트 연산으로 각 비트에 손쉽게 접근할 수 있습니다. 따라서 주어진 숫자를 한 비트씩 오른쪽으로 시프트하면서 최하위 비트(LSb)가 1인지 확인해 1의 총개수를 세면, 그 숫자의 패리티를 구할 수 있습니다.

입력 및 출력 예시

입력:
숫자: 5
이진수 표현: (101)

출력:
5의 패리티는 홀수(Odd)입니다.

알고리즘: findParity(n)

입력: 패리티를 검사할 숫자 n

출력: 해당 숫자가 짝수 패리티인지 홀수 패리티인지 여부

1. count := 0, temp := n 으로 초기화한다.
2. temp >= 2 인 동안 다음을 반복한다.
   - temp의 최하위 비트(LSb)가 1이면 count를 1 증가시킨다.
   - temp를 1비트 오른쪽으로 시프트한다.
3. count가 홀수이면 "홀수 패리티"를 출력하고,
   그렇지 않으면 "짝수 패리티"를 출력한다.

C++ 구현 예제

#include <iostream>
using namespace std;

bool findParity(int n) {
    int count = 0;
    int temp = n;

    while (temp >= 2) {
        if (temp & 1)       // LSb가 1이면 카운트 증가
            count++;
        temp = temp >> 1;   // 숫자를 1비트 오른쪽으로 시프트
    }
    return (count % 2) ? true : false;
}

int main() {
    int n;
    cout << "Enter a number: "; cin >> n;
    cout << "Parity of " << n << " is " << (findParity(n) ? "Odd" : "Even");
}

실행 결과

Enter a number: 5
Parity of 5 is Odd

더 효율적인 방법: 커니핸(Kernighan) 알고리즘

위 방법은 숫자의 모든 비트를 처음부터 끝까지 검사하므로 시간 복잡도가 O(log n)입니다. 반면 n & (n - 1) 연산을 활용하는 브라이언 커니핸 알고리즘은 값이 1인 비트의 개수만큼만 반복하기 때문에, 1의 개수가 적은 숫자일수록 훨씬 빠르게 패리티를 계산할 수 있습니다.