본문으로 건너뛰기

비트마스킹

비트 연산자​

연산자설명예시
a & ba의 모든 비트와 b의 모든 비트를 AND 연산한다.
둘다 1이라면 1, 아니면 0		a = 4 = 100(2)
b = 7 = 111(2)
a & b = 100(2) = 4
a | ba의 모든 비트와 b의 모든 비트를 OR 연산한다.
둘다 0이라면 0, 아니면 1		a = 2 = 010(2)
b = 5 = 101(2)
a | b = 111(2) = 7
a ^ ba의 모든 비트와 b의 모든 비트를 XOR 연산한다.
둘이 다르다면 1, 아니면 0		a = 3 = 011(2)
b = 5 = 101(2)
a ^ b = 110(2) = 6
~aa의 모든 비트에 NOT 연산을 한다.
0이면 1, 1이면 0		3비트라고 가정
a = 3 = 011(2)
~a = 100(2) = 4
a << ba를 b비트 만큼 왼쪽으로 시프트a = 1 = 001(2)
a << 2 = 100(2) = 4
a >> ba를 b비트 만큼 오른쪽으로 시프트a = 4 = 100(2)
a >> 2 = 001(2) = 1

상태체크 (if)​

if ((myBit & (1 << 3)) == (1 << 3)) {
...
}
  • 의미: myBit의 4번째 비트 자리가 1인지?

같은 의미이지만 더 자주 쓰이는 코드

if ((myBit & (1 << 3)) != 0) {
...
}
  • 여기서 착각하기 쉬운게 "n번째 자리의 1을 체크하려면 != 0 말고 == 1 을 써도 되는게 아닌가?" 라고 생각할 수도 있지만, 그렇게 되면 계속 1번째 자리만 확인하게 되므로 != 0을 사용하는 것이 맞다.

잘못된 예

if ((myBit & (1 << 3)) == 1000) {
...
}
  • 결과값이 2진수 이기 때문에 == 1000 이런식으로 비교해서는 안된다.
  • 저 의미를 담고싶다면 if ((myBit & (1 << 3)) == 8) 이렇게 해야한다.

방문처리​

myBit = myBit | (1 << 2);
  • 의미: myBit 의 3번째 자리를 1로 방문처리 함

효율적인 사용 예시​

상태 관리​

  • 상태 관리나 방문처리를 할 때 bool 타입 배열을 만든다면 1000개의 상태 관리를 할 때 1000바이트(8000비트)가 필요하다.
  • 비트마스크로 처리를 한다면 int 1개에 32개의 bool 타입 상태를 나타낼 수 있다. 즉, 1000개의 상태를 관리를 할 때 비트마스크로 처리를 한다면, 약 125바이트(1000 / 32 = 약 125)로 처리를 할 수 있으므로 1/8의 메모리를 사용하고도 똑같은 처리를 할 수 있다.
    • int의 최대 표현 수가 2312^{31} 이므로 32비트를 나타낼 수 있다.

집합 연산​

비트마스크는 "집합"을 다루는 데 효율적이다. (집합 라이브러리보다 훨씬 빠르고, 메모리도 적게 든다)

  • 원소 추가: mask |= (1 << x)
  • 원소 제거: mask &= ~(1 << x)
  • 원소 포함 여부: if (mask & (1 << x))
  • 두 집합의 합집합: maskA | maskB
  • 교집합: maskA & maskB

예시:

  • 5 = 101010
  • 4 = 011100
  • 합집합 = 111110
  • 교집합 = 001000

부분집합 (중요)​

int arr[] = {3, 6, 7, 1, 5, 4};
int size = arr.length; // 전체 집합이 6개 이므로

for (int i = 0; i < (1 << size); i++) { // 2^n 개의 부분집합
	for (int j = 0; j < size; j++) {    // 매 자리의 비트 확인
		if ((i & (1 << j)) != 0) {   // i의 j번째 비트가 1이면 j번째 원소 출력
			System.out.print(arr[j] + " ");
		}
	}
	System.out.println(); // 줄바꿈 - 부분집합 하나 완료
}
  • 첫번째 for 문에서 (1 << size)는 1000000 즉 64를 나타내기 때문에 262^6 번 반복한다.
  • 두번째 for 문에서 부분집합의 각 자리의 상태를 확인하고 출력한다.
  • 원래 부분집합을 구하려면 '선택/비선택' 분기를 나눠 재귀적으로 구현했지만, 비트마스크를 쓰면 2중 for문으로 끝난다.
    • 재귀는 부분집합을 담기 위해 매번 리스트를 새로 만들어야한다. 하지만, 비트마스크는 단일 정수로 상태를 표현 (메모리 효율성)
  • 집합 연산을 할 때 재귀로 만든 부분집합 리스트는 매 배열을 비교하는 O(n2)O(n^2) 연산이 필요하지만, 비트마스크를 쓰면 O(1)O(1)로 처리할 수 있다.
    • 합집합: maskA | maskB
    • 교집합: maskA & maskB
    • 차집합: maskA & ~maskB
  • 집합을 생성하는 연산은 둘다 O(2n∗n)O(2^{n}*n) 으로 같다.

외판원 문제(TSP)​

  • 외판원 문제에서 DP와 비트마스크를 함께 사용하여 효율적인 문제 풀이가 가능하다.
  • dp[mask][i]: mask 집합을 방문하고 i에서 끝나는 최소 비용