Algorithms-[Bit Mask]

우선 비트마스킹은 이름에서 알 수 있듯이 비트를 이용한 알고리즘이다. 

정확히 하자면 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법이다.

비트마스킹을 사용하면 더 빠르고 간결한 코드와 메모리 효율성을 얻을 수 있다. 우선 비트마스킹에 대해 설명하기전에 비트마스킹을 할 때 쓰이는 비트연산자의 종류에 대해 알아보자. 

우선 비트마스킹이 빠른 이유는 집합등을 관리(삭제,추가 등)을 할 때 집합안의 유무를 0,1두개로 표현하여 간편하다.

각각의 자리르 지정해두고 그 자리의 비트가 1이면 집합에 있는것, 0이면 그 집합에 존재하지 않는 것을 의미한다.

예를들어 A,B,C,D,E,F가 있을 때 각각 A는 첫번째 자리, B는 두번째 자리 이렇게 쭉 정해놨으면 {A}라는 부분집합은 

100000(64)를 의미한다. 다음으로 {B}는 010000을 의미하고 {A,B}는 110000을 의미한다. 이런식으로 집합의 표현을 이진수로 표현한뒤 이진수를 10진수로 변경하여 10진수하나로 부분집합등을 나타낼 수 있다. 

다음으로 방금처럼 나타낸 이진수에서 집합을 추가하기 위해서는 lists = lists | (1 << p) 이렇게 해주면 p번째 원소를 추가해주는 것이된다. 쉽게 설명하자면 'C'라는 단어를 집합에 추가하기 위해서 사전에 C가 몇번째 비트자리인지 정해주고(방금 예제에서의 p가 C의 자리에 해당함) 그 p를 쉬프트해주면 되는 것이다. 

위 처럼 부분집합을 정수하나로 표현할 수 있으면서 추가,삭제등도 훨씬 빠르다. 비트마스킹의 더 많은 사용법은 

https://rebro.kr/63 을 참고하여 공부하였다.

출처:Rebro의 코딩 일기장