이 글에서는 주어진 숫자 N의 패리티(parity)를 구하는 C++ 프로그램을 살펴보겠습니다.
패리티란 무엇인가?
패리티는 숫자의 이진수 표현에서 설정된 비트(set bit), 즉 '1'의 개수를 의미합니다.
- 이진수 표현에서 '1'의 개수가 짝수이면 짝수 패리티(Even Parity)
- 이진수 표현에서 '1'의 개수가 홀수이면 홀수 패리티(Odd Parity)
알고리즘: XOR 폴딩 기법
주어진 숫자가 N일 때, 다음과 같은 연산을 순서대로 수행합니다.
- y = N ^ (N >> 1)
- y = y ^ (y >> 2)
- y = y ^ (y >> 4)
- y = y ^ (y >> 8)
- y = y ^ (y >> 16)
여기서 사용된 원리는 XOR 폴딩(XOR Folding) 기법입니다. 각 단계마다 시프트하는 비트 수가 1, 2, 4, 8, 16으로 두 배씩 늘어나면서 유효 비트 범위가 절반으로 줄어듭니다. 즉, 32비트 정수 기준으로 단 5번의 연산만으로 모든 비트의 정보가 최하위 비트 하나로 응축됩니다.
모든 연산이 끝난 후 y의 가장 오른쪽 비트(최하위 비트)가 해당 숫자의 패리티를 나타냅니다.
- 최하위 비트가 1이면 → 홀수 패리티
- 최하위 비트가 0이면 → 짝수 패리티
이 방법은 비트를 하나씩 순회하며 세는 일반적인 방식(O(n))보다 훨씬 효율적이며, O(log n) 시간 복잡도로 매우 빠르게 동작합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
bool calc_parity(int N) {
int y;
y = N ^ (N >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);
// 최하위 비트 확인
if (y & 1)
return 1;
return 0;
}
int main() {
int n = 1345;
int result = calc_parity(n);
if (result == 1)
cout << "Odd Parity" << endl;
else
cout << "Even Parity" << endl;
return 0;
}실행 결과
Even Parity
동작 원리 검증
예제의 숫자 1345를 이진수로 변환하면 10101000001이 됩니다. 이 숫자에는 '1'이 총 4개 있으므로 짝수 개수에 해당하고, 따라서 프로그램은 Even Parity(짝수 패리티)를 출력하게 됩니다.
마무리
XOR과 시프트 연산을 조합한 이 기법은 반복문 없이 상수 번의 연산만으로 패리티를 판별할 수 있는 우아한 방법입니다. 임베디드 시스템이나 에러 검출 코드(CRC 등)처럼 성능이 중요한 환경에서 특히 유용하게 활용됩니다.