비스마스킹

• 집합을 쉽게 표현할 수 있다.
• 집합에 원소를 추가,삭제하는 등 다양한 연산을 빠르게 수행 가능.
• 해당 인덱스에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함

예)  { A, B, C, D, E, F, G } 집합이 있을때, 
총 7개의 원소가 존재하므로 우리는 7개의 비트로 이 집합을 표현할 수 있다.

즉, 각 원소마다 비트를 하나씩 대응시켜서 원소가 존재한다면 1, 존재하지 않다면 0으로.

{ A } 라는 부분집합은 64 = 1000000(2) 로 표현하고
{ C, F } 는 18 = 0010010(2) 로 표현됨.

 

원소 추가하기 

현재 상태 cur이 있을 때, p번 원소를 추가한다고 할때,  cur에서 p번 비트를 1로 바꿔줘야 한다.

a | b 비트연산자를 사용.

cur = cur | (1 << p)

원래 상태 cur에서 1 << p를 통해 p번 비트를 1로 설정하고,  | 연산을 진행한다면 cur의 p번 비트는 1로 바뀌게 되고, 나머지 비트는 원래 상태를 유지하게 된다. 

 

 

원소 삭제하기

현재 상태 cur에서 p번 원소를 삭제한다고 할때, p번 비트를 0으로 바꿔줘야한다.

cur = cur & ~(1 << p);

 1 << p 를 통해서 p번 비트만 1로 만든 것에, ~ 연산을 통해 p번 비트만 0으로 만들고

& 연산을 진행한다면 p번 비트만 0으로 바뀌고 나머지는 현재 상태 cur과 동일하게 유지하게 된다.

 

 

원소 토글

토글: p번 비트가 1이면 0, 0이면 1로 바꾸는 것.

현재 상태 cur에서 p번 원소가 있다면 삭제하고, 없다면 추가하기

cur = cur ^ (1 << p);

 1 << p 를 통해서 p번 비트만 1,  cur의 나머지 비트들은 0과 XOR 연산을 진행하므로

0이면 0, 1이면 1로 현재 상태를 유지하게 되고,

p번 비트는 1과 XOR 연산을 진행하므로 1이면 0, 0이면 1로 바뀌게 된다.

(XOR 연산: 같으면 0 반환, 다르면 1 반환)

 

 

집합 연산

a | b; // a 와 b의 합집합
a & b; // a 와 b의 교집합
a & ~b; // a 에서 b를 뺀 차집합
a ^ b; // a와 b 중 하나에만 포함된 원소들의 집합

 

 

 

집합의 크기 구하기

집합의 크기를 구하려면, 현재 1로 켜져 있는 비트의 수를 count 해야 한다.

따라서, 모든 비트를 순회해야 되고 재귀적으로 다음과 같이 구현할 수 있습니다.

int bitCount(int x){
	if(x == 0) return 0;
	return x % 2 + bitCount(x / 2);
}

 x % 2 를 하면 마지막 비트를 얻게 되고, x / 2 를 하게 되면 마지막 비트를 삭제할 수 있다.

따라서, 모든 비트를 재귀적으로 순회할 수 있게 된다.

 

 

 

모든 부분집합 순회하기

for(int subset = set; subset; subset = (subset - 1) & set){
	// subset은 set의 부분집합 중 하나.
}

 예를 들어, 집합이 { A, B, D } 일 때, 

 모든 부분 집합은 공집합을 제외하고 { A }, { B }, { D }, { A, B }, { A, D }, { B, D }, { A, B, D } 가 존재한다.

 비트로 표현하면 다음과 같다.

{ A, B, D }	1101(2)
{ A, B }	1100(2)
{ A, D }	1001(2)
{ B, D }	0101(2)
{ A }	1000(2)
{ B }	0100(2)
{ D }	0001(2)

 위에서 구현한 코드를 순서대로 보면

처음 subset= set = 1101(2) = { A, B, D } 

subset	(subset - 1)	(subset - 1) & set
1101(2) // { A B D }	1100(2)	1100(2)
1100(2) // { A B }	1011(2)	1001(2)
1001(2) // { A D }	1000(2)	1000(2)
1000(2) // { A }	0111(2)	0101(2)
0101(2) // { B D }	0100(2)	0100(2)
0100(2) // { B }	0011(2)	0001(2)
0001(2) // { D }	0000(2)	0000(2) // 종료

 for문을 통해 모든 부분 집합을 다 순회하는 것을 확인할 수 있다.