[CS] 비트마스킹 | 비트 연산자 | 비트마스킹과 집합

비트마스킹(Bitmasking a.k.a. lightweight)

컴퓨터는 숫자나 데이터를 이진수로 표현한다. 이진 표현을 수정하고 활용하는 과정이 비트마스킹이다.

비트마스킹은 비트 연산을 사용하여 특정 비트의 값을 설정하거나 검사하는 방법을 제공한다. 비트마스킹을 통해 메모리를 절약하고 연산 속도를 향상시킬 수 있다.

 

비트 연산자

AND(a&b)	둘다 1이면 1, 아니면 0
OR(a|b)	둘다 0이면 0, 아니면 1
XOR(a^b)	같으면 0, 다르면 1
NOT(~a)	0 → 1, 1 →0
LS(a << 2)	a를 2비트 만큼 왼쪽 시프트(001(2) → 100(4))
RS(a >> 2)	a를 2비트 만큼 오른쪽 시프트

 

---

비트마스크와 집합

비트마스크를 활용하여 집합 연산을 쉽고 빠르게 사용할 수 있다. 이를 통해 문제 해결을 쉽고 빠르게 할 수 있다!

원소의 개수가 N인 집합이 있다고 하자.

각 원소를 0번부터 (N-1)번까지 번호를 부여한다. 

번호에 해당하는 비트가 1 → 포함, 0 → 미포함

 

비트마스크와 집합 원소 추가 | 삭제 | 연산

추가

집합 A에 원소 p를 추가하기 위해서는 다음과 같은 비트 연산을 활용할 수 있다.

• 1<<p : p번 비트만 1, 나머지 비트는 0으로 만들고 OR 연산을 수행하면 a의 p번 비트는 1로 바뀌고 나머지는 그대로 둘 수 있다.

a = a | (1 << p)

 

삭제

집합 A의 원소 p를 삭제하기 위해서는 다음과 같은 비트 연산을 활용할 수 있다.

• 1 << p 연산 후, NOT 연산을 통해 p번 비트만 0으로 만들고 AND 연산을 수행한다면 p번 비트만 0으로 바뀐다.

a = a & ~(1 << p)

 

연산

비트마스크를 활용하여 합/교/차집합 등을 쉽게 구할 수 있다.

a | b # a와 b의 합집합
a & b # a와 b의 교집합
a & ~b # a와 b의 차집합(a-b)
a ^ b # a와 b 중 하나에만 포함된 원소들의 집합

---

Reference

https://www.geeksforgeeks.org/what-is-bitmasking/

https://travelbeeee.tistory.com/451