비트마스킹 - 비트로 집합을 표현하는 방법

집합의 표현

집합을 표현하는 여러가지 방법 중에 비트를 이용하는 방법이 있다.

만약 64비트 정수를 쓴다면 원소의 개수가 64개보다 작은 집합을 나타낼 수 있다.

집합을 아래와 같이 비트로 표현할 수 있다.

{1, 2, 3, 4, 5} -> 11111

{2, 3, 4, 5} -> 11110

{1, 3, 5} -> 10101  

i 번째 비트만 1로 바꾸기 - or 연산

set = set | (1 << (i -1));

ex) i = 2 일때, 0000 | (1 << 1 )  ->  0000 | 0010   -> 0010 

i 번째 비트만 0로 바꾸기 - and 연산

set = set & ~(1 << (i -1));

ex) i = 2 일때, 1111 & (1 << 1 )  ->  1111 & ~0010   -> 1111 & 1101 -> 1101

i 번째 비트만 뒤집기 - xor 연산

set = set ^ (1 << (i -1));

ex) i = 2 일때, 1111 ^ (1 << 1 )  ->  1111 ^ 0010   ->  1101

i 번째 비트가 1인지 0인지 확인

set & 1 << (i - 1);

ex) 1100 & (1 << 2) -> 1100 & 0100 -> 0100 -> 결과값 != 0 -> i번째 비트가 1

i번째 비트만 0으로 만들기

set = set & ~(1 << (i - 1))
ex) 11011 & ~(1 << 3) = 11011 & ~(01000) = 11011 & 10111 = 10011

0 ~ n-1번 비트까지 모두 1인지 확인

set == (1 << n) - 1
ex) n이 4라면 1 << 4 = 10000이고 10000 - 00001은 01111이다.

 

비트 마스킹을 사용하는 문제

백준 11723 집합

백준[11723] 집합

백준 2098 원판원 순회

백준[2098] 외판원 순회

백준 1311 할 일 정하기 1

백준 [1311] 할 일 정하기 1