AlgoSpot DRAWRECT - XOR 비트 연산으로 코딩하기

"AlgoSpot DRAWRECT 문제 풀이"에 대한 마지막 코드 예제 입니다. 이번에는 절차지향 방식의 코드를 개선해 XOR 비트 연산자의 원리를 이용해 if 제어문 조차 사용하지 않는 short code를 소개하고자 합니다. XOR 비트 연산자 사용에 대한 아이디어는 이은택님이 제안해 주셨고, 이은택님의 샘플 코드 또한 참고해 보시면 좋겠습니다. XOR 연산자를 활용한 기법을 소개하는 이유는 컴퓨터 하부 구조의 동작 방식 (2진수 기반의 컴퓨터 원리 등)과 수학적 논리(혹은 공식)를 잘 이해할 경우, 더 할 나위 없는 성능을 발휘하는 가장 짧은 코드를 작성할 수 있다는 것을 보여 드리기 위함입니다.

▶ 배타적 논리합

배타적 논리합 (exclusive or)은 수리 논리학에서 주어진 2개의 명제 가운데 1개만 참일 경우를 판단하는 논리 연산입니다. 약칭으로 XOR, EOR, EXOR라고도 씁니다. 연산자는 ⊻ (유니코드: U+22BB)입니다. 혼돈이 되지 않을 경우, XOR, xor ⊕ (유니코드: U+2295), +、≠ 라고도 씁니다. (위키백과 배타적 논리합 참조)

배타적 논리합의 "진리표"는 아래와 같습니다.

명제 P	명제 Q	P ⊕ Q
참	참	거짓
참	거짓	참
거짓	참	참
거짓	거짓	거짓

▶ XOR (Exclusive OR) 비트 연산

XOR 연산은 두 값의 각 자릿 수를 비교해, 값이 같으면 0, 다르면 1을 계산하는 연산입니다. XOR 연산은 비트 단위로 이루어집니다.

0101

XOR    0011

-----------

       = 0110

 

C or C++ 언어에서 XOR 비트 연산자는 ^ (caret) 문자를 사용합니다.

   x = y ^ z;

▶ XOR 비트 연산을 이용한 동일 값 제거

XOR 비트 연산자를 활용하면, 여러 개의 값 중에서 동일한 값들을 제거할 수 있습니다. 예를 들어, 3개의 값이 존재하고 그 중에서 2개의 값이 동일하고 나머지 하나의 값이 다른 경우, XOR 비트 연산 2번을 통해 나머지 하나의 다른 값을 추출할 수 있습니다. 예를 들어, 십진수 12, 7, 7 등 3개의 값을 2번에 걸쳐 XOR 연산을 수행하는 과정과 그 결과는 다음과 같습니다. 연산 순서에 상관없이 하나의 다른 값이 얻게 되는 것을 확인할 수 있습니다.

▶ XOR 비트 연산을 short code 예시

#include <stdio.h>
#include <stdlib.h>

/* x,y 좌표를 표현하는 점(point) 구조체를 정의한다. */ 
typedef struct {
   int x;
   int y;
} point;
 

int main(int argc, char *argv[]) {
	
	// 테스트 케이스 반복 횟수 및 좌표 변수 생성 및 초기화 
	int cnt = 0;
	point p1 = {0, 0};
	point p2 = {0, 0};
	point p3 = {0, 0};
	point p4 = {0, 0};
	
	// 테스트 케이스 반복 횟수 입력. 
	int testCaseCount;
	printf("Input test case number : ");
	scanf("%d", &testCaseCount); 
	
	// 입력 받은 테스트 케이스 수만큼 반복 처리... 
	for(cnt=0; cnt<testCaseCount; cnt++) {
		
		// ----- pt, p3, p3 등 3개의 좌표 값 입력 -----
		printf("Input p1 (x, y) : ");
		scanf("%d %d", &p1.x, &p1.y);
		printf("p1.x = %d, p1.y = %d\n", p1.x, p1.y);
		
		printf("Input p2 (x, y) : ");
		scanf("%d %d", &p2.x, &p2.y);
		printf("p2.x = %d, p2.y = %d\n", p2.x, p2.y);
		
		printf("Input p3 (x, y) : ");
		scanf("%d %d", &p3.x, &p3.y);
		printf("p3.x = %d, p3.y = %d\n", p3.x, p3.y);
		
		// ----- 4번째 좌표 계산 및 출력 ----- 

		// p4.x 좌표 계산 
		p4.x = p1.x ^ p2.x ^ p3.x;
		// p4.y 좌표 계산 
		p4.y = p1.y ^ p2.y ^ p3.y;

		// p4 좌표 출력 
		printf("\nResult p4.x = %d, p4.y = %d", p4.x, p4.y );
	}
	
	return 0;
}