어떤 2진수에 존재하는 1의 개수가 홀수개면 패리티는 1이 되고, 짝수개면 0이 된다.
예를 들어, 14=1110(2)에는 1이 홀수개 있으므로 패리티는 1이 된다.
1️⃣ 만약 임의의 64비트 2진수의 패리티를 구하는 프로그램을 작성한다면, 가장 먼저 떠올릴 수 있는 단순한 방법은 1이 홀수개인지, 짝수개인지 모든 비트를 검사하는 것이다.
검사(x & 1)하는 비트값이 0이든 1이든 하나씩 확인하므로 이 방법은 입력된 2진수의 크기 n에 따라 O(n)이 걸린다.
public static short getParity(long x) {
short result = 0;
while (x != 0) { // x가 0이 될 때까지 오른쪽 시프트 할 예정
result ^= (x & 1); // x의 LSB가 1이면 초기값(0) XOR 1이 result에 저장
x = x >>> 1;
}
return result;
}
/*
result의 초기값은 0이다.
만약 x의 LSB가 1이면 result = 0 XOR 1이 되어 result에 1이 저장된다.
그 이후 x가 0이 되기 전까지 아래 계산을 반복하며 1이 나올 때마다 result값이 반전된다.
1. x의 다음번 비트가 0이면 result = 1 XOR 0이 되어 result가 1로 유지된다. (홀)
2. x의 다음번 비트가 1이면 result = 1 XOR 1이 되어 result가 0으로 변한다. (짝)
*/
2️⃣ 약간 더 나은 방법으로는, 0으로 세팅된 비트들을 무시하고 1의 개수만 확인하는 방법이 있다. 이 방법은 1로 세팅된 비트의 개수에 따라 O(1)부터 O(n)까지 소요된다. 1로 세팅된 비트의 개수를 k라고 한다면, O(k)가 걸리는 셈이다.
구체적인 방법은 입력값과 입력값에서 1을 뺀 값을 AND 연산하는 것을 반복하며 홀/짝을 세는 것이다. 예를 들어, 10 = 1010(2)가 입력이라면 10 & (10-1) = 1010(2) & 1001(2) = 1000(2)가 되어 가장 낮은 자릿수에 위치한 1이 0으로 바뀐다. (홀) 그리고 이를 반복하면, 1000(2) & 0111(2) = 0이 되어 루프가 종료된다. (짝, 따라서 패리티는 0)
이 방법을 코드로 작성하면 아래처럼 된다.
public static short getParity(long x) {
short result = 0;
while (x != 0) {
x = x & (x - 1);
result ^= 1;
}
return result;
}
3️⃣ 위 두 방법들은 현실에서 패리티를 구할 때 쓰기에는 너무 많은 연산이 필요하다.
주어진 입력을 절반 길이로 나눈 이진수를 서로 XOR한 수의 패리티는 원래 입력의 패리티와 같은데, 이는 XOR이 결합법칙과 교환법칙을 만족하는 연산이기 때문이다.
예를 들어, 234 = 11101010(2)를 절반 길이로 나누면 1110과 1010이 되고, 둘을 XOR하면 0100이 된다. 11101010에는 1이 홀수개 포함되어 있는데, 절반씩 나누면 결국 둘 중 하나에는 1이 홀수개 존재한다. 이어서 0100을 또 절반으로 나누면 01과 00이 되고, 둘을 XOR하면 01이 된다. 마지막으로 1만 남으므로 234의 패리티는 1이다. 이 성질을 이용하면 연산 횟수를 많이 줄일 수 있다.
* 두 개 이상의 연산자가 존재하는 식에서, 앞쪽의 연산을 먼저 수행한 값과 뒤쪽의 연산을 먼저 수행한 결과가 항상 같을 때, 그 연산자는 결합법칙을 만족한다고 한다. (덧셈, 곱셈, 합집합, 교집합, OR, AND, XOR 등)
* 이항연산자의 입력값의 순서를 바꾸어도 결과가 같을 때, 그 연산자 교환법칙을 만족한다고 한다. (덧셈, 곱셈, 합집합, 교집합, OR, AND, XOR 등)
이 알고리즘은 64비트(2^6) 입력을 처리하는 데 시프트 연산 log₂64 = 6회가 필요하므로 시간복잡도는 O(log₂ n)이다.
public static short getParity(long x) {
x = x ^ (x >>> 32);
x = x ^ (x >>> 16);
x = x ^ (x >>> 8);
x = x ^ (x >>> 4);
x = x ^ (x >>> 2);
x = x ^ (x >>> 1);
return (short) (x & 1);
}