XOR 연산 정리

백준에서 재미있는 XOR 관련 문제를 발견하여 XOR 연산을 간단하게 정리해보았다.

[25036번] 연속 XOR
https://www.acmicpc.net/problem/25306

XOR 연산은 bitwise 연산 중 하나로 비트가 같으면 0, 다르면 1을 결과로 가진다.

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	1

위의 성질을 이용하여 다음과 같은 성질 역시 성립한다.

1. x ^ 0 = x

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	1

2. x ^ x = 0

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	1

3. x ^ y = y ^ x (commutativity)

x	y	x ^ y	y ^ x
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

위의 1,2,3번 성질을 이용하면 아래와 같은 계산할 수 있다.

a ^ b ^ c ^ a ^ b     # Commutativity
= a ^ a ^ b ^ b ^ c     # Using x ^ x = 0
= 0 ^ 0 ^ c             # Using x ^ 0 = x (and commutativity)
= c

In-Place Swapping

지금까지는 두 변수 x,y 에 저장된 값을 서로 바꿀 때 중간에 변수를 하나 두는 방법으로 가능했다(Python의 경우 예외).

void swap(int x, int y) {
	int tmp = x;
    x = y;
    y = tmp;
}

이 방법을 XOR 연산의 2번 성질을 사용하여 추가 변수없이 swap 할 수 있다.

void swap(int x, int y) {
	x ^= y;  // (x^y, y)
    y ^= x;  // (x^y, x)
    x ^= y;  // (y, x)
}

[1,N] 연속 XOR

1,2,...,N 까지의 수를 연속으로 XOR 연산을 취한 값이 궁금하다고 해보자.

풀이 1.

#include <bits/stdc++.h>

using namespace std;

int N;

int XOR(int n) {
	if(n == 0) return 0;
    
    int res = 0;
    for(int i=1;i<=n;++i) {
    	res ^= i;
    }
    
    return res;

int main() {
	scanf("%d", &N);
    printf("%d\n", XOR(N));
    
    return 0;
}

Time complexity : O(N)
Space complexity : O(1)

풀이 2.

XOR 연산의 성질을 이용한 풀이로 XOR 연산의 경우 4로 나눈 나머지를 이용하여 O(1)의 시간복잡도 안에 [1,N] 연속 XOR 연산을 할 수 있다.

#include <bits/stdc++.h>

using namespace std;

int N;

int XOR(int n) {
	if(n % 4 == 0) return n;
    if(n % 4 == 1) return 1;
    if(n % 4 == 2) return n+1;
    if(n % 4 == 3) return 0;
}

int main() {
	scanf("%d", &N);
    printf("%d\n", XOR(N));
    
    return 0;
}

Time complexity : O(1)
Space complexity : O(1)

아니 이게 무슨 말인가?? 실상은 아래와 같다.

Number Binary-Repr  XOR-from-1-to-n
1         1           [0001]
2        10           [0011]
3        11           [0000]  <----- We get a 0
4       100           [0100]  <----- Equals to n
5       101           [0001]
6       110           [0111]
7       111           [0000]  <----- We get 0
8      1000           [1000]  <----- Equals to n
9      1001           [0001]
10     1010           [1011]
11     1011           [0000] <------ We get 0
12     1100           [1100] <------ Equals to n

위와 같은 패턴이 반복되면서 [1,N] 연속 XOR을 무려 O(1) 시간 복잡도에 계산 할 수 있었던 것이다!

[L,R] 연속 XOR

위에서 [1,N] 연속 XOR을 O(1) 시간 복잡도에 구할 수 있다는 사실을 배웠다. 이것과 XOR의 2번 성질을 이용하여 [L,R] 범위 연속 XOR을 O(1) 시간 복잡도에 구해보겠다.

#include <bits/stdc++.h>

using namespace std;

int L,R;

int XOR(int n) {
	if(n % 4 == 0) return n;
    if(n % 4 == 1) return 1;
    if(n % 4 == 2) return n+1;
    if(n % 4 == 3) return 0;
}

int main() {
	scanf("%d %d", &L, &R);
    printf("%d\n", XOR(L-1) ^ XOR(R));
    
    return 0;
}

1. [1, L-1] 연속 XOR을 O(1) 시간 복잡도로 계산한다.
2. [1, R] 연속 XOR을 O(1) 시간 복잡도로 계산한다.
3. {1 ^ 2 ^ ... ^ (L-1)} ^ {1 ^ 2 ^ ... ^ (L-1) ^ L ^ (L+1) ^ ... ^ R}
	= L ^ (L+1) ^ ... ^ R 
# 2번 성질에 의하여 중복되는 1...L-1은 XOR 연산은 모두 0이 된다.

Reference

https://www.geeksforgeeks.org/calculate-xor-1-n/
https://www.geeksforgeeks.org/find-xor-of-numbers-from-the-range-l-r/
https://florian.github.io/xor-trick/