[JS] 비트 마스크 (BitMask)

✨ 비트 연산자 (Bit Operator)

비트를 직접 조작하는 연산자

// 비트 연산자
const x = 10; // 1010
const y = 12; // 1100

x & y; // AND - 8
x | y; // OR - 14
x ^ y; // XOR - 6
// 000000000000000000000000000001010
// 111111111111111111111111111110101
// 2의 보수
~x; // NOT - -11
x << 1; // Left Shift - 10100 - 20
x >> 1; // Right Shift - 101 - 5

 

✨ 비트 마스크 (BitMask)

• 이진법 성질을 이용하여 문제를 해결하는 방법
• 특정 알고리즘은 아니고 비트 연산을 이용한 일종의 코딩 기법
• 이진수가 자료 구조로 사용된다.
  • ex) [true, true, false, true] = 13(1101)
• 굉장히 빠르고 메모리 사용량이 적다.
• Greedy, Dynamic Programming 등 다른 알고리즘과 함께 사용할 수 있다.

 

비트를 배열(집합)처럼 사용하는 Tip

억지로 외울 필요는 없음

• false로 초기화 하기 → bit = 0;
• N개 만큼 true로 초기화하기 → bit = (1 << N) - 1;
• i번째 요소 true로 바꾸기 → bit |= (1 << i);
• i번째 요소 false로 바꾸기 → bit &= ~(1 << i);
• i번째 요소 토글하기 → bit ^= (1 << i);
• i번째 요소가 true인지 체크하기 → bit & (1 << i);

 

두 집합끼리 연산하기

• 합집합 → A | B;
• 교집합 → A & B;
• A에서 B를 뺀 차집합 → A & (~B);
• 합집합에서 교집합 제외 (xor) → A ^ B;

 

주의할 점

• 정수형 범위를 넘지 않도록 조심할 것 (JS에서도 비트 연산은 정수 범위를 넘을 수 없다.)
• 연산자 우선 순위에 주의할 것

 

 

---

✨ 관련 문제 풀이

 

https://lazyhysong.tistory.com/entry/JS-BitMask-%EB%B9%84%EB%B0%80%EC%A7%80%EB%8F%84

[JS] BitMask - 비밀지도