[알고리즘] 비트마스킹

비트마스킹이란?

비트 즉, 2진수를 가지고 자료구조를 표현해서 더 빠르고 효율적으로 연산을 수행할 수 있습니다.

 

특히 집합 표현을 간결하고 빠르게 할 수 있습니다.

예를 들어 1101 이라는 이진수가 있다면, 각 자리수가 1이라면 그 자리수에 해당하는 것이 존재하는 것이고, 0이면 존재하지 않는다는 식입니다.

 

이것을 가지고 여러 연산을 수행할 수 있습니다.

 

비트 연산

우선 기본적인 비트 연산을 자바 기준으로 살펴보겠습니다.

모든 연산은 이진수의 각자리를 비교합니다.

연산자	뜻
&	AND (둘다 1이면 1, 아니면 0)
|	OR (둘 중에 하나 이상이 1이면 1, 둘 다 0이면 0)
^	XOR (둘 이 서로 다르면 1, 같으면 0)
~	1항 연산자로서 1이면 0으로 0이면 1로 바꿈
A << k	정수 A를 이진수로 변환하여 k자리수만큼 왼쪽으로 옮김. (빈자리는 0으로 채워짐, MSB가 1이 되면 음수로 바뀜)
A >> k	위와 같고, 빈자리는 정수 A의 MSB와 같은 값으로 채워짐
A >>> k	정수 A를 오른쪽으로 k자리수(비트)만큼 이동하고 (빈자리를 0으로 채움)

 

집합 연산

연산	사용 예시
공집합	A = 0;
꽉 찬 집합	(A 중에서  2진수 4자리를 사용한다면) A = (1 << 4) - 1; (1 << 4) : 10000 (1 << 4 - 1) : 1111
원소 추가	A |= (1 << k); (1 << k)의 0들은 A에 아무런 영향을 못 줌
원소 삭제	A &= ~(1 << k); A에서 1인 것은 ~(1 << k)의 1들이 아무런 영향을 못 줌. A가 1이고 ~(1 << k)가 0인 것만 0으로 바뀜. ex) 13 |= ~(1 << 2); 13 == 1101 1 << 2 == 100 ~(1 << 2) == 1111...111011 13 |= ~(1 << 2) == 0000...0001001 == 1001
원소의 포함 여부 확인	if((A & (1 << k)) == (1 << k))
원소의 토글(toggle)	A ^= (1 << k);
두 집합에 대해서 연산	A | B       → A와 B의 합집합 A & B     → A와 B의 교집합 A & (~B) → A에서 B를 뺀 차집합 A ^ B     → A와 B중 하나에만 포함된 원소들의 집합
집합의 크기 구하기	Integer.bitCount(A)
최소 원소 찾기	int first = A & (-A);
최소 원소 지우기	A &= (A - 1);
모든 부분 집합 순회하기	for (int subset = A ; subset>0; subset = ((subset - 1) & A)){ }

 

 

참조

https://loosie.tistory.com/238