[Java]XOR 이용하기

 

XOR,XNOR 진리표(Truth Table)

XOR의 진리표는 다음과 같다.

 

 

그럼 사용할 수 있는 경우를 보자.

Arrays.asList(1,1,2,2,3,3,5,5,4)

위와 같은 List 가 있다.  

 

list 안에는 중복되는 1,2,3,5 가 있을 때 중복되지 않는 4의 값만 가져오고 싶다.

 

이러한 알고리즘을 풀 때는 다양한 방법이 존재하지만 XOR을 이용해서 간단히 풀 수 있다.

 

private Integer Solution(List<Integer> integers) {
        Integer i = 0;

        for (Integer integer : integers) {
            i ^=integer;
        }
        return i;
    }

이렇게 간단한 XOR 방법으로도 4를 추출할 수 있다.

좀 더 자세히 알아보자면

 

0 ^ 1 = 1

1 ^ 1 = 0

0 ^ 2 = 2

2 ^ 2 = 0

0 ^ 3 = 3

3 ^ 3 = 0

0 ^ 5 = 5

5 ^ 5 = 0

0 ^ 4 = 4  -> 최종 값 

 

물론 List에 값이 정렬되어 있지 않아도 결과는 4로 같다  ex(1,2,4,2,1,5,3,3,5) 

 

비트 값으로 보면( ->으로 보시면 됩니다)  초기값, 결괏값 

000(0) 001(1) ---- 001(1)

001(1) 010(2) ---- 011(3)

011(3) 100(4) ---- 111(7)

111(7) 010(2) ---- 101(5)

101(5) 001(1) ---- 100(4)

100(4) 101(5) ---- 001(1)

001(1) 011(3) ---- 010(2)

010(2) 011(3) ---- 001(1)

001(1) 101(5) ---- 100(4)

 

하지만 위와 같은 경우는 여태까지 개발을 하거나 공부하면서 쓴 경우는 별로 없던 거 같다. 

 

왜냐하면 배열안에 짝이 맞지 않는 숫자가 단 하나만 존재한 것을 본 적이 없기 때문이다.

 

예를 들어

Arrays.asList(1,1,2,2,3,3,5,5,123,124)

중복된 1,2,3,5 를 제외하고 123, 124 만 List로 담아서 Return 하고 싶다.

 

그래서 나는 왠만하면 이런 짝이 맞지 않는 경우에는 차라리 Set 이용해서 분류한다.

 

private Set<Integer> Solution(List<Integer> integers) {
        Set<Integer> dup = new HashSet<>();
        Set<Integer> noDup = new HashSet<>();
        for (Integer integer : integers) {
            if (dup.contains(integer)) {
                noDup.remove(integer);
            } else {
                noDup.add(integer);
            }
            dup.add(integer);
        }
        return noDup;
    }

결괏값

 

 

 

그림 출처: www.ktword.co.kr/abbr_view.php?m_temp1=4420