[JavaScript] 비트연산자 XOR(^)

XOR ?? 그게 뭐에요...

알고리즘 문제를 풀던 중 해괴한 연산자를 만나버렸다.
XOR(^) 이라는 연산자였는데, 사실 이게 연산자라는 것도 예시를 보고 알았다 듣도 보도 못해본 연산자니까 일단 냅다 MDN 검색 ㄱㄱ

MDN 비트 XOR(^) 연산자 문서를 보면 알겠지만, 설명이 몹시 불친절하다.

설명에 의하면, XOR 연산자는 각 비트 쌍을 대상으로 연산을 수행한다. a ^ b 는 a와 b가 다르면 1을 리턴하고, 같으면 0을 리턴한다.

이쯤에서 문제를 확인해보자.

문제

There is a hidden integer array arr that consists of n non-negative integers.
It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].
You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].
Return the original array arr. It can be proved that the answer exists and is unique.


대강 내용은 이렇다.

만들어야 할 함수의 인자는 2개다.
1. encoding된 배열 encoded
2. encoding되기 전 원본 배열인 arr의 첫번째 엘리먼트 first

이 때, encoded의 i번째 인덱스에 해당하는 엘리먼트는 arr[i] XOR arr[i + 1] 이다.
따라서 당연히encoded의 길이는 arr.length - 1이 된다.

우리는 encoded와 원본배열의 첫번째 엘리먼트인 first를 받아서 원본 배열인 arr를 반환하는 함수를 만들어야 한다.

여기서 의문.
분명히 MDN에서는 "XOR 연산자는 각 비트 쌍을 대상으로 연산을 수행한다. a ^ b 는 a와 b가 다르면 1을 리턴하고, 같으면 0을 리턴한다." 라고 했는데 XOR 연산을 거친 결과값에 1이나 0이 아닌 수가 등장한다.

보통 연산이라는게 a * b = c 라면 a = c / b 인 것처럼 가는게 있으면 오는게 있는 법이니까.. 그렇다면 XOR 연산자도 반대 연산자가 있을까 검색해보았지만 나오지 않았다.

그래서 시작된 나의 뻘짓...
(혹시 이 글을 읽게될 누군가가 있다면, XOR 연산자에 대한 진짜 정보는 여기쯤은 되어야 나온다는 것을 미리 밝힙니다.)

XOR 연산자의 규칙을 찾겠다는 황당하고 무모한 시도를 시작했다.

뻘짓의향연.jpg

encoded[i]는 짝수고 arr[i]은 홀수인 경우만 제외하면 규칙을 찾았다고 생각했지만 오산이었다.

var decode = function(encoded, first) {
    let arr = [first];
    encoded.reduce((acc, curr) => {
        if (curr % 2 === 0 && acc % 2 !== 0) {
          arr.push( Math.abs(acc - curr) ); 
          return Math.abs(acc - curr);
      } else {
          arr.push(Math.abs(curr - acc));
          return Math.abs(curr - acc);
      }
    }, first);
    return arr;
};

내가 생각한 규칙에 따르면,
encoded = [1, 2, 5, 2, 4], first = 1 을 받았을 때 결과값으로 [1, 0, 2, 3, 5, 1]이 반환되어야 한다. 하지만 정작 반환된 값은 [1, 0, 2, 3, 1, 3] 였다. 내가 만든 테스트케이스가 잘못되었나 싶어서 일단 실행시켜봤다.

실행결과001.jpg

문제는 encoded[i]는 짝수고 arr[i]은 홀수인 경우가 아니었다. 그냥 내가 생각한 룰 자체가 잘못됐던 것. 그래서 다시 원점으로 돌아가 되는대로 뒤지다가 진짜 룰을 발견했다.

뻘짓의향연AndFinally.jpg

맨 아래쪽을 보면 5 ^ 3 의 결과가 6이 나온 것이 보인다. 그 다음 줄에 보면 3 ^ 5 의 결과도 6 이 나왔다. 뺄셈의 절댓값도 아니고 도대체 무슨 규칙일까 고민하다가 시도해본 3 ^ 6 . 놀랍게도 결과는 5 였다. (설마 니들 듀오가 아니라 트리오였니..?)
바로 5 ^ 6 을 확인해보니 3이 나온다. YEAHHHHHH!!!!!!

그 후로 이것 저것 테스트 케이스를 더 돌려보고 트리오라는 확신을 얻고나자 그제서야 보이는 문제의 그 단어, encoded.
암호와 키와 원본은 당연히 한 쌍으로 움직여야 한다는 걸 놓친 것부터 잘못된거였다...

Anyway, 내가 알아낸 XOR 연산자의 규칙은 다음과 같다.

XOR 연산자

let a = 5;
let b = 3;
// a와 b는 임의의 정수 아무거나 상관없다.
const result = a ^ b; // --> 5 ^ 3 === 6 

console.log(b ^ a); // --> 6
console.log(a ^ result); // --> 3
console.log(result ^ a); // --> 3
console.log(b ^ result); // --> 5
console.log(result ^ b); // --> 5

a XOR b 의 결과가 c일 때, (a, b, c)가 한 쌍이라고 보면 된다. 셋 중 아무거나 두개를 골라 XOR 연산을 실행하면 결과는 나머지 하나가 나온다.

이 규칙을 알고나면 문제는 반복문을 통해 간단하게 해결할 수 있다. 혹시 나중에 이 글을 읽게 될 수도 있으니 정답은 생략하겠다. (새로 풀어보자!!)

실행결과-최종.jpg

마치며

힘겹게 알아낸 규칙이라서 정리해두려다가 뻘짓의 향연이 진짜 '뻘짓' 은 아니었다는 생각에 그 과정을 주절거려봤다. 역시 시행착오를 겪으면서 해결방법을 찾아내는게 코딩의 매력인 것 같다.

-끝-

---

모든 케이스를 확인해보고 검증을 완료한 규칙이 아니기 때문에 잘못된 부분이 있을 수 있습니다. 오류를 발견하셨다면 댓글로 알려주시면 감사하겠습니다. 🙇‍♀️