C, C++ - 임시 변수 없이 변수 바꾸기 (Swap Two Numbers without using the Third Variable)

C, C++ 전체 링크

삼성 C형 전체 링크

 

long long int 타입 a, b 변수를 교체해보자.

#include <stdio.h>

typedef long long int ll;

int main(void)
{
	ll a = 1234123412341234;
	ll b = 5678567856785678;

	printf("a : %lld\n", a);
	printf("b : %lld\n", b);

	putchar('\n');
	ll tmp = a;
	a = b;
	b = tmp;

	printf("a : %lld\n", a);
	printf("b : %lld\n", b);

	return 0;
}

 

값이 잘 변경된 것을 알 수 있다.

 

XOR Swap 알고리즘을 이용하면 변수를 추가하지 않고 아래와 같이 간결하게 두 변수를 교환할 수 있다.

a ^= b ^= a ^= b;

참고로 이 방법이 tmp를 사용하는 것보다 특별히 빠른 것은 아니다.

 

코드 실행결과는 tmp를 사용한 것과 같다.

---

char 8개 한 번에 교체하기

 

하지만 위의 방법을 응용하면 char 변수 8개를 한꺼번에 교체할 수 있다.

char 8개는 long long과 크기가 같기 때문에 통째로 메모리를 교체할 수 있어 성능이 향상된다.

아래와 같이 타입 캐스팅을 이용해서 배열을 통째로 교체한다.

#include <stdio.h>

typedef long long int ll;

int main(void)
{
	char arr1[8];
	char arr2[8];

	for (int i = 10; i < 18; i++) arr1[i - 10] = i;
	for (int i = 20; i < 28; i++) arr2[i - 20] = i;

	for (int i = 0; i < 8; i++) printf("%d ", arr1[i]); putchar('\n');
	for (int i = 0; i < 8; i++) printf("%d ", arr2[i]); putchar('\n');

	putchar('\n');

	ll& cp1 = *(ll*)arr1;
	ll& cp2 = *(ll*)arr2;

	cp1 ^= cp2 ^= cp1 ^= cp2;

	for (int i = 0; i < 8; i++) printf("%d ", arr1[i]); putchar('\n');
	for (int i = 0; i < 8; i++) printf("%d ", arr2[i]); putchar('\n');

	return 0;
}

 

arr1의 모든 값이 arr2의 값과 교체되었다.

 

c++이 아니라서 reference를 사용할 수 없다면, 포인터로도 가능하다.

ll* cp1 = (ll*)arr1;
ll* cp2 = (ll*)arr2;

(*cp1) ^= (*cp2) ^= (*cp1) ^= (*cp2);

 

전체 코드는 다음과 같다.

#include <stdio.h>
#include <time.h>

typedef long long int ll;

int main(void)
{
	ll a = 1234123412341234;
	ll b = 5678567856785678;

	printf("a : %lld\n", a);
	printf("b : %lld\n", b);

	putchar('\n');

	a ^= b ^= a ^= b;

	printf("a : %lld\n", a);
	printf("b : %lld\n", b);
	putchar('\n');

	/* --------------------------------------- */

	char arr1[8];
	char arr2[8];

	for (int i = 10; i < 18; i++) arr1[i - 10] = i;
	for (int i = 20; i < 28; i++) arr2[i - 20] = i;

	for (int i = 0; i < 8; i++) printf("%d ", arr1[i]); putchar('\n');
	for (int i = 0; i < 8; i++) printf("%d ", arr2[i]); putchar('\n');

	putchar('\n');

	ll& cp1 = *(ll*)arr1;
	ll& cp2 = *(ll*)arr2;

	cp1 ^= cp2 ^= cp1 ^= cp2;
	
	//// pointer ver

	//ll* cp1 = (ll*)arr1;
	//ll* cp2 = (ll*)arr2;

	//(*cp1) ^= (*cp2) ^= (*cp1) ^= (*cp2);

	for (int i = 0; i < 8; i++) printf("%d ", arr1[i]); putchar('\n');
	for (int i = 0; i < 8; i++) printf("%d ", arr2[i]); putchar('\n');

	return 0;
}

 

하지만 굳이 ^ 연산으로 char 8개를 교체할 필요는 없다.

애초에 타입 캐스팅이 8개를 1개로 묶어주는 역할을 하므로 이후 교체는 tmp 변수로도 가능하다. (더 빠르다.)

ll& cp1 = *(ll*)arr1;
ll& cp2 = *(ll*)arr2;

ll tmp = cp1;
cp1 = cp2;
cp2 = tmp;

/* ------------------------ */

ll* cp1 = (ll*)arr1;
ll* cp2 = (ll*)arr2;

ll tmp = *cp1;
*cp1 = *cp2;
*cp2 = tmp;

---

성능 비교

 

Visual Studio에서 각각의 케이스에 대해서 시간을 측정해보자.

#include <stdio.h>
#include <time.h>

typedef long long int ll;

int main(void)
{
	{
		int TESTCASE = 1000;
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			char arr1[8];
			char arr2[8];

			for (int i = 10; i < 18; i++) arr1[i - 10] = i;
			for (int i = 20; i < 28; i++) arr2[i - 20] = i;

			for (int i = 0; i < 100000; i++)
			{
				for (int k = 0; k < 8; k++)
				{
					int tmp = arr1[k];
					arr1[k] = arr2[k];
					arr2[k] = tmp;;
				}
			}
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("TIME 1 : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{
		int TESTCASE = 1000;
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			char arr1[8];
			char arr2[8];

			for (int i = 10; i < 18; i++) arr1[i - 10] = i;
			for (int i = 20; i < 28; i++) arr2[i - 20] = i;

			for (int i = 0; i < 100000; i++)
			{
				for (int k = 0; k < 8; k++)
				{
					arr1[k] ^= arr2[k] ^= arr1[k] ^= arr2[k];
				}
			}
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("TIME 2 : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{
		int TESTCASE = 1000;
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			char arr1[8];
			char arr2[8];

			for (int i = 10; i < 18; i++) arr1[i - 10] = i;
			for (int i = 20; i < 28; i++) arr2[i - 20] = i;

			for (int i = 0; i < 100000; i++)
			{
				ll& cp1 = *(ll*)arr1;
				ll& cp2 = *(ll*)arr2;

				cp1 ^= cp2 ^= cp1 ^= cp2;
			}
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("TIME 3 : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{
		int TESTCASE = 1000;
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			char arr1[8];
			char arr2[8];

			for (int i = 10; i < 18; i++) arr1[i - 10] = i;
			for (int i = 20; i < 28; i++) arr2[i - 20] = i;

			for (int i = 0; i < 100000; i++)
			{
				ll* cp1 = (ll*)arr1;
				ll* cp2 = (ll*)arr2;

				(*cp1) ^= (*cp2) ^= (*cp1) ^= (*cp2);
			}
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("TIME 4 : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{
		int TESTCASE = 1000;
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			char arr1[8];
			char arr2[8];

			for (int i = 10; i < 18; i++) arr1[i - 10] = i;
			for (int i = 20; i < 28; i++) arr2[i - 20] = i;

			for (int i = 0; i < 100000; i++)
			{
				ll& cp1 = *(ll*)arr1;
				ll& cp2 = *(ll*)arr2;

				ll tmp = cp1;
				cp1 = cp2;
				cp2 = tmp;
			}
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("TIME 5 : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{
		int TESTCASE = 1000;
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			char arr1[8];
			char arr2[8];

			for (int i = 10; i < 18; i++) arr1[i - 10] = i;
			for (int i = 20; i < 28; i++) arr2[i - 20] = i;

			for (int i = 0; i < 100000; i++)
			{
				ll* cp1 = (ll*)arr1;
				ll* cp2 = (ll*)arr2;

				ll tmp = *cp1;
				*cp1 = *cp2;
				*cp2 = tmp;
			}
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("TIME 6 : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	return 0;
}

 

TIME 1 - 8개의 배열을 tmp 변수로 교체

TIME 2 - 8개의 배열을 tmp 변수 없이 각각 교체

TIME 3 - reference + ^ 연산으로 한 번에 교체

TIME 4 - pointer로 + ^ 연산으로 한 번에 교체

TIME 5 - reference + tmp 변수로 교체

TIME 6 - pointer + tmp 변수로 교체

 

TIME 2에서 변수 없이 비트 연산으로 교체하는 것이 그렇게 빠르지 않다는 것을 알 수 있다.

그 외에는 8개를 통째로 변경하므로 reference나 pointer를 사용하는 것이 성능이 더 좋다.

여기서 다시 ^= 연산을 굳이 쓸 필요없이 tmp로 교체해주면 더 빠른 속도가 나온다.

 

결론 :

tmp 변수를 추가해서는 안 될 정도로 메모리가 부족하지 않는 이상,

^로 swap하는 것은 성능 향상에 도움이 되지 않는다.