[이론] 쉽게 정리한 xor

XOR의 정의

다르면 1, 같으면 0입니다.

A	B	A ^ B
1	1	0
1	0	1
0	1	1
0	0	0

XOR의 특징

아래의 세 가지 특징을 기억하고 있으면 좋습니다.

1. 교환법칙
   • a^b=b^a
   • a^b^c = c^b^a
2. a^a = 0
3. a^0 = a

활용 1. 추가 변수 선언 없이 두 변수의 값 바꾸기

a != b인 경우 두 값을 바꿀 수 있습니다. 실수로 a == b인 경우 아래의 방법을 적용하면 a와 b가 모두 0이 됩니다.

a ^= b;
b ^= a;
a ^= b;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int a = 1, b = 2;
    cout << a << "," << b << "\n"; // 1, 2

    a = a ^ b; // a = a ^ b
    b = b ^ a; // b = b ^ (a ^ b ) = a
    a = a ^ b; // a = (a ^ b) ^ a = b
    cout << a << "," << b << "\n"; // 2, 1

    a ^= b;
    b ^= a;
    a ^= b;
    cout << a << "," << b << "\n"; // 1, 2

    return 0;
}

백준 문제

https://www.acmicpc.net/problem/3009

import sys
from collections import deque

# 배열 초기화
# MAX = 15
# arr = [[0] * MAX for _ in range(MAX)]
# arr = [0] * MAX

# TestCase
# for _ in range(int(input())):

# 배열 접근
# for r in range(MAX):
#     for c in range(MAX):

# 파일 입력
# sys.stdin = open('input.txt', 'r')

x, y = map(int, input().split())
a, b = map(int, input().split())
x ^= a
y ^= b
a, b = map(int, input().split())
x ^= a
y ^= b
print(x, y)

활용 2. 문제풀이

아래 링크에 XOR을 사용한 문제 풀이를 적어두었습니다!

영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!

결론

Success Notice: 수고하셨습니다.

Reference

• 알고리즘 소학회 코알라