[JAVA / 자바] 비트 마스킹(Bit Mask), BitSet자료형

비트 마스킹 / 비트 마스크 (BitMasking / BitMask)

  : 정수의 이진수 표현을 사용하는 기법

 

장점

1. 연산 시간이 빠름 - 비트 마스킹은 bit연산이므로 거의 모든 연산이 O(1)의 시간 복잡도를 갖고 있다. 따라서 다른 연산자를 이용한 연산보다 연산 시간이 빠르다.

2. 코드가 짧음 - 다양한 집합 연산을 비트 연산자를 이용하여 한 줄로 작성이 가능하다.

3. 메모리 사용량이 적다 - 데이터를 미리 계산하여 저장 가능하고, boolean 자료형의 경우 1byte(= 8bit)의 메모리가 필요한 반면, 비트로 저장하면 1bit만 사용한다. => 동적 계산법 (DP : Dynamic Programming)에 유리

---

비트 연산자

비트 연산자	논리	의미
&	AND	양쪽 비트가 모두 1인 경우에만 1, 나머지 모든 경우 0
|	OR	양쪽 비트가 모두 0인 경우에만 0, 나머지 모든 경우 1
^	XOR	양쪽 비트가 서로 다른 경우 1, 같은 경우 0
~	NOT	비트 반전 (= 0이면 1, 1이면 0으로 바꿈)
<<	SHIFT	정수 a를 왼쪽으로 b비트 만큼 이동 (빈자리 0으로 채움, MSB가 바뀌면 양수↔음수)
>>		정수 a를 오른쪽으로 b비트 만큼 이동 (빈자리 최상위 비트(MSB)로 채움)
>>>		정수 a를 오른쪽으로 b비트 만큼 이동 (빈자리 0으로 채움)

---

비트 마스크로 집합(A) 연산

연산	예시 코드	설명
공집합	변수 = ((1 << A) - 1);	0 반환
꽉 찬 집합		A의 개수만큼 비트 켜짐(1)
원소 추가	A |= (1 << k);	k번째 비트 켜기
원소 삭제	A &= ~(1 << k);	k번째 비트 끄기
원소 포함 여부	A & (1 << k) == (1 << k)	집합 A에서 k 번째 비트의 켜짐, 꺼짐 확인
원소 토글	A ^= (1 << k);	k번째 비트 반전
두 집합 연산	A | B	집합 A와 집합 B의 합집합
	A & B	집합 A와 집합 B의 교집합
	A & -B	집합 A - 집합 B (차집합)
	A ^ B	집합 A와 집합 B 합집합 - 교집합 (XOR)
집합의 크기	Integer.bitCount(A);	집합 A내 켜진 비트수 반환
최소 원소 찾기	변수 = A & (-A);	집합 A에서 켜져있는 비트 중 최소 비트 반환
최소 원소 삭제	A &= A-1;	집합 A에서 켜져있는 비트 중 최소 비트 끄기
부분 집합 순회	for(int i=A; i; i=((i-1)&A)) {}	집합 A의 부분집합 순회

---

BitSet

import java.util.BitSet;

BitSet b = new BitSet();

연산	코드
원소 삽입	b.set(int index);
원소 호출	b.get(int index);
원소 반전 (삽입↔삭제)	b.flip(int index);
원소 삭제	b.clear(int index);

index는 비트 인덱스를 의미 = 해당 인덱스의 스위치를 조절함으로 해당 숫자가 삽입/삭제 및 유/무의 상태도 확인