[JAVA] XOR 연산자 ^ 에 대해 ( feat. 백준 - XOR (12844번))

XOR 연산이란?

- XOR 연산이란 쉽게 말해 다르면 참을 반환한다.

- 아래 예시를 보자. 

(1 = 참 , 0 = 거짓)

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0 

 

- 연산자로 표시하면 

0^0 = 0

0^1 = 1

1^0 = 1

1^1 = 1

 

- 이진수의 하나의 비트가 아닌 여러비트로 예시를 들어보자.

십진수 13 과 십진수 8은 각각 이진수로 1101 과 1000 로 나타낼수 있다. 

 

1 1 0 1

1 0 0 0

--------

0 1 0 1  = 5

 

따라서 13 ^ 8 = 5 이다.

 

 

XOR 연산 성질

ko.wikipedia.org/wiki/XOR_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

XOR 교체 알고리즘 - 위키백과, 우리 모두의 백과사전

 

1. 교환법칙 성립

8 ^ 13 = 13 ^ 8 이다. 연산의 위치는 중요하지 않다.

 

2. 결합 법칙 성립

(1^2)^3 = 1^(2^3) 이다.  연산의 순서는 상관없다.

 

위 결합법칙과 교환법칙의 성립으로 인해 XOR연산에 대해 세그먼트 트리를 구성할 수 있다.

3. 항등원은 0 이다. (중요)

2 = 2

2^2 = 0

2^2^2 = 2

2^2^2^2 = 0 

...

2^0 = 2

X^0 = X 

 

서로 같은수를 XOR연산하면 0 이 나오는데 0 은 어떠한 수 X와 연산을 하면 X가 나옴을 보장받는다. 

이런 항등원의 성질을 이용해 세그먼트 트리에 쿼리를 날릴 수 있다.

 

 

 

www.acmicpc.net/problem/12844

12844번: XOR

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


class Main{

    static int n;
    static int[] base;

    static int[] tree;
    static int[] lazy;
    static Fs fs = new Fs();

    public static void updateLazy(int node,int st ,int ed){
        if(lazy[node]!=0){ // 현재 노드를 업데이트해야한다면 ?
            if((ed-st+1)%2 == 1 ){ // 홀수개일때만 업데이트하자
                tree[node] ^= lazy[node];
            }

            if(st != ed){ // 마지막 노드가 아니면 전파
                lazy[node*2] ^= lazy[node];
                lazy[node*2+1] ^= lazy[node];
            }

        }
        lazy[node] = 0;
    }

    public static void update(int node,int st,int ed,int left,int right,int val){
        updateLazy(node,st,ed);
        if(st>right || ed < left) return;
        if(left<=st && ed <= right){
            if((ed-st+1)%2==1){
                tree[node] ^= val;
            }
            if(st != ed){
                lazy[node*2] ^= val;
                lazy[node*2 + 1 ] ^= val;
            }

            return;
        }
        update(node*2,st,(st+ed)/2,left,right,val);
        update(node*2+1,(st+ed)/2+1,ed,left,right,val);
        tree[node] = tree[node*2] ^ tree[node*2+1];
    }

    public static int query(int node,int st,int ed,int left,int right){
        updateLazy(node,st,ed);
        if(st > right || ed < left) return 0; // 0 은 항등원임
        if(left<=st && ed<=right) return tree[node];
        return query(node*2,st,(st+ed)/2,left,right)
                ^query(node*2+1,(st+ed)/2+1,ed,left,right);

    }


    public static int init(int node ,int st ,int ed){
        if(st == ed){
            return tree[node] = base[st];
        }
        else{
            return tree[node] = init(node*2,st,(st+ed)/2)
                    ^ init(node*2+1,(st+ed)/2+1,ed);
        }
    }

    public static void main(String[] args) throws IOException{
        n = fs.nInt();
        base = new int[n];
        for(int i=0;i<n;i++){
            base[i] = fs.nInt();
        }

        int size = 1;
        while(size < n){
            size <<= 1;
        } size <<= 1;

        tree = new int[size];
        lazy = new int[size];

        StringBuilder sb = new StringBuilder();

        init(1,0,n-1);
        int m = fs.nInt();
        while(m-- != 0){
            int cond = fs.nInt();
            int t1 = fs.nInt();
            int t2 = fs.nInt();
            if(cond == 1){
                int val = fs.nInt();
                update(1,0,n-1,t1,t2,val);
            }
            else{
                sb.append(query(1,0,n-1,t1,t2)).append('\n');
            }
        }

        System.out.println(sb);


    }

    static class Fs{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nInt() throws IOException {
            if(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }
    }
}