배열중 1개씩만 존재하는 숫자 2개를 찾아내기.

하나의 배열중 1개만 존재하는 하나의 숫자는 찾는 것은 XOR로 찾아내면 된다.

하지만 2개가 존재할 경우에는 어떻게 찾아야 할까? 이것도 XOR로 찾아내면 된다. 단, 2번의 loop가 필요하다.

/* 1개 존재하는 숫자가 1개 있을 경우 */
var arr1 = [1,3,2,4,1,3,2,4,20]
console.log(arr1.reduce( (p,a)=>p^a, 0));  // 20
 
/* 1개 존재하는 숫자가 2개 있을 경우 */
var arr2 = [1,3,2,4,7,1,3,2,4,10];
console.log(arr2.reduce( (p,a)=>p^a, 0));  // 13이나온다. 답이 아님

1개 짜리 숫자 2개가 xor연산이 되어버린다. 위의 예시를 보자면 7 ^ 10 = 13

  7 = 이진수   111

10 = 이진수 1010

13 = 이진수  1101

xor 특성상 1이 홀수개가 존재할 경우에 1이 존재하게 된다. 즉 모든 값들을 xor했을 때 1이 존재하는 것은 해당 값이 홀수개가 존재한다는 것이다.

그렇기에 1을 기준으로 xor 연산을 하게 될 경우 하나의 값은 찾을수 있게 된다. 

/* 1개 존재하는 숫자가 2개 있을 경우 */
var arr2 = [1,3,2,4,7,1,3,2,4,10];
 
function arrXor(arr) {
    return arr.reduce( (p,a)=> p^a, 0 );
}
 
 
function separateTwoNum(num, arr) {
    // 비트중 가장 오른편의 1인 값을 가져온다.
    var one = num & (-num);
 
    // 위에서 구한 값이 존재하는 숫자들을 xor하면서 홀수개인 둘중 하나의 숫자를 찾는다.
    var oneNumber = arr.reduce( (p, a) => (one&a) === 1 ? p^a:p, 0);
 
    // 나머지를 xor 연산해서 반환한다.
    return [oneNumber, num ^ oneNumber];
}
 
separateTwoNum( arrXor(arr2), arr2);  // [7, 10]