먼저 비트연산을 이용해서 임시변수 없이 두 정수를 교환하는 방법을 간단하게 알아보겠습니다.
다음 예제 코드를 보세요.
다음의 코드가 두 정수의 값을 바꿔주는 역할을 하는데요,
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
지금부터 어째서 이 코드가 두 정수가 교환되는 결과를 가져오는지 증명을 해 보겠습니다.
이 코드는 비트 XOR연산자의 다음과 같은 두 특성을 이용하여 만든 코드입니다.
1. x ^ x = 0
2. x ^ 0 = x
이 특성을 이용해서 두 정수를 교환하는 코드를 증명해 봅시다.
3. a' = a ^ b;
4. b' = a' ^ b;
5. a'' = a' ^ b'
3과 4를 정리하여 4를 다시 쓰면
6. b' = a ^ b ^ b;
6에 1을 적용하면(비트 XOR은 결합법칙이 성립하므로 뒤부터 계산해도 결과는 같습니다.)
7. b' = a ^ 0;
7에 2를 적용하면
8. b' = a;
3과 5를 정리하여 5를 다시 쓰면
9. a'' = a ^ b ^ b';
8과 9를 정리하여 9를 다시 쓰면
10. a'' = a ^ b ^ a;
비트 XOR은 교환법칙이 성립하므로 이를 이용해 10을 다시 쓰면
11. a'' = b ^ a ^ a;
11에 마찬가지로 1과 2를 적용하여 정리하면
12. a'' = b;
∴ 8과 12에 따라서 'b = a, a'' = b가 되어 두 정수가 교환됩니다.
그냥 끝내기엔 왠지 아쉬우니 실행 결과도 봐봅시다.
