[4. 기본자료형] 4.1 패리티 계산하기
[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
[4. 기본자료형] 단원의 기본 셋팅은 다음과 같다.
Q 4.1 패리티 계산하기
2진수의 패리티는 1로 세팅된 비트의 개수와 같다.
즉, 1이 홀수개 이면 1을 출력, 짝수개 이면 0을 출력하는 코드를 작성하라
Ex) 1011 => 1, 10001000 => 0
1. 단순한 방법으로는 1로 세팅된 모든 비트의 개수를 파악하는것 이다.
1이 짝수인지 홀수인지만 판별하자.
코드는 다음과 같다.
위 코드는 비트수 만큼 연산진행 복잡도가 증가한다.
// x>>1; 은 2로 나누는 효과를 갖는 shift연산이다.
2. 문제에서 요구하는것은 1과 0을 출력하는 것이다.
시간복잡도를 조금더 낮추는 방법으로 하위 비트를 한번에 지우는 것이다.
x & (x-1)연산을 하게되면 1로 세팅된 비트중에 가장 낮은 비트를 지울수 있다.
예를들면 x == 00101100 일때 x-1 == 00101011 과 같이 표현할 수 있다.
x ) 00101100
x-1) & 00101011
------------------------
00101000
위의 방법으로 1이 모두 사라질때 까지 연산을 시도하고,
result 를 xor 연산을 해 홀수일때 1 짝수일때 0를 출력한다.
이때 시간복잡도는 O(k) (단,k는 1의 갯수) 이다. 코드는 다음과 같다.
코딩 결과는 1.과 같다.
3. 현재 사용하는 자료형이 unsigned (__int64 또는 long long) 을 사용하고 있다.
64비트의 패리티 값을 모두 저장하기에는 크기가 크다.
따라서 64비트를 16비트 4개로 나누어 계산하려고 한다.
예시로 8비트를 2비트 4개로 나누면 다음과 같다.
11001010 일때 (11) (00) (10) (10) 이고, 이때 각각의 패리티 비트는 <0, 0, 1, 1> 이다.
0011의 패리티비트는 0이다. 따라서 11001010도 0이다. 라는 점을 이용한다.
이때 시간복잡도는 O(n/L), (단,L은 해시테이블의 키값, n은 전체 비트의 수) 이다.
소스코드는 다음과 같다.
코딩 결과는 1.과 같다.
XOR의 결합법칙과 교환법칙이 만족한다는 점을 이용해보려고 한다.
예를 들어 8비트 11010111를 (1101) ^ (0111) 연산을 하려고 한다.
1101
^ 0111
--------------
1010
1010을 또 (10)^(10)연산을 한다.
10
^ 10
--------
00 => 즉 00의 패리티와 같다.
결국 전부 xor연산을 하고 마지막 2개의 비트로 최종 패리티 값을 구할수 있는 점을 이용한다.
이때 시간복잡도는 O(log n) 이다. 소스코드는 다음과 같다.
코딩 결과는 1.과 같다.