비트 연산 XOR

핑크공듀가 나타났다

문제 설명

정수 num1, num2가 매개변수로 주어질 때, num1를 num2로 나눈 나머지를 return 하도록 solution 함수를 완성해주세요.

제한사항

0 < num1 ≤ 100
0 < num2 ≤ 100

내 풀이

const solution = (num1, num2) => num1 % num2

핑크공듀 풀이

3번째 イコモチ의 풀이, 로그인 필요

function hiki(x , y) {
    if (y == 0) return x;
    return hiki(x ^ y, (~x & y) << 1);
}

function kake(a, b) { 
    var res = 0;
    while (b > 0) { 
        if (b & 1) res = res + a; 
        a = a << 1; 
        b = b >> 1; 
    } 
    return res; 
} 

function wari(w1, w2) {
    var sign = ((w1 < 0) ^ (w2 < 0)) ? ~0x00 : 0x01;
    w1 = Math.abs(w1);
    w2 = Math.abs(w2);
    var quotient = 0;
    while (w1 >= w2) {
        w1 -= w2;
        ++quotient;
    }
    if(sign == ~0) quotient =- quotient;
    return quotient;
}

function solution(num1, num2) {
    return hiki(num1, kake(num2, wari(num1, num2)));
}

엄청 복잡하다. 하나만 살펴보자

^: XOR

• 토글 가능, 따라서 원본 없이 원본 복구됨
• 자릿수가 변하지 않는다, 받아올림이 없다, sum without carry

return hiki(x ^ y, (~x & y) << 1);
첫 함수의 반환행을 보자. 여기서 등장하는 ^는 바이너리 연산자이다. XOR이라 부른다. 같은 자리의 비트가 같으면 0, 다르면 1이 된다.

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

더 큰 자릿수의 수를 연산하는 예를 보자.

  0101  (5)
^ 1011  (11)
------
  1110  (14)

도대체 이런 연산이 어디에 도움이 된다는 것인가? 이 XOR은 다음과 같은 장점이 있다.

1. 원본값을 저장하지 않고도 복구할 수 있다. (토글 가능)

앞서 5 ^ 11 = 14라는 결과를 얻었다. 여기서 나는 원본값(5)를 11이라는 키를 이용해 조작해 14를 얻었다. 14에서 다시 5로 가기 위해선 다시 ^11을 하면 된다.

  1110  (14)
^ 1011  (11)
------
  0101  (5)

같은 연산을 반복했을 뿐인데 원본이 복구된다.

2. 자릿수가 변하지 않는다.

• 전체 자릿수가 변하지 않는다.
• 한 자리에서의 연산은 다른 자리에 영향을 주지 않는다.

단순히 원본을 복구하고 싶다면 더하기를 이용해도 되지 않겠는가? 더해서 값을 조작하고 다시 빼서 복구하면 될 것 같다. 하지만 더하기의 경우 수의 자릿수를 바꿀 수도 있다. 그러나 XOR은 각 자릿수를 비교하기만 하기 때문에 비트의 자릿수, 길이는 변하지 않는다.
또한 덧셈에서는 전체 자릿수가 유지되더라도 각 자릿수의 합이 10 이상이 되어 그 이후 자릿수에도 영향을 줄 수가 있다. 하지만 XOR에서는 각 자릿수의 연산은 각 자릿수에서 끝난다.

번외: 스스로가 스스로의 역원

XOR은 토글이 되기 때문에 재미있는 성질이 있다.
XOR 연산의 항등원은 0이다.
XOR 연산의 역원은 자기 자신이다.
a ^ 0 = a (identity)
a ^ a = 0 (always!)

받아올림으로 덧셈 만들기

덧셈은 두 부분으로 나눌 수 있다.
1. 자릿수 변화 없이 일어나는 부분
2. 자릿수를 변화시키는 받아올림

// 10진수 덧셈
  123
+ 495
-------
  518  <--- 받아올림 없는 덧셈
  1    <--- 받아올림
-------
  618
  
// 2진수 덧셈
  1010
+ 1100
-------
  0110  <--- 받아올림 없는 덧셈
 1      <--- 받아올림
-------
 10110

2진수에서 받아올림을 만들어내기 위해선 다음이 필요하다.
1. 각 자리가 1로 같은 곳을 살리고 나머지는 죽인다.
2. 살아남은 자릿수를 하나씩 올린다.

   덧셈 = 받아올림 없이 + 받아올림
5 + 11 =   5 ^ 11  + (5 & 11) << 1

이를 위해 필요한 두 연산자를 알아보자.

&: bitwise AND

둘 다 1인 곳만 살아남긴다.

~x = 1010
y  = 0011
---------
   = 0010  (1 only where both bits are 1)

<<: Shifts bits to the left

5 << 1   // 5 shifted left by 1
         // 0101 -> 1010

완성된 덧셈 함수

function sum(x, y) {
	if (y === 0) { retun x} // 더 이상 더할 게 없으면 함수 종료
  
  return sum(x ^ y, (x & y) << 1) // 받아올림 없는 합과 받아올림을 더함
}

뺄셈

뺄셈도 마찬가지로 계산할 수 있다.
뺄셈 = 받아내림 없는 뺄셈 - 받아내림

받아내림 구현하기

~x = bitwise NOT (flips all bits)

x = 5 = 0101
~x    = 1010  (flips every bit)

// 2진수 뺄셈
  1000
+ 0110
-------
  1110  <--- 받아내림 없는 뺄셈(다른 것들만 살아남김)
  11    <--- 받아내림(위가 0, 아래가 1이면 앞에서 1을 받아내려야 함)
-------
  0010

완성된 뺄셈 함수

function subtract(x, y) {
 if (y === 0) { return x }

 return subtract(x ^ y, (~x & y) << 1)
}